นับลำดับไบนารีความยาวคู่ที่ครึ่งหน้าและครึ่งหลังมีผลรวมบิตเท่ากันใน C++

เราได้รับจำนวนบิต n สำหรับลำดับไบนารี เป้าหมายคือหาจำนวนลำดับไบนารีความยาว 2n ที่ผลรวมบิตครึ่งแรกและครึ่งหลังเท่ากัน (n บิตแรกและ n บิตถัดไปมีผลรวมเท่ากัน)

สำหรับ n บิต จำนวนวิธีที่มี 1 จำนวน k ตัว คือ nCk สำหรับ 2n บิต ต้องการครึ่งแรกมี k ตัว 1 และครึ่งหลังก็ k ตัว 1 จำนวนวิธี = nCk × nCk

ผลรวมทั้งหมด = Σ (nCk)² สำหรับ k=0 ถึง n

อินพุต

n = 1

เอาต์พุต

Sequences with same sum of first and second half bits: 2

คำอธิบาย − 2-bit sequences: 00,01,10,11 มี 01 และ 10 ผลรวม = 1

อินพุต

n = 2

เอาต์พุต

Sequences with same sum of first and second half bits: 6

คำอธิบาย − 4-bit sequences ทั้งหมด 16 แบบ ที่มีผลรวม 2 บิตแรก = 2 บิตหลัง: 0000,0101,0110,1001,1010,1111 รวม 6

วิธีการที่ใช้ในโปรแกรมด้านล่าง

• ตัวแปร bits เก็บ n
• ฟังก์ชัน findSeq(int n) คืนค่าจำนวนลำดับที่ตรงเงื่อนไข
• nCi เริ่มต้น = 1 (nC0), ans = 1
• ลูป i=1..n: nCi = nCi * (n+1-i) / i, ans += nCi * nCi
• คืนค่า ans

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int findSeq(int n) {
    int nCi = 1;
    int ans = 1;
    for (int i = 1; i <= n; 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