Разбор задачи B1 (демо ЕГЭ 2013)
У исполнителя Арифметик две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая утраивает его.
Например, 21211 – это программа
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в число 19.
Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
1. прибавь 2,
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая утраивает его.
Например, 21211 – это программа
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в число 19.
Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.
Ответ: 11212
Решение:
Решим обратную задачу: из 69-и получим 3. Будем использовать команды:убавь на 2, раздели на 3. Первая команда убавляет от числа 2, а вторая-делит число на 3. Выполним 5 команд. Изобразим ход выполнения команд:
Изобразим ход выполнения команд в виде графа:
На рисунке видно,что в ходе выполнения команды получили число 3, оно выделено темно-розовым цветом. К 3-м приведет ветка графа: 69→23→21→7→5→3
Изобразим прямой ход выполнения, т.е. из 3-х получим 69:
3→5→7→21→23→69
Распишем подробно:
1 команда: 3+2=5 (1.прибавь 2).
2 команда: 5+2=7 (1.прибавь 2).
3 команда: 7*3=21 (2.умножь на 3).
4 команда: 21+2=23 (1.прибавь 2).
5 команда: 23*3=69 (2.умножь на 3).
Получили порядок команд: 11212.