数据结构
网络
关系数据库管理系统 (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 次浏览
