Chương trình C/C++ đếm chuỗi nhị phân không có 1 liên tiếp

Chuỗi nhị phân độ dài N không chứa hai bit 1 liên tiếp. Ví dụ N=5: 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101 (13 chuỗi).

Sinh tất cả chuỗi rồi lọc không hiệu quả. Dùng đệ quy: tại mỗi bước thêm 0 hoặc 1 vào chuỗi đang xây. Chỉ thêm 1 nếu chữ số cuối là 0, đảm bảo không có 1 liên tiếp.

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