Computer >> Máy Tính >  >> Lập trình >> C ++

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

Chúng tôi được cung cấp một số bit n làm đầu vào cho một chuỗi nhị phân. Mục tiêu ở đây là tìm chuỗi nhị phân có độ dài 2n sao cho tổng các bit đầu tiên và nửa thứ hai của nó bằng nhau. N bit đầu tiên và n bit tiếp theo có tổng bằng nhau.

Chúng ta có một chuỗi nhị phân nên sự lựa chọn duy nhất để đặt các chữ số ở bất kỳ vị trí nào là 0 và 1. Đối với n bit ở nửa đầu và nửa sau, không. trong số các kết hợp có thể có là -

n bit với tất cả các số không (0 1’s) nC0 =1

n bit với 1 1 là nC1

n bit với 2 1 là nC2

.

.

n bit với n 1 là nCn

Đối với 2n bit

  • Hiệp một với 0 1’s và nửa sau với 0 1’s nC0 X nC0

  • Nửa đầu với 1 1 và nửa sau với 1 1 là nC1 X nC1

  • Nửa đầu với 2 1’s và nửa sau với 2 1’s nC2 X nC2

  • ..............

  • Nửa đầu với n 1 và nửa sau với n 1 là nCn X nCn

Tổng các kết hợp như vậy =nC0 * nC0 + nC1 * nC1 + ....... + nCn * nCn

=(nC0) 2+ (nC1) 2 + ........... + (nCn) 2

Đầu vào 

n=1

Đầu ra 

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

Giải thích - Có thể có 2 * 1 =2 dãy bit 00,01,10,11 Trong bốn số 01 và 10 này có tổng =1

Đầu vào 

n=2

Đầu ra 

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

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

Trong số các chuỗi này có tổng của 2 bit đầu tiên và 2 bit cuối cùng là như nhau -

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Số nguyên ‘bit’ lưu trữ số.

  • Hàm findSeq (int n) nhận n làm đầu vào và trả về số lượng các chuỗi có tổng trên 2n bit đầu tiên và nửa thứ hai bằng nhau.

  • Biến nCi được sử dụng để lưu trữ giá trị ban đầu =1 vì nC0 là 1.

  • Khởi tạo ans =0, sẽ đếm các chuỗi như tổng của nCi * nCi.

  • Bắt đầu từ i =0 đến n, thêm nCi * nCi vào ans, tính từng nCi như công thức trên.

  • Sau khi kết thúc vòng lặp for, trả về kết quả ở dạng "ans" dưới dạng số đếm.

Ví dụ 

#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;
}

Đầu ra 

Count of binary sequences such that sum of first and second half bits is same: 6