计算没有连续 1 的二进制字符串

在这个问题中，我们必须找到一些没有连续 1 的二进制数。在一个 3 位二进制字符串中，有三个二进制数 011、110、111 有连续的 1，还有五个数字没有连续的 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)

输入:n 是位数。
输出 − 计算有多少个数字没有连续的 1。

开始
   定义以 0 结尾和以 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]
结束

示例

#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 << "输入位数:"; cin >> n;
   cout << "没有连续 1 的二进制数的数量:"<<countBinNums(n) << endl;
   return 0;
}

输出

输入位数:4
没有连续 1 的二进制数的数量:8

相关文章

• 计算没有连续 1 的二进制字符串