У исполнителя Удвоитель две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Первая из них увеличивает данное число на 2, вторая — увеличивает его в 5 раз. Программа для исполнителя Удвоитель — это последовательность команд.
Определите количество программ, которые число 1 преобразуют в число 37.
Заметим, что все числа, получаемые с помощью заданных команд из числа 1, — нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 37 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 5, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i − 2), i — нечётное. Если число на 5 делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда R(i) = R(i−2)+R(i/5), i — нечётное. Заполним соответствующую таблицу по приведенным формулам слева направо:
| 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 |
| 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 5 | 5 |
| 29 | 31 | 33 | 35 | 37 | |||||||||
| 5 | 5 | 5 | 7 | 7 |
Ответ: 7