Question

Python Определите количество последовательностей из нулей и единиц длины (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом. Вводится натуральное число , не превосходящее 40. Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231 − 1.

Answer 1

x = (input("Введіть число з 0 и 1:"))
nul = []
one = []
new = x.split('0')
nul.append(new)
newn = x.split('1')
one.append(newn)
print(nul)
print(one)

Answer 2

Для решения данной задачи можно использовать динамическое программирование. Пусть dp[i] - количество последовательностей длины i, в которых никакие три единицы не стоят рядом. Тогда можно записать рекуррентное соотношение:

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

Объяснение этого соотношения следующее: чтобы получить последовательность длины i, не содержащую трех единиц подряд, можно взять последовательность длины i-1 и добавить в конец 0, или взять последовательность длины i-2 и добавить в конец 01, или взять последовательность длины i-3 и добавить в конец 001.

Изначально dp[0] = 1, dp[1] = 2, dp[2] = 4 (это можно проверить вручную). Далее можно заполнить массив dp[i] для i от 3 до n, где n - данное натуральное число. Ответом на задачу будет dp[n].

В Python код для решения этой задачи будет выглядеть следующим образом:

pythonCopy code
n = int(input())
dp = [1, 2, 4] + [0] * (n-2)
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
print(dp[n])

Этот код заполняет массив dp и выводит ответ на задачу. Сложность этого алгоритма O(n), так как требуется пройти по массиву dp от 3 до n. Время выполнения этого алгоритма для n=40 составит около 1 миллисекунды.