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

Ở đây chúng ta sẽ thấy một vấn đề thú vị. Giả sử một giá trị của n được cho trước. Chúng ta phải tìm tất cả các chuỗi có độ dài n, sao cho không có các số 1 liên tiếp. Nếu n =2, thì các số là {00, 01, 10}, Vậy đầu ra là 3.

Chúng tôi có thể giải quyết nó bằng cách sử dụng lập trình động. Giả sử chúng ta có một bảng ‘a’ và ‘b’. Trong đó arr [i] đang lưu trữ số lượng các chuỗi nhị phân có độ dài i, trong đó không có số 1 liên tiếp nào và kết thúc bằng 0. Tương tự, b đang giữ các số giống nhau nhưng các số kết thúc bằng 1. Chúng ta có thể thêm 0 hoặc 1 vào vị trí cuối cùng là 0, nhưng chỉ thêm 0 nếu giá trị cuối cùng là 1.

Hãy để chúng tôi xem thuật toán để có được ý tưởng này.

Thuật toán

noConsariesOnes (n) -

Begin
   define array a and b of size n
   a[0] := 1
   b[0] := 1
   for i in range 1 to n, do
      a[i] := a[i-1] + b[i - 1]
      b[i] := a[i - 1]
   done
   return a[n-1] + b[n-1]
End

Ví dụ

#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
   int a[n], b[n];
   a[0] = 1;
   b[0] = 1;
   for (int i = 1; i < n; i++) {
      a[i] = a[i-1] + b[i-1];
      b[i] = a[i-1];
   }
   return a[n-1] + b[n-1];
}
int main() {
   cout << noConsecutiveOnes(4) << endl;
}

Đầu ra

8