Перебор вариантов
Рекурсия перебирает варианты. Чтобы выписать все слова длины n из букв «а» и «б», функция получает уже собранное начало и дописывает к нему по букве, пока слово не наберет нужную длину.
Готовое слово — базовый случай: его выводят. Иначе функция по очереди пробует каждое продолжение, и каждое продолжение перебирает свои варианты дальше.
def words(start, n):
if len(start) == n:
print(start)
return
for letter in "аб":
words(start + letter, n)
words("", 2)
Перестановки — все порядки букв. Первой по очереди ставят каждую из оставшихся букв, а остальные переставляет тот же вызов: perm(start + rest[i], rest без буквы i).
Строка без буквы с номером i — rest[:i] + rest[i + 1:]. Когда букв не осталось, перестановка готова.
def perm(start, rest):
if rest == "":
print(start)
for i in range(len(rest)):
perm(start + rest[i], rest[:i] + rest[i + 1:])
perm("", "abc")
Перебор растет очень быстро. В числах Фибоначчи fib(n) = fib(n - 1) + fib(n - 2) одни и те же значения считаются заново много раз, и уже fib(35) заметно долго ждать.
Помогает словарь-память: найденный ответ запоминают в memo[n] и при следующем вызове сразу возвращают. Так каждое значение считается один раз.
memo = {}
def fib(n):
if n < 2:
return n
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(10))
print(fib(80))
Итог урока. При переборе функция получает собранное начало. В базовом случае она выводит или проверяет готовый вариант, а иначе по очереди пробует каждое продолжение.
Так перечисляют строки, перестановки и наборы и проверяют, есть ли подходящий. Ответы, которые нужны много раз, запоминают в словаре — тогда даже большой перебор считается быстро.
В следующем уроке — заливка: рекурсия обходит на поле целую область клеток.
Урок пройден
Перебор вариантов
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Перебор вариантов
Перебор вариантов рекурсией в Python: строки из нулей и единиц, перестановки, выбор чисел с нужной суммой, словарь-память для повторных вызовов. В 6 заданиях вы выпишете двоичные строки, строки без двух единиц подряд и перестановки, найдете набор с суммой, посчитаете прыжки кузнечика и прочитаете программу: что она выведет?