26.1.Еще пример задания

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 1

2. увеличь вторую с конца цифру на 1

Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.

Сколько есть программ, которые число 15 преобразуют в число 28?

Решение (1 способ, составление таблицы):

1. заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)

2. при заданных командах очередное число N может быть получено двумя способами:

3. увеличением на 1 (для всех чисел, больших начального числа)

4. увеличением числа десятков на 1 (то есть, фактически командой «+10») – для всех чисел, больших или равных 25; например, число 24 не может быть получено этой командой (14 + 10 = 24), потому что число 14 меньше, чем начальное значение 15

5. таким образом, рекуррентные формулы принимают вид

для всех чисел, меньших, чем 25

для чисел, больших или равных 25

1. других способов получения числа с помощью исполнителя с заданными командами нет, то есть мы таким образом рассматриваем все возможные программы

2. начальное значение: (число 15 можно получить единственной пустой программой)

3. далее заполняем таблицу:

   	15	16	17	18	19	20	21	22	23	24	25	26	27	28
   	1	1	1	1	1	1	1	1	1	1	2	3	4	5

4. Ответ: 5