计算不带连续1的二进制字符串
在这个问题中，我们必须找到一些没有连续1的二进制数。在一个3位二进制字符串中，存在三个具有连续1的二进制数字011、110、111，并且有五个没有连续1的数字。因此，将此算法应用于3位数字后，答案将为5。
如果a[i]是二进制数的集合，其位数为I，并且不包含任何连续的1，而b[i]是二进制数的集合，其中位数为I，并且包含连续的1，则存在类似的重复关系：
a[i] := a[i - 1] + b[i - 1] b[i] := a[i - 1]
输入输出
Input: This algorithm takes number of bits for a binary number. Let the input is 4. Output: It returns the number of binary strings which have no consecutive 1’s. Here the result is: 8. (There are 8 binary strings which has no consecutive 1’s)
算法
countBinNums(n)
输入：n是位数。
输出-计算存在多少个不连续的数字1。
Begin
define lists with strings ending with 0 and ending with 1
endWithZero[0] := 1
endWithOne[0] := 1
for i := 1 to n-1, do
endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
endWithOne[i] := endWithZero[i-1]
done
return endWithZero[n-1] + endWithOne[n-1]
End示例
#include <iostream>
using namespace std;
int countBinNums(int n) {
int endWithZero[n], endWithOne[n];
endWithZero[0] = endWithOne[0] = 1;
for (int i = 1; i < n; i++) {
endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
endWithOne[i] = endWithZero[i-1];
}
return endWithZero[n-1] + endWithOne[n-1];
}
int main() {
int n;
cout << "Enter number of bits: "; cin >> n;
cout << "Number of binary numbers without consecitive 1's: "<<countBinNums(n) << endl;
return 0;
}输出结果
Enter number of bits: 4 Number of binary numbers without consecitive 1's: 8