Тема «Алгоритмы и исполнители»
Решение задач с исполнителями: Калькулятор, Квадратор
Пример 1 . У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 2 числа 26, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:
умножь на 3
прибавь 1
прибавь 1,
которая преобразует число 1 в 14).
Решение
Будем решать задачу с конца.
1) Число 26 не делится на 3, значит, оно получено прибавлением единицы к числу 25: 26 = 25 + 1 (команда 1).
Повторим рассуждение для числа 25: 25 = 24 + 1 (команда 1).
2) Т. к. мы хотим получить не более 6 команд, то для получения числа 24 выгодно использовать умножение:
24 = 8 * 3 (команда 2).
Для числа 8 применяем первое рассуждение: 8 = 7 + 1(команда 1),
повторяем его для 7: 7 = 6 + 1 (команда 1),
а для числа 6 применем рассуждение 2): 6 = 2 * 3(команда 2).
Тогда окончатльно получаем ответ: 211211
Ответ: 211211
Пример 2 . Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера:
1. Возведи в квадрат
2. Прибавь 1
Выполняя команду номер 1, КВАДРАТОР возводит число на экране в квадрат, а выполняя
команду номер 2, прибавляет к этому числу 1. Напишите программу, содержащую не
более 4 команд, которая из числа 1 получает число 17. Укажите лишь номера команд.
Например, программа 12122 – это программа:
Возведи в квадрат
Прибавь 1
которая преобразует число 1 в число 6.
Решение.
Будем решать задачу с конца .
1) Число 17 не является квадратом, значит, оно получено добавлением единицы к числу 16: 17 = 16 + 1 (команда 2).
Повторим рассуждение для числа 25: 25 = 27 - 2 (команда 2).
2) Т. к. мы хотим получить не более 4 команд, то для получения числа 16 возведём в квадрат 4: 16 = 42 (команда 1).
Повторим рассуждение 2) для числа 4: 4 = 22 (команда 1), а для числа 2 применим рассуждение 1): 2 = 1 + 1 (команда 2).
Тогда окончательно получаем ответ: 2112.
Ответ: 2112
Решение задач с графическими исполнителями
Пример 1 Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:
вверх
влево
вниз
вправо
Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.
Решение .
Задачу можно решить, повторив все движения Робота на бумаге. Затем соединить начальную клетку и конечную клетку пути Робота, используя имеющиеся команды, и посчитать их количество.
Заметим, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают Робота, поэтому все такие пары можно выкинуть из программы, вдобавок, поскольку стенок нет, все равно где стоят парные команды в программе.
Вычеркунв все пары, видим, что остались только команды вниз, вправо. Их две.
Ответ: 2.
Пример 2 Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:
Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.
Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.
Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:
Сместиться на вектор (5,2)
Сместиться на вектор (-3, 3)
Повторить 3[Сместиться на вектор (1,0)]
Сместиться на вектор (3, 1)
На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?
Пояснение.
Конечная точка будет обладать координатами по оси x и y. Эти координаты можно складывать независимо друг от друга.
Найдём значение x: 5 - 3 + 1 + 1 + 1 + 3 = 8.
Найдём значение y: 2 + 3 + 1 = 6.
Расстояние от начала координат находится по формуле: , поэтому
.
Ответ: 10.
Пример 3 Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N – Кузнечик прыгает вперед на N единиц
Назад M – Кузнечик прыгает назад на M единиц
Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад 4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?
Обозначим через количество команд «Вперед 3» в программе, а через – количество команд «Назад 4», причём может быть только неотрицательным целым числом.
Всего кузнечик сделал х+х – 4=20 команд. Отсюда найдём х=12. Посчитаем, в какую точку попадёт Кузнечик после выполнения указанных команд:
3*12-4*(12-4)=36-32=4
В эту точку можно попасть из исходной, выполнив команду "Вперед 4".
Ответ: Вперед 4.
Графические исполнители с препятствием
Пример 1 Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
2324142
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
Если робот пойдёт назад тем же путём, каким пришёл в конечную клетку, то он точно не разрушится. Группа команд 3241 круговая, поэтому её можно откинуть. До конечной клетки робот прошёл путём 242. Значит, чтобы попасть обратно, ему нужно заменить команды на противоположные (131) и записать их справа налево: 131.
Ответ: 131.
