Các số từ 1 đến n bit không có số 1 liên tiếp trong biểu diễn nhị phân?

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 đó số bit là i và chứa các số 1 liên tiếp, thì 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

Thuật toán này lấy số lượng bit cho một số nhị phân. Đặt đầu vào là 4.

Đầu ra

Nó trả về số chuỗi nhị phân không có số 1 liên tiếp.

Đây là kết quả - 8. (Có 8 chuỗi nhị phân không có số 1 liên tiếp)

Thuật toán

countBinNums (n)

Input: n is the number of bits.
Output: Count how many numbers are present which have no consecutive 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 consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

Đầu ra

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