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

連続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 - 動的プログラミングを使用する

例

リーリー

出力

リーリー

コードの説明

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

方法 2

リーリー

出力

リーリー

コードの説明

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

結論

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

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