使用 C++ 統計具有相同首尾半段位數和的偶數長度二進位制序列


給定一個二進位制序列的位數 n 作為輸入。目標是找到長度為 2n 的二進位制序列,使其前半部分和後半部分的位數之和相等。前 n 位和後 n 位的和相同。

我們有一個二進位制序列,因此在任何位置放置數字的唯一選擇是 0 和 1。對於前半部分和後半部分的 n 位,可能的組合數為:

n 位全為零 (0 個 1) nC0 = 1

n 位有 1 個 1 nC1

n 位有 2 個 1 nC2

.

.

n 位有 n 個 1 nCn

對於 2n 位:

  • 前半部分有 0 個 1,後半部分有 0 個 1 nC0 × nC0

  • 前半部分有 1 個 1,後半部分有 1 個 1 nC1 × nC1

  • 前半部分有 2 個 1,後半部分有 2 個 1 nC2 × nC2

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

  • 前半部分有 n 個 1,後半部分有 n 個 1 nCn × nCn

此類組合總數 = nC0*nC0 + nC1*nC1+.......+nCn*nCn

=(nC0)²+(nC1)²+...........+(nCn)²

輸入

n=1

輸出

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

說明 - 可能的 2*1=2 位序列 00,01,10,11,其中 01 和 10 的和為 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,1010,1001,0110,1111,總共 6 個

下面程式中使用的演算法如下:

  • 整數 `bits` 儲存數字。

  • 函式 `findSeq(int n)` 以 n 為輸入,返回具有上述前半部分和後半部分 2n 位之和相等的序列計數。

  • 變數 `nCi` 用於儲存初始值 1,因為 nC0 為 1。

  • 初始化 ans=0,它將計算此類序列的和 nCi*nCi。

  • 從 i=0 到 n,將 nCi*nCi 加到 ans 中,根據上述公式計算每個 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

更新於:2020年7月28日

395 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告