1

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

Есть ответ

def seq_count(n, p = 0):
    if not n: return 1
    return seq_count(n - 1, 0) + (0 if p else seq_count(n - 1, 1))

Нужно переписать итеративно.

seq_count(3) вернет 5, так как из возможных комбинаций:

000 001 011 111 010 100 110 101

не содержат 2 единицы подряд:

000 001 010 100 101

но почему это работает совершенно не понятно, поэтому и прошу переписать на циклы.

2
  • А что за последователи длины? Как работает алгоритм? Почему seq_count(3) вернет 5?
    – gil9red
    19 мая 2018 в 1:22
  • seq_count(3) вернет 5, так как из возможных комбинаций 000 001 011 111 010 100 110 101, не содержат 2 единицы подряд 000 001 010 100 101, но почему это работает совершенно не понятно, поэтому и прошу переписать на циклы
    – firet
    19 мая 2018 в 1:43

3 ответа 3

3

почему это работает совершенно не понятно, поэтому и прошу переписать на циклы

В данном случае рекурсивное решение (как это часто бывает для задач динамического программирования) буквально решение описывает: f(0...) = f(00..) + f(01..) и f(1...) = f(10..) то есть количество последовательностей бит без 11 длиной n равно количеству последовательностей длиной (n-1), начинающихся на 0, плюс количество последовательностей, начинающихся на 1, если предыдущий бит не равен 1 (чтобы исключить 11):

def count(n, previous_bit=0):
    assert n>=0
    return 1 if n==0 else (
        count(n-1, 0)
        + (previous_bit == 0) * count(n-1,1))

Что почти также ясно как решение в лоб (перебрать все битовые последовательности длиной n бит, посчитать сколько не содержит 11):

def brute_force(n):
    return sum(1 for bits in map(bin, range(2**n)) if '11' not in bits)

Циклы могут скрыть очевидность правильности решения:

def fib(a=0, b=1):
    """Fibonacci sequence"""
    while True:
        yield a
        a, b = b, a+b

Все варианты одинаковые результаты выдают:

for n, f in zip(range(10), fib(1, 2)):
    print(n, count(n), f, brute_force(n))

Результат:

0 1 1 1
1 2 2 2
2 3 3 3
3 5 5 5
4 8 8 8
5 13 13 13
6 21 21 21
7 34 34 34
8 55 55 55
9 89 89 89

Добавив @functools.lru_cache(maxsize=5) перед count(), можно запомнить несколько предыдущих результатов, чтобы не вычислять их повторно.

Если точный результат не нужен (достаточно приближённого), то есть замкнутые формулы, которые за O(1) результат позволяют находить. Подробнее см. ссылки в ответе на Сумма четных элементов ряда Фибоначчи.

2

Можно повторить генерацию комбинаций и посчитать те, что не имеют двух единиц подряд:

import itertools


items = [''.join(i) for i in itertools.product('01', repeat=3)]
print(items)  # ['000', '001', '010', '011', '100', '101', '110', '111']

items = [i for i in items if '11' not in i]
print(items)  # ['000', '001', '010', '100', '101']
print(len(items))  # 5

Алгоритм есть, теперь можно проверить его:

import itertools


def seq_count_v2(n):
    items = [''.join(i) for i in itertools.product('01', repeat=n)]
    items = [i for i in items if '11' not in i]
    return len(items)

  
for i in range(3, 10):
    print(seq_count(i), seq_count_v2(i))

Совпадает:

5 5
8 8
13 13
21 21
34 34
55 55
89 89

PS. Знаю, что алгоритм в seq_count_v2 не оптимизированный, но решил показать саму идею

1

Попробуем дать не рыбу, но удочку.

Пусть есть правильная последовательность длиной K. Эта последовательность может кончаться на 0 - тогда к ней можно добавить хоть 0, хоть 1. А если она кончается на 1, то к ней можно добавить только 0. Или другая интерпретация: 0-последовательность, может быть получена как из более короткой 0-последовательности, так и из более короткой 1-последовательности, а вот 1-последовательность можно сделать только из 0-последовательности.

Обозначим количество первых F0(K), вторых F1(K). Их количество в зависимости от количества последовательностей предыдущей длины:

F0(K) = F0(K-1) + F1(K-1)
F1(K) = F0(K-1)
S(K) = F0(K) + F1(K)  //общее количество правильных последовательностей

Осталось задать начальные значения для единичной длины и сделать цикл с обновлением значений.

P.S. Получающаяся последовательность содержит довольно примечательные числа

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.