Алгоритмы и рекурсия · тема 3 из 8
Число программ исполнителя
Исполнитель · 2027 №13 / 2026 №23
Одна идея — один пример
Состояние — текущее число. Количество путей в состояние можно складывать из предыдущих состояний. Это динамическое программирование.
ways = [0] * 5
ways[1] = 1
for x in range(2, 5):
ways[x] = ways[x - 1]
if x % 2 == 0: ways[x] += ways[x // 2]
print(ways[4])Теперь решаем самостоятельно
Если команды одинаково меняют число, программы всё равно различны, когда различаются команды. Запрещённому состоянию присваивают 0 путей.
Вводится n от 2 до 30. Исполнитель начинает с 1, команды +1 и ×2. Выведи число разных программ, приводящих к n.
Пример входных данных и результата
Ввод:
2
Вывод:
2
Черновик и файл программы
Черновик сохраняется в этом браузере. Ctrl/⌘ + S — сохранить.
Результаты проверки
Напиши решение и нажми «Проверить код». Данные каждого теста подаются автоматически.
Нужна подсказка?
К x приходят из x-1 и, если x чётное, из x//2.
На чём легко ошибиться
Не прибавляй путь из x//2 для нечётного x.
Разобрать один из способов решения
Сначала попробуй написать код сам. Сравни алгоритм, затем закрой разбор и воспроизведи решение без подсказки.
n = int(input())
ways = [0] * (n + 1)
ways[1] = 1
for x in range(2, n + 1):
ways[x] = ways[x - 1]
if x % 2 == 0: ways[x] += ways[x // 2]
print(ways[n])Тесты проверяют результат на учебных примерах, но не доказывают правильность для любого входа. Объясни каждую строку и предложи собственный тест.
Перед следующей темой
Назови входные данные, результат, основной шаг алгоритма и граничный случай. Если использовал разбор, напиши решение заново. Для свободных экспериментов открой Python онлайн.
Все темы этого курса
Программа подготовлена по темам банка «Академии С». Официальные документы: ФИПИ. Справочник языка: Python. Не все экзаменационные задачи нужно решать программой: например, работа в таблицах требует освоения табличного редактора.