Question

Define a sequence of string of 0’s and 1’s: 1 The first string, s0, is just the empty string "". The second string, s1, is 1. The third, fourth, fifth, . . . strings are defined as follows: si = si−11ti−1 where ti−1 is the reverse of si−1 with all 0s replaced by 1s and all 1s replaced by 0s. The first few strings are s0 = "", s1 = 1, s2 = 110, s3 = 1101100, s4 = 110110011100100. Write a Java program named “ q3d.java” that prints the first 10 strings in this sequence.

Answer 1

To implement above problem we will use following steps:

Algorithm:

1.Take array of string str of size 10 as str[10]

2.Assign str[0]="";

3.Assign str[1]="1";

4.Print str[0];

5.Print str[1];

6.Take a variable i and assign its value 2.

7.Check if value of i is less than 10 if yes then goto step 8 otherwise goto step 13.

8. Call function rev(str[i-1]) and store the result in string t and then reverse the value of string t.

10 Concat string si-1 and "1" with string t and store the result in str[i]

11.Print str[i]

12.Increment the value of i by 1 and then goto step 7.

13 End

Function rev(str):

1.Take a variable i and assign its value to 0.

2.Calculate length of string str and store result in l.

3.Implement a for loop from i =0 to l.

    3.1.) Check if str[i]=='1' if yes then str[i]='0'

   3.2) Else str[i]='1'

4 . Return str;

Java code for this problem.

public class q3d {
    
    public static String rev(String str)
    {
        //implementing rev function
        int i;
        int l =str.length(); //calculating length
        String newstr="";
        for(i=0;i<l;i++)
        {
            if(str.charAt(i)=='0') //if string contains 0 
            {
                newstr=newstr+'1'; //change it to 1
            }
            else
            {
                newstr=newstr+'0'; //else change it to 0
            }
        }
        return newstr;
    }
    public static void main(String args[]) {
    
    String s[]=new String[10]; //take string of array
    s[0]=""; //initialize first sequence
    s[1]="1"; //initialize second sequence
    int i=2; //intiialize i;
    
    String t=""; //for reverse
    while(i<10)
    {
        t=rev(s[i-1]); // calling rev function
        
        StringBuffer sbr = new StringBuffer(t); //creating string buffer for reverse
        
        sbr.reverse(); //reverse the string
        
        s[i]=s[i-1]+1+t; //concating the strings
        
        System.out.println(s[i]); //printing the sequence
        
        i=i+1;
    }
    
    
    
    }
}

Sample Output of above code :