연속 1이 없는 이진 문자열 계산

이 문제에서는 연속 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]

입력 및 출력

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)

알고리즘

countBinNums(n)

입력: n은 비트 수입니다.
출력 - 연속 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 consecitive 1's: "<<countBinNums(n) << endl;
   return 0;
}

출력

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