Разбор задачи B3 (демо ЕГЭ 2008)
У исполнителя Утроитель две команды, которым присвоены номера:
1. вычти 2
2. умножь на три
Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:
умножь на три
вычти 2
умножь на три
вычти 2
вычти 2,
которая преобразует число 2 в 8).
(Если таких программ более одной, то запишите любую из них.)
1. вычти 2
2. умножь на три
Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:
умножь на три
вычти 2
умножь на три
вычти 2
вычти 2,
которая преобразует число 2 в 8).
(Если таких программ более одной, то запишите любую из них.)
Ответ: 11121
Решение:
Решим обратную задачу: из 13-и получим 11.
Будем использовать команды: прибавь 2, раздели на 3. Первая команда добавляет 2 к числу, а вторая-делит число на 3. Выполним 5 команд. Изобразим ход выполнения команд:
Изобразим ход выполнения команд в виде графа:
На рисунке видно, что в ходе выполнения команды получили число 11, оно выделено темно-розовым цветом. К 11-и приведет ветка графа: 13→15→5→7→9→11.
Изобразим прямой ход выполнения, т.е. из 11-и получим 13:
11→9→7→5→15→13
Распишем подробно:
1команда: 11−2=9 (1.вычти 2).
2 команда: 9−2=7 (1.вычти 2).
3 команда: 7−2=5 (1.вычти 2).
4 команда: 5*3=15 (2.умножь на три).
5 команда: 15−2=13 (1.вычти 2).
Получили порядок команд: 11121.