Просмотр содержимого документа
«26.2.Еще пример задания»
Еще пример задания:
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь две младшие цифры на 1
Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая-либо из двух младших цифр равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.
Сколько есть программ, которые число 23 преобразуют в число 48?
Решение (1 способ, составление таблицы):
заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
при заданных командах очередное число N может быть получено двумя способами:
увеличением на 1 (для всех чисел, больших начального числа)
увеличением обеих цифр на 1 в результате выполнения команды 2 (то есть, фактически командой «+11») – для всех чисел, больших или равных 23 + 11 = 34, которые НЕ оканчиваются на 0;
увеличением только младшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+1») – для всех чисел от 91 до 99, но в нашем диапазоне (23..48) таких нет
увеличением только старшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+10») – для всех чисел, больших 34 и имеющих 9 на конце; в нашем случае под этот вариант подходит только число 39
таким образом, рекуррентные формулы принимают вид
для всех чисел, меньших, чем 34, а также для всех чисел, оканчивающихся на 0
для чисел, больших или равных 34, кроме 39
для числа 39
других способов получения числа с помощью исполнителя с заданными командами нет, то есть мы таким образом рассматриваем все возможные программы
начальное значение: (число 23 можно получить единственной пустой программой)
далее заполняем таблицу:
| 23 | … | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |
| 1 | … | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 8 | 9 | 10 | 11 | 12 | 14 | 17 | 21 | 26 |
здесь многоточия означают, что для всех чисел от 23 до 33 включительно количество программ равно 1;
например, для числа 47 количество программ вычисляется как
= 17 + 4 = 21
а для числа 39 –как
= 6 + 1 + 1 = 8
Ответ: 26