1到n位数字，二进制表示中没有连续的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]

输入值

该算法为二进制数获取位数。让输入为4。

输出结果

它返回不具有连续1的二进制字符串的数量。

此处的结果是−8。（有8个二进制字符串，没有连续的1）

算法

countBinNums(n)

Input: n is the number of bits.
Output: Count how many numbers are present which have no consecutive 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 consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

输出结果

Enter number of bits: 4
Number of binary numbers without consecutive 1's: 8