首頁  >  文章  >  後端開發  >  在C/C++中寫一個程式來計算沒有連續1的二進位字串的數量?

在C/C++中寫一個程式來計算沒有連續1的二進位字串的數量?

WBOY
WBOY轉載
2023-08-25 22:05:13623瀏覽

在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

Example

的中文翻譯為:

範例

#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

以上是在C/C++中寫一個程式來計算沒有連續1的二進位字串的數量?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除