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

Trong bài toán này, chúng ta phải tìm một số số nhị phân không có số 1 liên tiếp. Trong một chuỗi nhị phân 3 bit, có ba số nhị phân 011, 110, 111 có các số 1 liên tiếp và năm số có các số 1 không liên tiếp. Vì vậy, sau khi áp dụng thuật toán này cho các 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 bất kỳ số 1 liên tiếp nào và b [i] là tập hợp số nhị phân, trong đó một số bit là I và chứa các số 1 liên tiếp , sau đó có các quan hệ lặp lại như:

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

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

Input:
This algorithm takes number of bits for a binary number. Let the input is 4.
Output:
It returns the number of binary strings which have no consecutive 1’s.
Here the result is: 8. (There are 8 binary strings which has no consecutive 1’s)

Thuật toán

countBinNums(n)

Đầu vào: n là số bit.
Đầu ra - Đếm xem có bao nhiêu số có mặt không liên tiếp 1.

Begin
   define lists with strings ending with 0 and ending with 1
   endWithZero[0] := 1
   endWithOne[0] := 1

   for i := 1 to n-1, do
      endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
      endWithOne[i] := endWithZero[i-1]
   done
   return endWithZero[n-1] + endWithOne[n-1]
End

Ví dụ

#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