C/C++에서 연속 1이 없는 이진 문자열의 수를 계산하는 프로그램?

<시간/>

여기서 우리는 한 가지 흥미로운 문제를 보게 될 것입니다. 하나의 n 값이 주어진다고 가정합니다. 연속된 1이 없도록 길이가 n인 모든 문자열을 찾아야 합니다. n =2이면 숫자는 {00, 01, 10}이므로 출력은 3입니다.

동적 프로그래밍을 사용하여 해결할 수 있습니다. 테이블 'b'와 'b'가 있다고 가정합니다. 여기서 arr[i]는 길이가 i이고 연속적인 1이 없고 0으로 끝나는 이진 문자열의 수를 저장합니다. 마찬가지로 b는 동일하지만 1로 끝나는 숫자를 보유합니다. 마지막 위치에 0 또는 1을 추가할 수 있습니다. 0이지만 마지막 값이 1인 경우 0만 추가합니다.

이 아이디어를 얻기 위한 알고리즘을 살펴보겠습니다.

알고리즘

noConsecutiveOnes(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

예시

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