Карточки
Тесты
Главная
Курсы
Подписка
13. Анализ хода исполнения алгоритма: #295614
Исполнитель Минус преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Вычесть $2$
2. Вычесть $5$
Первая команда уменьшает число на экране на $2$, вторая уменьшает это число на $5$. Программа для исполнителя Минус – это последовательность команд.
Сколько существует программ, которые число $17$ преобразуют в число $1$?
Для решения используем рекурсивную функцию.
def f(x, y):
if x == y:
return 1
if x < y:
return 0
return f(x - 2, y) + f(x - 5, y)
print(f(17, 1))Функция $f(x, y)$ считает количество программ, переводящих число $x$ в число $y$.
Если $x=y$, нужная программа найдена. Если $x<y$, такая траектория не подходит, так как все команды только уменьшают число.
Программа выведет: $11$.
20
