Write a C++ recursive method countBinary that has one integer parameter n and re

ID: 3769426 • Letter: W

Question

Write a C++ recursive method countBinary 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, 0101For this problem, your method needs to return only the number of such strings, notthe strings themselves. HINT: The number of such strings is the number of stringsthat start with a 1 plus the number of strings that start with 01. Determine the complexity.

Explanation / Answer

#include <iostream>
using namespace std;

int countBinary (int n)
{
    int a[n], b[n];
    a[0] = b[0] = 1;
    for (int i = 1; i < n; i++)
    {
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1] + b[n-1];
}

Complexity -> Log(n)

Navigate

Write a C++ recursive method countBinary that has one integer parameter n and re

Write a C++ recursive method doubleElements that has one parameter, an ArrayList

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

Write a C++ recursive method countBinary that has one integer parameter n and re

Question

Explanation / Answer

Related Questions

Navigate