연속되는 1이 없는 이진 문자열의 개수는 무엇입니까?

연속되는 1 없이 이진 문자열을 계산하는 개념을 설명하는 예를 살펴보겠습니다.

예

연속된 1을 포함하지 않는 길이가 3인 이진 문자열의 수를 계산한다고 가정합니다. 이진 문자열은 0과 1로만 구성된 문자열입니다.

길이 3의 가능한 이진 문자열은 000, 001, 010, 011, 100, 101, 110 및 111입니다.

그러나 연속된 1이 없는 이진 문자열만 계산하면 됩니다. 따라서 문자열 011, 101, 111을 개수에서 제외해야 합니다.

나머지 바이너리 문자열을 분석해 보겠습니다.

• 000: 연속된 1이 없으므로 유효한 문자열입니다.

• 001: 연속된 1이 없으므로 유효한 문자열입니다.

• 010: 연속된 1이 없으므로 유효한 문자열입니다.

• 100: 연속된 1이 없으므로 유효한 문자열입니다.

• 110: 1이 연속되어 있으므로 잘못된 문자열입니다.

위 분석에서 연속된 1이 없는 길이 3의 유효한 이진 문자열 4개가 있음을 알 수 있습니다.

연속되는 1 없이 이진 문자열의 수를 계산하는 PHP 프로그램

방법 1 - 동적 프로그래밍 사용

예

산출

Number of binary strings without consecutive 1's: 13

코드 설명

이 PHP 코드는 동적 프로그래밍을 사용하여 연속된 1이 없는 $n 길이의 이진 문자열 수를 계산하는 countBinaryStrings라는 함수를 정의합니다. 기본 사례 $dp[0] = 1 및 $dp[1] = 2로 배열 $dp를 초기화합니다. 길이는 각각 0과 1입니다. 그런 다음 루프를 사용하여 길이 $i - 1 및 $i -에 대한 개수를 합산하여 길이 2에서 $n까지의 나머지 개수를 채웁니다. 2. 마지막으로 길이 $n에 대한 개수를 반환하고 인쇄합니다. 이 특정 예에서 코드는 길이 5에 대해 연속된 1이 없는 이진 문자열의 수를 계산하고 결과를 표시합니다.

방법 2

산출

Number of binary strings without consecutive 1's: 13

코드 설명

이 PHP 코드는 두 개의 연속된 1이 없는 $n 길이의 고유한 이진 문자열 수를 계산합니다. 개수를 저장하기 위해 $a 및 $b라는 두 개의 배열을 정의합니다. 기본 사례는 $a[0] = $b[0] = 1로 설정됩니다. 그런 다음 루프를 사용하여 길이 1부터 $까지의 개수를 계산합니다. n-1. 길이 $i 수는 배열 $a의 $i-1 길이 수와 $[ 길이 수를 합산하여 얻습니다. &&&]i-1 배열 $b. 또한 배열 $i의 길이 개수는 $b 배열의 길이 개수 $i-1 $에서 얻습니다. 에이. 마지막으로, 코드는 배열 $a의 길이 $n-1 개수와 배열 [의 길이 $n-1 개수의 합을 반환합니다. &&&]$b: 연속된 1이 없는 이진 문자열의 총 개수를 나타냅니다. 이 특정 예에서 코드는 길이 5에 대한 개수를 계산하고 결과를 표시합니다. 결론

결론적으로 첫 번째 방법은 동적 프로그래밍을 활용하여 기본 사례로 배열을 초기화하고 더 큰 길이에 대한 개수를 반복적으로 계산합니다. 이전 두 길이의 개수를 합산하여 결과를 효율적으로 계산합니다. 두 번째 방법은 두 개의 배열을 사용하여 개수를 저장하고 이전 길이의 개수를 기반으로 반복적으로 업데이트하는 더 간단한 접근 방식을 사용합니다. 두 배열을 별도로 합산할 필요 없이 총 개수를 직접 계산합니다. 두 방법 모두 연속된 1이 없는 이진 문자열의 정확한 개수를 제공하며 둘 중 하나를 선택하는 방법은 특정 요구 사항 및 성능 고려 사항에 따라 달라질 수 있습니다.