使用 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