Каково количество двоичных строк без последовательных единиц?

Давайте рассмотрим пример, объясняющий концепцию подсчета двоичных строк без последовательных единиц.

Пример

Предположим, мы хотим подсчитать количество двоичных строк длиной 3, которые не содержат последовательных единиц. Бинарная строка — это строка, состоящая только из 0 и 1.

Возможные двоичные строки длиной 3: 000, 001, 010, 011, 100, 101, 110 и 111.

Однако нам нужно считать только те двоичные строки, в которых нет последовательных единиц. Итак, нам нужно исключить из подсчета строки 011, 101 и 111.

Давайте проанализируем оставшиеся двоичные строки:

• 000: это допустимая строка, поскольку в ней нет последовательных единиц.

• 001: Это допустимая строка, поскольку в ней нет последовательных единиц.

• 010: Это допустимая строка, поскольку в ней нет последовательных единиц.

• 100: это допустимая строка, поскольку в ней нет последовательных единиц.

• 110: это недопустимая строка, поскольку в ней есть последовательные единицы.

Из приведенного выше анализа мы видим, что существует 4 допустимые двоичные строки длиной 3 без последовательных единиц.

PHP-программа для подсчета количества двоичных строк без последовательных единиц

Метод 1. Использование динамического программирования

Пример

Выход

Number of binary strings without consecutive 1's: 13

Пояснение кода

Этот PHP-код определяет функцию countBinaryStrings, которая вычисляет количество двоичных строк длиной $n без последовательных единиц с использованием динамического программирования. Он инициализирует массив $dp с базовыми вариантами $dp[0] = 1 и $dp[1] = 2, представляющими счетчики для строк длина 0 и 1 соответственно. Затем он использует цикл для заполнения оставшихся счетчиков для длин от 2 до $n путем суммирования счетчиков для длин $i - 1 и $i - 2. Наконец, он возвращает счетчик длины $n и печатает его. В этом конкретном примере код вычисляет количество двоичных строк без последовательных единиц для длины 5 и отображает результат.

Метод 2

Выход

Number of binary strings without consecutive 1's: 13

Пояснение кода

Этот PHP-код вычисляет количество различных двоичных строк длиной $n без двух последовательных единиц. Он определяет два массива: $a и $b для хранения счетчиков. Базовые случаи задаются как $a[0] = $b[0] = 1. Затем используется цикл для вычисления счетчиков для длин от 1 до $ n-1. Счетчик длины $i получается путем суммирования счетчика длины $i-1 из массива $a и счетчика длины $i-1 из массива $b. Кроме того, счетчик длины $i в массиве $b получается из счетчика длины $i-1 в массиве $ а. Наконец, код возвращает сумму счетчика длины $n-1 из массива $a и счетчика длины $n-1 из массива $b, представляющее общее количество двоичных строк без последовательных единиц. В этом конкретном примере код вычисляет счетчик для длины 5 и отображает результат.

Заключение

В заключение, первый метод использует динамическое программирование, инициализируя массив с базовыми случаями и итеративно вычисляя счетчики для больших длин. Он эффективно вычисляет результат, суммируя значения для двух предыдущих длин. Второй метод использует более простой подход, используя два массива для хранения счетчиков и итеративно обновляя их на основе счетчиков предыдущей длины. Он напрямую вычисляет общее количество без необходимости суммирования двух массивов по отдельности. Оба метода обеспечивают точный подсчет двоичных строк без последовательных единиц, и выбор между ними может зависеть от конкретных требований и соображений производительности.