資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告