เราได้รับหลายบิต n เป็นอินพุตสำหรับลำดับไบนารี เป้าหมายที่นี่คือการค้นหาลำดับเลขฐานสองของความยาว 2n โดยที่ผลรวมของบิตครึ่งแรกและครึ่งหลังมีค่าเท่ากัน n บิตแรกและ n บิตถัดไปมีผลรวมเท่ากัน
เรามีลำดับเลขฐานสอง ดังนั้นทางเลือกเดียวที่จะใส่ตัวเลขในที่ใดก็ได้คือ 0 และ 1 สำหรับ n บิตในครึ่งแรกและครึ่งหลัง ไม่มี ของชุดค่าผสมที่เป็นไปได้คือ −
n บิตที่มีศูนย์ทั้งหมด (0 1's) nC0=1
n บิตกับ 1 1 ของ nC1
n บิตกับ 2 1 ของ nC2
.
.
n บิตกับ nCn ของ n 1
สำหรับ 2n บิต
-
ครึ่งแรกกับ 0 1 และครึ่งหลังกับ 0 1 ของ nC0 X nC0
-
ครึ่งแรกกับ 1 1 และครึ่งหลังกับ 1 1 ของ nC1 X nC1
-
ครึ่งแรกกับ 2 1 และครึ่งหลังกับ 2 1 ของ nC2 X nC2
-
......................
-
ครึ่งแรกกับ 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 จากสี่ 01 และ 10 มีผลรวม=1
อินพุต
n=2
ผลลัพธ์
Sequences with same sum of first and second half bits: 6
คำอธิบาย − เป็นไปได้ 2*2 =ลำดับ 4 บิต 0000001,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 ใช้เพื่อเก็บค่าเริ่มต้น =1 เนื่องจาก nC0 คือ 1
-
เริ่มต้น ans=0 ซึ่งจะนับลำดับดังกล่าวเป็นผลรวมของ nCi*nCi
-
เริ่มจาก i=0 ถึง n เพิ่ม nCi*nCi ให้กับ ans คำนวณแต่ละ nCi ตามสูตรด้านบน
-
หลังจากสิ้นสุด for loop ให้คืนค่าผลลัพธ์ที่แสดงเป็น '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
