Đếm số nhị phân 1 đến n bit không có 1 liên tiếp

Bài toán: Tìm số lượng chuỗi nhị phân n-bit không chứa hai bit 1 liên tiếp. Ví dụ 3-bit: có 3 chuỗi có 1 liên tiếp (011, 110, 111), 5 chuỗi không có.

Gọi a[i] là số chuỗi i-bit không có 1 liên tiếp, b[i] là số chuỗi i-bit có 1 liên tiếp. Công thức truy hồi:

a[i] := a[i-1] + b[i-1]
b[i] := a[i-1]

Đầu vào

Số bit n (ví dụ n=4)

Đầu ra

Số chuỗi nhị phân không có 1 liên tiếp. Với n=4 kết quả là 8.

Thuật toán countBinNums(n)

Input: n số bit. Output: Số chuỗi không có 1 liên tiếp.
Begin
    endWithZero[0] := 1
    endWithOne[0] := 1
    for i := 1 to n-1:
        endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
        endWithOne[i] := endWithZero[i-1]
    done
    return endWithZero[n-1] + endWithOne[n-1]
End

Ví dụ code

#include <iostream>
using namespace std;

int countBinNums(int n) {
    int endWithZero[n], endWithOne[n];
    endWithZero[0] = endWithOne[0] = 1;
    for (int i = 1; i < n; i++) {
        endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
        endWithOne[i] = endWithZero[i-1];
    }
    return endWithZero[n-1] + endWithOne[n-1];
}

int main() {
    int n;
    cout << "Nhap so bit: "; cin >> n;
    cout << "So chuoi nhi phan khong co 1 lien tiep: " << countBinNums(n) << endl;
    return 0;
}

Kết quả

Nhap so bit: 4
So chuoi nhi phan khong co 1 lien tiep: 8