C/C++ プログラム: 連続する 1 のないバイナリ文字列の数をカウントしますか?

2 進数とは、2 桁のみ、つまり 0 と 1 のみを含む数値です。それぞれの 2 進数は 2 進ビットのストリームであり、私たちはこれを 2 進文字列とみなします。この文字列については、連続する 1 を含まない長さ N のバイナリ文字列の数を見つける必要があります。

たとえば、N=5 の場合、指定された条件を満たすバイナリ文字列は、00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101 です。

1 つの方法は、N 桁の文字列をすべて生成し、指定された条件を満たす文字列のみを出力することです。ただし、このアプローチは大規模な操作では効率的ではありません。

もう 1 つの方法は、再帰を使用することです。再帰の各ステップで、部分的に形成された数値に 0 と 1 を追加し、数値を 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 中国語 Web サイトの他の関連記事を参照してください。