Home > Article > Backend Development > C/C++ program: Count number of binary strings without consecutive 1's?
A binary number is a number that contains only two digits, that is, only 0 and 1. Each binary number is a stream of binary bits, which we think of as a binary string. For this string, we need to find the number of length N binary strings that do not contain consecutive 1's.
For example, for N=5, the binary string that satisfies the given condition is 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101.
One way is to generate all N-digit strings and print only the strings that satisfy the given condition. However, this approach is not efficient when it comes to large-scale operations.
Another way is to use recursion. At each step of the recursion, we append 0 and 1 to the partially formed number and recurse with one less number. The key is that only if the last digit of the partially formed number is 0, we append 1 and recurse. This way, there will be no consecutive 1's in the output string.
Input: n = 5 Output: Number of 5-digit binary strings without any consecutive 1's are 13
#include <iostream> #include <string> using namespace std; int countStrings(int n, int last_digit) { if (n == 0) return 0; if (n == 1) { if (last_digit) return 1; else return 2; } if (last_digit == 0) return countStrings(n - 1, 0) + countStrings(n - 1, 1); else return countStrings(n - 1, 0); } int main() { int n = 5; cout << "Number of " << n << "-digit binary strings without any " "consecutive 1's are " << countStrings(n, 0); return 0; }
The above is the detailed content of C/C++ program: Count number of binary strings without consecutive 1's?. For more information, please follow other related articles on the PHP Chinese website!