C/C++程式：計算沒有連續1的二進位字串的數量？

二進位數是只包含兩個數字的數，即只有0和1。每個二進制數都是由二進制位組成的流，我們將其視為二進位字串。對於這個字串，我們需要找到不包含連續1的長度為N的二進位字串的數量。

例如，對於N=5，滿足給定條件的二進位字串為00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10101。

一種方法是產生所有N位元字串，並僅列印滿足給定條件的字串。但是，當涉及大規模運算時，這種方法效率不高。

另一種方法是使用遞歸。在遞歸的每一步中，我們將0和1附加到部分形成的數字上，並以少一個數字的形式進行遞歸。關鍵在於，只有當部分形成的數字的最後一位是0時，我們才附加1​​並進行遞歸。這樣，輸出字串中就不會有連續的1。

Input: n = 5
Output: Number of 5-digit binary strings without any consecutive 1's are 13

範例

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
   if (n == 0)
      return 0;
   if (n == 1) {
      if (last_digit)
         return 1;
      else
         return 2;
   }
   if (last_digit == 0)
      return countStrings(n - 1, 0) + countStrings(n - 1, 1);
   else
      return countStrings(n - 1, 0);
}
int main() {
   int n = 5;
   cout << "Number of " << n << "-digit binary strings without any "
   "consecutive 1&#39;s are " << countStrings(n, 0);
   return 0;
}

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