数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究二进制表示中没有连续 1 的 1 到 n 位数字？
在这个问题中，我们必须找到一些没有连续 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)
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
更新于： 2019-07-30
375 次浏览
广告