資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究不含連續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]
輸入和輸出
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
更新於： 2020年6月16日
647 次瀏覽
廣告