Python
 Computer >> コンピューター >  >> プログラミング >> Python

連続する1’のないバイナリ文字列の数をカウントするPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −正の整数Nが与えられているので、文字列に連続する1が存在しないように、長さNで使用可能なすべての可能な個別のバイナリ文字列をカウントする必要があります。

次に、以下の実装のソリューションを見てみましょう-

例

# count the number of strings
def countStrings(n):
   a=[0 for i in range(n)]
   b=[0 for i in range(n)]
   a[0] = b[0] = 1
   for i in range(1,n):
      a[i] = a[i-1] + b[i-1]
      b[i] = a[i-1]
   return a[n-1] + b[n-1]
# main
n=5
print("The number of strings: ",countStrings(n))

出力

The number of strings: 13

連続する1’のないバイナリ文字列の数をカウントするPythonプログラム

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、連続する1’なしでバイナリ文字列の数をカウントするPythonプログラムを作成する方法について学びました。


  1. PythonでnノードのBSTの数をカウントするプログラム

    n個の異なるノードがあるとします。すべてが異なります。二分探索木を形成するためにそれらを配置できる方法の数を見つける必要があります。二分探索木で知っているように、左側のサブツリーは常に小さい値を保持し、右側のサブツリーは大きい値を保持します。 これを解決するために、カタラン数を見つけます。カタラン数C（n）は、n個の異なるキーを持つ二分探索木を表します。式は次のようになります $$ C（n）=\ frac {（2n）！} {（n + 1）！\ times n！} $$ したがって、入力がn =3の場合、出力は5になります。 これを解決するには、次の手順に従います- 関数ncr

  2. 2進数にK個の連続した1があるかどうかをチェックするPythonプログラム？

    まず、1と0を組み合わせたユーザー入力文字列を取得します。次に、1を使用して新しい文字列を作成し、p個の連続する1が存在するかどうかを確認します。存在する場合はFOUNDを表示し、存在しない場合はNOTFOUNDを表示します。 例 Binary number ::1111001111 Enter consecutive 1’s :3 Consecutive 1s is Found アルゴリズム Step 1: input a string with the combination of 1’s, it’s stored in the variable X and 0’s and p is