資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 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
395 次瀏覽
