Задание 23 - Информатика
Условие задачи
Задание 7570
У исполнителя Прибавитель две команды, которым присвоены номера:
1. прибавь 1,
2. прибавь 4.
Первая из них увеличивает число на экране на 1, вторая увеличивает это число на 4. Программа для Прибавителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 15?
Комментарий
Оттолкнемся от того, что вторую команду мы можем использовать не более 3 раз. Операцию сложения можно выполнять в любом порядке,поэтому порядок команд в программе также не имеет значения для результата. Пусть R(n) — количество программ, которые число 1 преобразуют в число n.
Тогда справедлива следующая формула: R(n) = R(n - 1) + R(n - 4) если n больше 4.
R(3) = 1
R(4) = 1
R(5) = R(4) = 1
R(6) = R(5) = 1
R(7) = R(6) + R(3) = 1 + 1 = 2
R(8) = R(7) + R(4) = 2 + 1 = 3
R(9) = R(8) + R(5) = 3 + 1 = 4
R(10) = R(9) + R(6) = 4 + 1 = 5
R(11) = R(10) + R(7) = 5 + 2 = 7
R(12) = R(11) + R(8) = 7 + 3 = 10
R(13) = R(12) + R(9) = 10 + 4 = 14
R(14) = R(13) + R(10) = 14 + 5 = 19
R(15) = R(14) + R(11) = 19 + 7 = 26
Получается 26 программ.
