Đếm chuỗi nhị phân độ dài chẵn có tổng nửa đầu và nửa sau bằng nhau trong C++

Chúng ta được cho số bit n làm đầu vào cho chuỗi nhị phân. Mục tiêu là tìm chuỗi nhị phân độ dài 2n sao cho tổng bit nửa đầu và nửa sau bằng nhau. n bit đầu và n bit tiếp theo có tổng giống nhau.

Chúng ta có chuỗi nhị phân nên lựa chọn duy nhất đặt chữ số tại bất kỳ vị trí nào là 0 và 1. Với n bit nửa đầu và nửa sau, số tổ hợp có thể:

n bit toàn 0 (0 bit 1) nC0 = 1
n bit có 1 bit 1: nC1
n bit có 2 bit 1: nC2
...
n bit có n bit 1: nCn

Cho 2n bit:

Nửa đầu 0 bit 1 và nửa sau 0 bit 1: nC0 x nC0
Nửa đầu 1 bit 1 và nửa sau 1 bit 1: nC1 x nC1
Nửa đầu 2 bit 1 và nửa sau 2 bit 1: nC2 x nC2
..............
Nửa đầu n bit 1 và nửa sau n bit 1: nCn x nCn

Tổng tổ hợp như vậy = nC0*nC0 + nC1*nC1 + ... + nCn*nCn = (nC0)² + (nC1)² + ... + (nCn)²

Ví dụ

Đầu vào

n = 1

Đầu ra

Chuỗi có tổng nửa đầu và nửa sau bằng nhau: 2

Giải thích − Chuỗi 2*1=2 bit có thể: 00, 01, 10, 11. Trong 4 chuỗi này, 01 và 10 có tổng = 1.

Đầu vào

n = 2

Đầu ra

Chuỗi có tổng nửa đầu và nửa sau bằng nhau: 6

Giải thích − Chuỗi 2*2=4 bit có thể: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

Trong đó chuỗi có tổng 2 bit đầu và 2 bit cuối bằng nhau:

0000, 0101, 0110, 1001, 1010, 1111, tổng = 6.

Phương pháp sử dụng trong chương trình dưới đây

Số nguyên 'bits' lưu số.
Hàm findSeq(int n) nhận n, trả về số chuỗi với tổng nửa đầu và nửa sau 2n bit bằng nhau.
Biến nCi lưu giá trị ban đầu = 1 vì nC0 = 1.
Khởi tạo ans = 0, sẽ đếm các chuỗi như tổng nCi*nCi.
Bắt đầu từ i=0 đến n cộng nCi*nCi vào ans, tính mỗi nCi bằng công thức trên.
Sau vòng for trả về kết quả trong 'ans' là số lượng.

Ví dụ mã nguồn

#include <iostream> 
using namespace std; 

// Trả về số chuỗi độ dài chẵn
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 << "Số chuỗi nhị phân mà tổng nửa đầu và nửa sau bằng nhau: " 
         << findSeq(bits); 
    return 0; 
}

Kết quả

Số chuỗi nhị phân mà tổng nửa đầu và nửa sau bằng nhau: 6