資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究用 C/C++ 計算不含連續 1 的二進位制字串數量的程式？
這裡我們將看到一個有趣的問題。假設給定一個 n 的值。我們必須找到所有長度為 n 的字串，這些字串中沒有連續的 1。如果 n = 2，則數字為 {00, 01, 10}，所以輸出為 3。
我們可以使用動態規劃來解決它。假設我們有表“a”和“b”。其中 arr[i] 儲存長度為 i 的二進位制字串的數量，其中沒有連續的 1 且以 0 結尾。類似地，b 持有相同的內容，但數字以 1 結尾。當最後一個為 0 時，我們可以在它後面附加 0 或 1，但如果最後一個為 1，則只能附加 0。
讓我們瞭解一下獲取此想法的演算法。
演算法
noConsecutiveOnes(n) −
Begin define array a and b of size n a[0] := 1 b[0] := 1 for i in range 1 to n, do a[i] := a[i-1] + b[i - 1] b[i] := a[i - 1] done return a[n-1] + b[n-1] End
示例
#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
int a[n], b[n];
a[0] = 1;
b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
return a[n-1] + b[n-1];
}
int main() {
cout << noConsecutiveOnes(4) << endl;
}輸出
8
更新於: 20-Aug-2019
116 次瀏覽
廣告