이진 시퀀스에 대한 입력으로 여러 비트 n이 제공됩니다. 여기서 목표는 길이가 2n인 이진 시퀀스를 찾는 것이므로 첫 번째 및 두 번째 하프 비트의 합이 동일합니다. 처음 n비트와 다음 n비트는 합이 같습니다.
우리는 이진 시퀀스를 가지고 있으므로 임의의 위치에 숫자를 넣을 수 있는 유일한 선택은 0과 1입니다. 전반부와 후반부의 n 비트에 대해 아니오. 가능한 조합의 -
모두 0인 n 비트(0 1) nC0=1
1 1의 nC1이 있는 n비트
2 1의 nC2가 있는 n 비트
.
.
n 1의 nCn이 있는 n 비트
2n 비트의 경우
-
전반전 0 1, 후반 0 1 nC0 X nC0
-
전반전 1 1, 후반 1 1 nC1 X nC1
-
전반전 2 1, 후반 2 1 nC2 X nC2
-
..............
-
전반전 n 1 및 후반 n 1 nCn X 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 중 합계=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을 저장하는 데 사용됩니다.
-
nCi*nCi의 합과 같은 시퀀스를 계산하는 ans=0을 초기화합니다.
-
i=0부터 n까지 ans에 nCi*nCi를 추가하고 위의 공식과 같이 각 nCi를 계산합니다.
-
for 루프가 끝나면 'ans'에 있는 결과를 count로 반환합니다.
예시
#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