1が連続しないバイナリ文字列のカウント数とは何ですか?

連続する 1 のないバイナリ文字列を数える概念を説明する例を考えてみましょう。

例

連続する 1 を含まない、長さ 3 のバイナリ文字列の数を数えたいとします。バイナリ文字列は、0 と 1 だけで構成される文字列です。

長さ 3 の可能なバイナリ文字列は、000、001、010、011、100、101、110、および 111 です。

ただし、カウントする必要があるのは、連続する 1 を持たないバイナリ文字列だけです。したがって、文字列 011、101、および 111 をカウントから除外する必要があります。

残りのバイナリ文字列を分析してみましょう。

• 000: 連続する 1 がないため、これは有効な文字列です。

• 001: 連続する 1 がないため、これは有効な文字列です。

• 010: 連続する 1 がないため、これは有効な文字列です。

• 100: 連続する 1 がないため、これは有効な文字列です。

• 110: 1 が連続しているため、これは無効な文字列です。

上記の分析から、連続する 1 のない長さ 3 の有効なバイナリ文字列が 4 つあることがわかります。

連続 1 のないバイナリ文字列の数を数える PHP プログラム

方法 1 - 動的プログラミングを使用する

例

出力

Number of binary strings without consecutive 1's: 13

コードの説明

この PHP コードは、動的プログラミングを使用して、連続する 1 を含まない長さ $n のバイナリ文字列の数を計算する countBinaryStrings という関数を定義します。これは、基本ケース $dp[0] = 1 および $dp[1] = 2 で配列 $dp を初期化し、次の文字列のカウントを表します。長さはそれぞれ 0 と 1。次に、ループを使用して、長さ $i - 1 と $i - のカウントを合計することで、長さ 2 から $n までの残りのカウントを埋めます。 2. 最後に、長さ $n のカウントを返し、それを出力します。この特定の例では、コードは長さ 5 で連続 1 のないバイナリ文字列の数を計算し、結果を表示します。

方法 2

出力

Number of binary strings without consecutive 1's: 13

コードの説明

この PHP コードは、2 つの連続する 1 を含まない、長さ $n の個別のバイナリ文字列の数を計算します。カウントを保存するために、$a と $b の 2 つの配列を定義します。基本ケースは $a[0] = $b[0] = 1 として設定されます。次に、ループを使用して長さ 1 から $ のカウントが計算されます。 n-1。長さ $i のカウントは、配列 $a からの長さ $i-1 のカウントと長さ $[ のカウントを合計することによって取得されます。 &&&]i-1 配列 $b から。さらに、配列 $b の長さ $i のカウントは、配列 $ の長さ $i-1 のカウントから取得されます。 ａ．最後に、コードは、配列 $a からの長さ $n-1 のカウントと、配列 [ からの長さ $n-1 のカウントの合計を返します。 &&&]$b、連続する 1 を含まないバイナリ文字列の合計数を表します。この特定の例では、コードは長さ 5 のカウントを計算し、結果を表示します。 結論

結論として、最初の方法は動的プログラミングを利用し、基本ケースで配列を初期化し、より長い長さのカウントを繰り返し計算します。前の 2 つの長さのカウントを合計することで結果を効率的に計算します。 2 番目の方法では、より単純なアプローチを採用しており、2 つの配列を使用してカウントを保存し、以前の長さからのカウントに基づいてそれらを繰り返し更新します。 2 つの配列を個別に合計する必要なく、合計数を直接計算します。どちらの方法でも、連続 1 がないバイナリ文字列の正確なカウントが提供されます。どちらの方法を選択するかは、特定の要件とパフォーマンスの考慮事項に依存する場合があります。