Садовая дорожка длиной n выкладывается плитками длины 1 и 2. Порядок плиток важен: 1+2 и 2+1 — разные дорожки. Напишите tile_ways(n): функция возвращает число различных дорожек, заполняя таблицу подзадач.
tile_ways(1) # 1
tile_ways(3) # 3: 1+1+1, 1+2, 2+1
tile_ways(0) # 1: пустая дорожка0 <= n <= 40. Подходит таблица или рекурсия с запоминанием; полный перебор не успеет.Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
def tile_ways(n: int) -> int:
"""Число способов выложить дорожку длины n плитками длины 1 и 2."""
# ваш код
raise NotImplementedErrorВывод обрезан: показаны первые строки.
def test_small():
"""n = 1, 2, 3, 4 → 1, 2, 3, 5"""
for n, expected in [(1, 1), (2, 2), (3, 3), (4, 5)]:
got = tile_ways(n)
assert got == expected, f"tile_ways({n}): ожидалось {expected}, получено {got!r}"
def test_zero():
"""n = 0 → 1 (пустая дорожка)"""
got = tile_ways(0)
assert got == 1, f"ожидалось 1, получено {got!r}"
def test_ten():
"""n = 10 → 89"""
got = tile_ways(10)
assert got == 89, f"ожидалось 89, получено {got!r}"
def test_first_sixteen():
"""n = 0…15 — заранее посчитанные ответы"""
expected = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
for n, answer in enumerate(expected):
got = tile_ways(n)
assert got == answer, f"tile_ways({n}): ожидалось {answer}, получено {got!r}"
def test_large():
"""n = 38, 39, 40 — верные ответы за отведённое время"""
for n, expected in [(38, 63245986), (39, 102334155), (40, 165580141)]:
got = tile_ways(n)
assert got == expected, f"tile_ways({n}): ожидалось {expected}, получено {got!r}"
test_large.timeout_hint = "Если это рекурсия, добавьте запоминание или заполняйте таблицу слева направо"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 tile_ways.py — тесты те же, результат покажет ✓ / ✗ и итог.
Посмотрите на последнюю плитку дорожки длины n: она либо длины 1, либо длины 2. Какие подзадачи остаются?
ways[n] = ways[n − 1] + ways[n − 2], причём ways[0] = 1 (пустая дорожка — один способ) и ways[1] = 1.
Рекурсия без запоминания пересчитывает одни и те же подзадачи экспоненциально много раз. Заполняйте таблицу слева направо.
def tile_ways(n: int) -> int:
"""Число способов выложить дорожку длины n плитками длины 1 и 2."""
ways = [1] + [0] * n # ways[k] — число дорожек длины k
for k in range(1, n + 1):
ways[k] = ways[k - 1] + (ways[k - 2] if k >= 2 else 0)
return ways[n]