A Write, in Java, a recursive method count BinaryStrings that has one integer pa

Question

A Write, in Java, a recursive method count BinaryStrings that has one integer parameter n and returns the number of binary strings of length n that do not have two consecutive 0's. For example, for n = 4, the number of binary strings of length 4 that do not contain two consecutive 0's is 8: 1111, 1110, 1101, 1011, 1010, 0111, 0110, 0101. For this problem, your method needs to return only the number of such strings, not the strings themselves. You may assume that the integer specified in the parameter is positive. Looking at the example above will give you a hint about how such strings start. The method should be static and embedded in a class called Recursion. This class should also have a main method. In this case, we will call the main method with an argument, the number of bits n. This argument will be in args[0]. You should convert it to an int using the Integer.parseInt method. Look this method up in the Java documentation to see what it does.

Explanation / Answer

Hi,

Let me explain the concept of writing down the below code before getting into the actual code.

So our aim is to find no of binary digits with no consecutive zeroes of any given length n (provided by the user) .

Lets assume A[N] is the no of binary strings possible of length N that end with 0 and B[N] is the no of binary strings possible of length N that end with 1.

So numbers ending with 0 can be appended only with numbers ending with 1 because we dont want consecutive zeroes. but numbers ending with 1 can be appended with either 1 or 0.

So A[1] would be no of binary strings ending with 0 with no 2 consecutive zeroes . Hence A[1] would be 0

Similary B[1] would be no of binary strings ending with 1 with no 2 consecutive zeroes . Hence B[0] would be 1.

So at any point of time A[i] = B[i-1] and B[i] = A[i-1] + B[i-1]

and total no of strings possible with length N would be A[i] + B[i]

Now since the concept is clear lets Code

Class Recursion

{

static int countBinaryStrings(int n)

{

int a[] = new int [n];

int b [] = new int [];

a[1] = 0 ;

b[1] = 1;

for (int i =2; i<n; i++)

{

a[i] = b[i-1] ;

b[i] = a[i-1] + b [i-1];

}

return a[n] + b[n] ;

}

public static void main (String args[])

{

int x = Integer.parseInt(args[0]);

int y = countBinaryStrings(x);

System.out.println(y);

}

}

Integer.parseInt is used to convert a string value to integer.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.