Chúng ta được cho với các số nguyên N và K. Chúng ta có các chuỗi nhị phân có độ dài N, chứa 0’s và 1’sonly. Mục đích là để tìm số lượng các chuỗi có độ dài N như vậy có K 1’s liên tiếp. Tức là nếu N =3 và K =2, thì hãy đếm tất cả các chuỗi nhị phân gồm 3 chữ số có thể có 2 chữ số 1 liên tiếp.
Ví dụ - 111, ở đây các số 1 liền kề xuất hiện hai lần (K lần).
Trong năm 011 và 110 các số 1 liền kề chỉ xuất hiện một lần.
Chúng tôi sẽ giải quyết vấn đề này bằng cách lưu trữ kết quả của các giá trị trước đó.
Lấy số mảng 3D [x] [y] [z]. Trong đó x là N, y là K và z là chữ số cuối cùng của chuỗi (0 hoặc 1)
- Đối với N =1, các chuỗi sẽ là “0” và “1”. Tổng số 1 của liền kề =0.
Vì vậy, với bất kỳ K. Nếu N =1, đếm =0.
count [1] [K] [0] =count [1] [K] [1] =0.
- Khi chữ số cuối cùng là 0, để tính số 1 liền kề là K
Tất cả các chữ số có độ dài N-1 với K hàng đơn vị + số 0 cuối cùng → độ dài mới =N
Nếu số K của 1 liền kề là C thì việc thêm 0 vào cuối sẽ không thay đổi số đó.
count [N] [K] [0] =count [N-1] [K] [0] + count [N-1] [K] [1]
- Khi chữ số cuối cùng là 1, để tính số 1 liền kề là K
Tất cả các chữ số có độ dài N-1 kết thúc bằng 0 với K chữ số 1 + chữ số 1 cuối cùng → độ dài mới =N,
đếm [N-1] [K] [0]
Tất cả các chữ số có độ dài N-1 kết thúc bằng 1 với K-1 chữ số + 1 cuối cùng → độ dài mới =N,
đếm [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]
Đầu vào
N=4, K=2
Đầu ra
Count of strings: 2
Giải thích - 1110, 0111 là các chuỗi duy nhất có độ dài 4 trong đó các chuỗi 1 liền kề chỉ xuất hiện hai lần.
1110- “11 10”, then “1 11 0” ( splitting to show which adjacent 1’s are counted ) 0111- “0 11 1”, then “01 11”. K=2, adjacent 1’s= 2 times
Đầu vào
N=3, K=1
Đầu ra
Count of strings: 2
Giải thích - 110, 011. là các chuỗi duy nhất có độ dài 3 ở vị trí các chuỗi 1 liền kề xuất hiện một lần.
Trong 111 số 1 liền kề xuất hiện hai lần.
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 N và K lưu trữ độ dài của chuỗi và không. số lần các số 1 liền kề xuất hiện trong mỗi.
-
Hàm stringcount (int n, int k) nhận n và k làm tham số và trả về số chuỗi với K nhân với 1’s liền kề.
-
Số lượng mảng [i] [j] [0/1] được sử dụng để lưu trữ số lượng các chuỗi có độ dài i với j liền kề 1 đang gửi với 0 hoặc 1.
-
Điều kiện ban đầu là count [1] [0] [0] =1; đếm [1] [0] [1] =1;
-
Bây giờ hãy bắt đầu từ 2 chuỗi độ dài (i =2) đến độ dài n. Đối với mỗi chuỗi như vậy, số lần kiểm tra 1’s liền kề. j =0; j <=k, từ các lần đếm trước. Cập nhật số lượng hiện tại [i] [j] [0] và số lượng [i] [j] [1].
-
Nếu j-1> =0, số lượng các 1 liền kề lớn hơn 1. Sau đó cập nhật số lượng các chuỗi kết thúc bằng 1 dưới dạng đếm [i] [j] [1] + count [i - 1] [j - 1] [1 ];
-
Ở cuối, thêm số đếm [n] [k] [0] và số lượng [n] [k] [1]. Kết quả là lưu trữ nó.
- Trả về kết quả như số lượng mong muốn.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int stringcount(int n, int k){
//count of strings with length=n and adajcent 1's=k
int count[n + 1][k + 1][2]={0};
//count[n][k][0] -- strings with length=n and adajcent 1's=k last character is 0
//count[n][k][1] -- strings with length=n and adajcent 1's=k last character is 1
// If n = 1 and k = 0.
count[1][0][0] = 1;
count[1][0][1] = 1;
for (int i = 2; i <= n; i++) {
// number of adjacent 1's can not exceed 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 <<"Strings of length 6 and 3 adjacent 1's in each :"<< stringcount(N,K);
return 0;
} Đầu ra
Strings of length 6 and 3 adjacent 1's in each :7