Số nhị phân là số chỉ chứa hai tức là có một hoặc hai. Mọi số nhị phân đều là một dòng bit nhị phân và chúng tôi coi đây là một chuỗi nhị phân. đối với chuỗi này, chúng ta cần tìm số chuỗi nhị phân không chứa các chuỗi liên tiếp có N bit.
Ví dụ:đối với N - 5, các chuỗi nhị phân thỏa mãn các ràng buộc đã cho là 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
Một phương pháp là tạo tất cả các chuỗi chữ số N và chỉ in những chuỗi thỏa mãn các ràng buộc đã cho. Nhưng phương pháp này không hiệu quả khi hoạt động.
Phương pháp khác là sử dụng đệ quy. Tại mỗi thời điểm trong đệ quy, chúng ta thêm 0 và 1 vào số được tạo thành một phần và lặp lại với một chữ số nhỏ hơn. Bí quyết ở đây là chúng tôi thêm 1 và chỉ lặp lại nếu chữ số cuối cùng của số được tạo thành một phần là 0, Bằng cách đó, chúng tôi sẽ không bao giờ có bất kỳ số 1 liên tiếp nào trong chuỗi đầu ra.
Input: n = 5 Output: Number of 5-digit binary strings without any consecutive 1's are 13
Ví dụ
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0)
return 0;
if (n == 1) {
if (last_digit)
return 1;
else
return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any "
"consecutive 1's are " << countStrings(n, 0);
return 0;
}