在这个问题中,我们必须找到一些没有连续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