연속된 1을 포함하지 않는 이진 문자열의 수를 계산하는 PHP 프로그램

연속된 1이 없는 이진 문자열의 개수는 몇 개인가요?

연속되는 1 없이 이진 문자열을 계산하는 개념을 설명하기 위해 예를 들어 보겠습니다.

예

연속된 1을 포함하지 않는 길이가 3인 이진 문자열의 수를 세고 싶다고 가정해 보겠습니다. 이진 문자열은 0과 1로만 구성된 문자열입니다.

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

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

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

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

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

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

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

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

위 분석에서 길이가 3인 유효한 바이너리 문자열이 4개 있고 연속된 1이 없음을 알 수 있습니다.

연속되는 1이 없는 이진 문자열의 개수를 세는 PHP 프로그램

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

예

으아악

출력

으아악

코드 설명

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

방법 2

으아악

출력

으아악

코드 설명

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

결론

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

위 내용은 연속된 1을 포함하지 않는 이진 문자열의 수를 계산하는 PHP 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!