Đếm chuỗi nhị phân không có 1 liên tiếp

Trong bài toán này, ta phải tìm các số nhị phân không có các số 1 liên tiếp. Trong chuỗi nhị phân 3-bit, có ba số nhị phân 011, 110, 111, có 1 liên tiếp, và năm số không có 1 liên tiếp. Vậy sau khi áp dụng thuật toán này cho số 3-bit, câu trả lời sẽ là 5.

Nếu a[i] là tập hợp các số nhị phân, có số bit là i, và không chứa 1 liên tiếp nào, và b[i] là tập hợp số nhị phân, có số bit là i, và chứa 1 liên tiếp, thì có các quan hệ truy hồi như sau:

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

Đầu vào và Đầu ra

Đầu vào: Thuật toán này nhận số bit cho một số nhị phân. Giả sử đầu vào là 4.
Đầu ra: Trả về số chuỗi nhị phân không có 1 liên tiếp. Ở đây kết quả là: 8. (Có 8 chuỗi nhị phân không có 1 liên tiếp)

Thuật toán

countBinNums(n)
Đầu vào: n là số bit.
Đầu ra: Đếm bao nhiêu số có mặt mà không có 1 liên tiếp.
Bắt đầu
  định nghĩa danh sách chuỗi kết thúc bằng 0 và kết thúc bằng 1
  endWithZero[0] := 1
  endWithOne[0] := 1
  với i := 1 đến n-1, làm
    endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
    endWithOne[i] := endWithZero[i-1]
  kết thúc
  trả về endWithZero[n-1] + endWithOne[n-1]
Kết thúc

Ví dụ (C++)

#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 << "Enter number of bits: "; cin >> n;
  cout << "Number of binary numbers without consecitive 1's: " << countBinNums(n) << endl;
  return 0;
}

Đầu ra

Enter number of bits: 4
Number of binary numbers without consecitive 1's: 8