C++で隣接する2つのセットビットにk回出現するバイナリ文字列をカウントします

整数NとKが与えられます。0と1のみを含む長さNのバイナリ文字列があります。目標は、K個の連続した1を持つ長さNのそのような文字列の数を見つけることです。つまり、N =3、K =2の場合、2つの連続する1を持つ可能性のあるすべての3桁のバイナリ文字列をカウントします。

例 − 111、ここでは隣接する1が2回表示されます（K回）。

011と110では、隣接する1が1回だけ出現しました。

以前の値の結果を保存することでこれを解決します。

3D配列カウント[x][y][z]を取得します。ここで、xはN、yはK、zは文字列の最後の桁（0または1）

• N =1の場合、文字列は「0」と「1」になります。隣接する1の数=0。

したがって、任意のKに対して。N=1の場合、カウント=0。

count [1] [K] [0] =count [1] [K][1]=0。

• 最後の桁が0の場合、隣接する1をKとし​​てカウントします

長さN-1のすべての桁とK個+最後の0→新しい長さ=N

隣接する1のKの数がCの場合、最後に0を追加しても、その数は変わりません。

count [N] [K] [0] =count [N-1] [K] [0] + count [N-1] [K] [1]

• 最後の桁が1の場合、隣接する1をKとし​​てカウントします

長さN-1のすべての桁が0で終わり、K個+最後の1→新しい長さ=N、

カウント[N-1][K][0]

長さN-1のすべての数字が1で終わり、K-1のもの+最後の1→新しい長さ=N、

カウント[N-1][K-1][1]

count [N] [K] [1] =count [N-1] [K] [0] + count [N-1] [K-1] [1]

そのような文字列の合計=count[N] [K] [0] + count [N] [K] [1]

入力

N=4, K=2

出力

Count of strings: 2

説明 − 1110、0111は、隣接する1が2回だけ表示される長さ4の唯一の文字列です。

1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted )
0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times

入力

N=3, K=1

出力

Count of strings: 2

説明 − 110、011。は、隣接する1が1回出現する長さ3の唯一の文字列です。

111では、隣接する1が2回表示されます。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数NとKは、文字列の長さを格納します。隣接する1がそれぞれに表示される回数。

• 関数stringcount（int n、int k）は、パラメーターとしてnとkを取り、隣接する1のK倍の文字列の数を返します。

• 配列count[i][j] [0/1]は、長さiの文字列の数を格納するために使用されます。jは1に隣接し、0または1で送信されます。

• 初期条件はcount[1][0] [0]=1です。 count [1] [0] [1] =1;

• ここで、2つの長さの文字列（i =2）からnの長さまで開始します。そのような文字列ごとに、1に隣接するK回のカウントを確認します。 j =0; j <=k、以前のカウントから。現在のカウント[i][j][0]とカウント[i][j][1]を更新します。

• j-1> =0の場合、隣接する1の数は1より大きくなります。次に、1で終わる文字列の数をcount [i] [j] [1] + count [i-1][j-1][1として更新します。 ];

• 最後に、count [n][k][0]とcount[n][k][1]を追加します。結果として保存します。

• 必要な数として結果を返します。

例

#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
   //count of strings with length=n and adajcent 1's=k
   int count[n + 1][k + 1][2]={0};
   //count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
   //count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
   // If n = 1 and k = 0.
   count[1][0][0] = 1;
   count[1][0][1] = 1;
   for (int i = 2; i <= n; i++) {
      // number of adjacent 1's can not exceed i-1
      for (int j = 0; j <= k; j++) {
         count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
         count[i][j][1] = count[i - 1][j][0];
      if (j - 1 >= 0)
         count[i][j][1] =count[i][j][1] + count[i - 1][j - 1][1];
      }
   }
   int result=count[n][k][0]+count[n][k][1];
   return result;
}
int main(){
   int N = 6, K = 3;
   cout <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
   return 0;
}

出力

Strings of length 6 and 3 adjacent 1's in each :7