C/C++ 程序计算没有连续 1 的二进制字符串的数量?
cc++server side programmingprogramming
二进制数是仅包含两个的数字，即有一个或两个。每个二进制数都是二进制位的流，我们将其视为二进制字符串。对于这个字符串，我们需要找到不包含连续 N 位的二进制字符串的数量。
例如，对于 N - 5，满足给定约束的二进制字符串是 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
一种方法是生成所有 N 位字符串并仅打印满足给定约束的字符串。但是这种方法在工作时效率不高。
另一种方法是使用递归。在递归的每个点，我们将 0 和 1 附加到部分形成的数字，并以少一位数字递归。这里的技巧是，只有当部分形成的数字的最后一位数字为 0 时，我们才会附加 1 并递归，这样，输出字符串中就不会有任何连续的 1。
输入:n = 5 输出:没有任何连续 1 的 5 位二进制字符串的数量为 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;
}
