C++で前半ビットと後半ビットの合計が同じである偶数の長さのバイナリシーケンスをカウントします

バイナリシーケンスの入力として、いくつかのビットnが与えられます。ここでの目標は、前半ビットと後半ビットの合計が等しくなるような長さ2nのバイナリシーケンスを見つけることです。最初のnビットと次のnビットの合計は同じです。

バイナリシーケンスがあるため、任意の場所に数字を配置する唯一の選択肢は0と1です。前半と後半のnビットの場合、いいえ。可能な組み合わせは次のとおりです-

すべてゼロのnビット（0 1）nC0 =1

11のnC1を含むnビット

21のnC2を含むnビット

。

。

n1のnCnを含むnビット

2nビットの場合

• 前半は01で、後半は01でnC0X nC0

• 前半は11で、後半は11でnC1X nC1

• 前半は21で、後半は21でnC2X nC2

• ..............

• 前半はn1で、後半はn1でnCnX nCn

そのような組み合わせの合計=nC0* nC0 + nC1 * nC1 + ....... + nCn * nCn

=（nC0）2+（nC1）2 + ........... +（nCn）2

入力

n=1

出力

Sequences with same sum of first and second half bits: 2

説明 −可能な2 * 1=2ビットシーケンス00,01,10,11これらの4つの01と10のうちsum=1

入力

n=2

出力

Sequences with same sum of first and second half bits: 6

説明 −可能な2 * 2=4ビットシーケンス0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111

最初の2ビットと最後の2ビットの合計が同じであるこれらのシーケンスのうち-

0000,0101,0110,1001,1010,1111、合計=6

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

• 整数の「ビット」は数値を格納します。

• 関数findSeq（int n）は、入力としてnを受け取り、前半と後半の2nビットの合計が等しいシーケンスの数を返します。

• 変数nCiは、nC0が1であるため、初期値=1を格納するために使用されます。

• ans =0を初期化します。これにより、nCi*nCiの合計などのシーケンスがカウントされます。

• i =0からnまで、ansにnCi * nCiを追加し、上記の式のように各nCiを計算します。

• forループの終了後、「ans」に存在する結果をカウントとして返します。

例

#include<iostream>
using namespace std;
// Returns the count of even length sequences
int findSeq(int n){
   int nCi=1; //nC0=1
   int ans = 1;
   for (int i = 1; i<=n ; i++){
      //nCi=(nCi-1)*(nCi/nCi-1)
      // nCi/nC(i-1) = (n+1-i)/i;
      nCi = (nCi * (n+1-i))/i;
      ans += nCi*nCi;
   }
   return ans;
}
int main(){
   int bits = 2;
   cout << "Count of binary sequences such that sum of first and second half bits is
   same: "<<findSeq(bits);
   return 0;
}

出力

Count of binary sequences such that sum of first and second half bits is same: 6