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

2진수는 2개만 포함하는 숫자입니다. 즉, 1개 또는 2개가 있습니다. 모든 이진수는 이진 비트의 스트림이며 우리는 이것을 이진 문자열로 간주합니다. 이 문자열에 대해 N 비트의 연속적인 문자열을 포함하지 않는 이진 문자열의 수를 찾아야 합니다.

예를 들어, N - 5의 경우 이진 문자열은 주어진 제약 조건을 충족합니다.

한 가지 방법은 모든 N자리 문자열을 생성하고 주어진 제약 조건을 충족하는 문자열만 인쇄하는 것입니다. 하지만 이 방법은 작업할 때 그다지 효율적이지 않습니다.

다른 방법은 재귀를 사용하는 것입니다. 재귀의 각 지점에서 부분적으로 형성된 숫자에 0과 1을 추가하고 한 자릿수 적은 숫자로 되풀이합니다. 여기서 트릭은 부분적으로 형성된 숫자의 마지막 숫자가 0인 경우에만 1을 추가하고 반복한다는 것입니다. 그렇게 하면 출력 문자열에 연속적인 1이 없을 것입니다.

Input: n = 5
Output: Number of 5-digit binary strings without any consecutive 1's are 13

예시

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
   if (n == 0)
      return 0;
   if (n == 1) {
      if (last_digit)
         return 1;
      else
         return 2;
   }
   if (last_digit == 0)
      return countStrings(n - 1, 0) + countStrings(n - 1, 1);
   else
      return countStrings(n - 1, 0);
}
int main() {
   int n = 5;
   cout << "Number of " << n << "-digit binary strings without any "
   "consecutive 1's are " << countStrings(n, 0);
   return 0;
}