이진 표현에서 연속 1이 없는 1에서 n 비트 숫자?

이 문제에서는 연속 1이 없는 이진수를 찾아야 합니다. 3비트 이진 문자열에는 연속 1이 있는 3개의 이진수 011, 110, 111이 있고 연속 1이 없는 5개의 숫자가 있습니다. 따라서 이 알고리즘을 3비트 숫자에 적용하면 답은 5가 됩니다.

a[i]가 비트 수가 i이고 연속적인 1을 포함하지 않는 이진수 집합이고 b[i]가 비트 수가 i이고 연속적인 1을 포함하는 이진수 집합이면, 다음과 같은 반복 관계가 있습니다. -

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

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

입력

이 알고리즘은 이진수에 대해 비트 수를 사용합니다. 입력을 4로 둡니다.

출력

연속된 1이 없는 이진 문자열의 수를 반환합니다.

여기서 결과는 -8입니다. (연속 1이 없는 8개의 이진 문자열이 있습니다)

알고리즘

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

예시

#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;
}

출력

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