У исполнителя Калькулятор две команды, которым присвоены номера.
1. Прибавь 2. 2. Умножь на 5.
Первая из них увеличивает число на экране на 2, вторая увеличивает его в 5 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые число 2 преобразуют в число 50?
Мы хотим узнать, сколькими способами (программами) можно преобразовать число 2 в число 50, используя две команды: 1. «Прибавь 2»: увеличить число на 2. 2. «Умножь на 5»: умножить число на 5.
Чтобы решить задачу, удобно рассмотреть её в обратном направлении, то есть, задачу «сколькими программами можно получить число x из числа 2» описать с помощью рекурсии.
Обозначим через f(x) количество программ, переводящих число 2 в число x. Начальное условие: f(2)=1 (только пустая программа даёт число 2).
Если мы получаем число x последней выполненной операцией, то она могла быть одной из двух:
Не нашел нужную задачу?