Раздел B • Категория B2 (демонстрационный вариант-2012)
Условие задачи
Дано:
у исполнителя Утроитель две команды, которым присвоены номера:
прибавь 1;
умножь на 3.
Первая из них увеличивает число на экране на 1, вторая ─ утраивает его.
Вопрос:
запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, указывая лишь номера команд.
(Например, 21211 ─ это программа
умножь на 3;
прибавь 1;
умножь на 3;
прибавь 1;
прибавь 1.
которая преобразует число 1 в 14).
Методические указания
Первое, на что стоит обратить внимание - то, что обе команды увеличивают текущее число. Следовательно, наиболее оптимально решать поставленную задачу методом от обратного, то есть преобразовывать число 22 в число 1, используя разрешенные команды исполнителя.
Почему можно выбирать подобный метод решения ("спускаться" от конечного числа к начальному числу)?
Потому что, гораздо удобнее двигаться по однозначно правильному маршруту не перебирая заведомо ложные варианты. Для движения по правильному маршруту поможет следующее тривиальное правило:
если преобразуемое число кратно 3 (делится на 3 без остатка), то делим это число на 3;
если преобразуемое число не кратно 3 (делится на 3 с остатком), то вычитаем 1.
Вы спросите, а откуда взялись операции "деление на 3" и "вычитание 1"? Все дело в том, что преобразование числа производится от конечного значения к начальному значению, следовательно, и взять нужно операции-антагонисты по отношению к исходным операциям.
Решение
Для получения из числа 22 число 1 воспользуемся процессинговой таблицей, состоящей из 4 колонок;
N команды | Число | "Деление на 3" или "Вычитание 1" | Результат |
1 | 22 | "Вычитание 1", так как 22 не кратно 3 | 22 - 1 = 21 |
2 | 21 | "Деление на 3", так как 21 кратно 3 | 21 / 3 = 7 |
3 | 7 | "Вычитание 1", так как 7 не кратно 3 | 7 - 1 = 6 |
4 | 6 | "Деление на 3", так как 6 кратно 3 | 6 / 3 = 2 |
5 | 2 | "Вычитание 1", так как 2 не кратно 3 | 2 - 1 = 1 |
Как видно из заполненной процессинговой таблицы:
число 1 успешно получено, используя разрешенные команды исполнителя;
число 1 получено, не дольше, чем за 5 команд (в данном случае, потребовалось ровно 5 команд).
По условию задачи требуется выписать порядок команд получения числа 22 из числа 1. Но мы получили обратную ситуацию: преобразовали число 22 в число 1, следовательно, нужно проводить анализ записей процессинговой таблицы от последней к первой. Причем, конвертируем команды в допустимые, то есть:
если в процессинговой таблице стоит команда "Вычитание 1", то ей соответствует команда "Прибавь 1" под номером 1;
если в процессинговой таблице стоит команда "Деление на 3", то ей соответствует команда "Умножь на 3" под номером 2;
Анализируя таблицу от последней записи к первой получаем последовательность команд:
Прибавь 1 | Умножь на 3 | Прибавь 1 | Умножь на 3 | Прибавь 1
1 | 2 | 1 | 2 | 1
Последовательность команда: 12121
Вывод: |
порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, имеет вид: 12121 |
Резюме
выбираем метод решения преобразования числа 1 в число 22, используя метод от обратного;
анализируем процессинговую таблицу от конца к началу, меняя команды на противоположные.
Ответ: |
12121 |
Комментарии