連続する 1 のないバイナリ文字列の数を数えるプログラムを C/C++ で作成しますか?

ここで興味深い質問があります。値 n が与えられたとします。連続する 1 がない長さ n の文字列をすべて見つけなければなりません。 n = 2 の場合、数値は {00, 01, 10} となるため、出力は 3 になります。

動的プログラミングを使用してそれを解決できます。テーブル「a」と「b」があるとします。ここで、arr[i] には、連続する 1 がなく、0 で終わる長さ i のバイナリ文字列の数が格納されます。同様に、b も同じですが、1 で終わります。最後のものが 0 の場合は 0 または 1 を追加できますが、最後のものが 1 の場合は 0 のみを追加します。

このアイデアを理解するためのアルゴリズムを見てみましょう。

Algorithm

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

の中国語訳は次のとおりです:

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;
}

Output

リーリー

以上が連続する 1 のないバイナリ文字列の数を数えるプログラムを C/C++ で作成しますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。