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

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

2016-06-17 20:40:51

Формулировка задания: У исполнителя Калькулятор две команды, которым присвоены номера: 1 – прибавь 2, 2 – умножь на 3. Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из A числа B, содержащей не более K команд, указывая лишь номера команд.

Задание входит в ЕГЭ по информатике для 11 класса под номером 6 (Анализ и построение алгоритмов для исполнителей).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:
умножь на 3
прибавь 2
умножь на 3
прибавь 2
прибавь 2,
которая преобразует число 1 в 19.)

Решение:

Нужно получить число 28 из 0, используя не более 6 команд. Лучше всего решать эту задачу обратным путем – получить из числа 28 число 0. Так как при умножении любого целого числа на 3 получится целое число, а при делении целого числа на 3 целый результат будет не всегда.

Заменим команды на обратные: «прибавь 2» на «вычти 2», а «умножь на 3» на «раздели на 3». И решим задачу обратным путем.

Так как при делении 28 на 3 получится дробное число, первой командой будет «вычти 2»:

28 – 2 = 26

Так как при делении 26 на 3 получится дробное число, следующей командой будет «вычти 2»:

26 – 2 = 24

Число 24 делится нацело на 3, поэтому можно выполнить команду «раздели на 3». Если сейчас выполнить вычитание, то будет использовано больше 6 команд:

24 / 3 = 8

Так как при делении 8 на 3 получится дробное число, следующей командой будет «вычти 2»:

8 – 2 = 6

Число 6 делится нацело на 3, поэтому можно выполнить команду «раздели на 3». Если сейчас выполнить вычитание, то будет использовано больше 6 команд:

6 / 3 = 2

Так как число 2 меньше 3, последней командой будет «вычти 2»:

2 – 2 = 0

Ровно за 6 команд мы получили из числа 28 число 0. Осталось изменить порядок команд на обратный и заменить названия команд на номера исходных. Таким образом, число 28 из 0 мы можем получить выполнением команд: «прибавь 2», «умножь на 3», «прибавь 2», «умножь на 3», «прибавь 2», «прибавь 2» или 121211.

Проверим, что все сделано верно:

((0 + 2) ⋅ 3 + 2) ⋅ 3 + 2 + 2 = 28

Ответ: 121211

Есть другой способ решения?

Наверх