C/C++ 프로그램: 연속된 1이 없는 이진 문자열의 개수를 계산하시겠습니까?

2진수는 0과 1, 두 자리 숫자만 포함하는 숫자입니다. 각 이진수는 이진 문자열로 생각되는 이진 비트의 스트림입니다. 이 문자열의 경우 연속된 1을 포함하지 않는 N 길이의 이진 문자열 수를 찾아야 합니다.

예를 들어 N=5인 경우 주어진 조건을 만족하는 바이너리 문자열은 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101입니다.

한 가지 방법은 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&#39;s are " << countStrings(n, 0);
   return 0;
}

위 내용은 C/C++ 프로그램: 연속된 1이 없는 이진 문자열의 개수를 계산하시겠습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!