Chúng ta được cho các số nguyên N và K. Chúng ta có các chuỗi nhị phân độ dài N, chỉ chứa 0 và 1. Mục tiêu là tìm số lượng chuỗi độ dài N có K cặp bit 1 liền kề. Tức là, nếu N=3, K=2, thì đếm tất cả chuỗi nhị phân 3 chữ số có thể có 2 cặp bit 1 liền kề.
Ví dụ − 111, ở đây các bit 1 liền kề xuất hiện 2 lần (K lần).
Trong 011 và 110, các bit 1 liền kề chỉ xuất hiện 1 lần.
Chúng ta sẽ giải quyết bằng cách lưu trữ kết quả của các giá trị trước đó.
Sử dụng mảng 3 chiều count[x][y][z]. Trong đó x là N, y là K và z là chữ số cuối của chuỗi (0 hoặc 1).
- Với N=1, chuỗi sẽ là "0" và "1". Số cặp bit 1 liền kề = 0.
Vì vậy với mọi K. Nếu N=1, count=0.
count[1][K][0] = count[1][K][1] = 0.
- Khi chữ số cuối là 0, để số cặp bit 1 liền kề là K:
Tất cả chuỗi độ dài N-1 với K cặp bit 1 + thêm 0 ở cuối → độ dài mới = N. Nếu số cặp K là C thì thêm 0 ở cuối không thay đổi số lượng đó.
count[N][K][0] = count[N-1][K][0] + count[N-1][K][1]
- Khi chữ số cuối là 1, để số cặp bit 1 liền kề là K:
Tất cả chuỗi độ dài N-1 kết thúc bằng 0 với K cặp bit 1 + thêm 1 → độ dài mới = N, count[N-1][K][0]
Tất cả chuỗi độ dài N-1 kết thúc bằng 1 với K-1 cặp bit 1 + thêm 1 → độ dài mới = N, count[N-1][K-1][1]
count[N][K][1] = count[N-1][K][0] + count[N-1][K-1][1]
Tổng số chuỗi như vậy = count[N][K][0] + count[N][K][1]
Ví dụ
Đầu vào
N=4, K=2
Đầu ra
Số lượng chuỗi: 2
Giải thích − 1110, 0111 là các chuỗi duy nhất độ dài 4 mà các bit 1 liền kề xuất hiện 2 lần.
1110 - "11 10", sau đó "1 11 0" (tách để chỉ cặp bit 1 nào được đếm) 0111 - "0 11 1", sau đó "01 11". K=2, cặp bit 1 liền kề = 2 lần
Đầu vào
N=3, K=1
Đầu ra
Số lượng chuỗi: 2
Giải thích − 110, 011 là các chuỗi duy nhất độ dài 3 mà các bit 1 liền kề xuất hiện 1 lần. Trong 111, cặp bit 1 xuất hiện 2 lần.
Phương pháp sử dụng trong chương trình dưới đây
- Số nguyên N và K lưu độ dài chuỗi và số lần cặp bit 1 liền kề xuất hiện.
- Hàm stringcount(int n, int k) nhận n và k, trả về số chuỗi với K cặp bit 1 liền kề.
- Mảng count[i][j][0/1] lưu số chuỗi độ dài i với j cặp bit 1 liền kề kết thúc bằng 0 hoặc 1.
- Điều kiện khởi tạo: count[1][0][0] = 1; count[1][0][1] = 1;
- Bắt đầu từ chuỗi độ dài 2 (i=2) đến n. Với mỗi chuỗi kiểm tra số cặp K. j=0 đến k, từ số lượng trước. Cập nhật count[i][j][0] và count[i][j][1].
- Nếu j-1 >= 0, số cặp bit 1 liền kề > 1. Cập nhật số chuỗi kết thúc bằng 1: count[i][j][1] + count[i-1][j-1][1].
- Cuối cùng cộng count[n][k][0] và count[n][k][1]. Lưu làm kết quả.
- Trả về kết quả là số lượng mong muốn.
Ví dụ mã nguồn
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k) {
// số chuỗi độ dài=n và cặp bit 1 liền kề=k
int count[n + 1][k + 1][2] = {0};
// count[n][k][0] -- chuỗi độ dài=n, cặp bit 1=k, ký tự cuối là 0
// count[n][k][1] -- chuỗi độ dài=n, cặp bit 1=k, ký tự cuối là 1
// Nếu n = 1 và k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// số cặp bit 1 liền kề không thể vượt quá i-1
for (int j = 0; j <= k; j++) {
count[i][j][0] = count[i - 1][j][0] + count[i - 1][j][1];
count[i][j][1] = count[i - 1][j][0];
if (j - 1 >= 0)
count[i][j][1] = count[i][j][1] + count[i - 1][j - 1][1];
}
}
int result = count[n][k][0] + count[n][k][1];
return result;
}
int main() {
int N = 6, K = 3;
cout << "Chuỗi độ dài 6 và 3 cặp bit 1 liền kề: " << stringcount(N, K);
return 0;
}
Kết quả
Chuỗi độ dài 6 và 3 cặp bit 1 liền kề: 7