연속되는 1이 없는 이진 문자열의 수를 세는 프로그램을 C/C++로 작성하시겠습니까?

여기서 흥미로운 질문을 보게 될 것입니다. n이라는 값이 주어졌다고 가정하자. 연속된 1이 없는 길이 n의 문자열을 모두 찾아야 합니다. n = 2이면 숫자는 {00, 01, 10}이므로 출력은 3입니다.

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

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

Algorithm

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

Example

의 중국어 번역은 다음과 같습니다.

Example

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

Output

8

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