Исполнители

 

Задания 6. Алгоритм для конкретного исполнителя с фиксированным набором команд

 

Задача 1. Исполнитель Чертёжник  перемещается на координатной плоскости, оставляя за собой след в виде линии. Чертёжник  может выполнять команду Сместиться на (a, b), где (a, b – целые числа), перемещающую Чертёжника из точки с координатами (х, у)  в точку (х + a, у + b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные – уменьшается.

Например, Чертёжник находится в точке с координатами (3,1), то команда Сместиться на (1,-2) переместит Чертёжника в точку (4,-1).

Запись

Повтори k раз

Команда 1 Команда 2 Команда 3

Конец

Означает, что последовательность команд Команда 1 Команда 2 Команда 3 повторится k раз.

 

     Чертёжнику был дан для исполнения следующий алгоритм

     Повтори 3 раза

         Сместиться на (1, 1)    Сместиться на (2, 2)     Сместиться на (1, -3)

     конец

Какую команду надо выполнить Чертежнику, чтобы вернуться в исходную точку, из которой он начал движение?

     1)  Сместиться на (12, 0)                       2)  Сместиться на (0, 12)                    3)  Сместиться на (0, -12)                 4)  Сместиться на (-12, 0)

 

Решение: После первого прохода   Сместиться на (1, 1)    Сместиться на (2, 2)     Сместиться на (1, -3)

Чертежник окажется в точке (4;0) - просуммируйте значения по х, а затем по у. Следовательно, повторив движения 3 раза он окажется в точке (12; 0). Чтобы вернуться в исходную точку, ему нужно выполнить команду 4.

Ответ: 4

 

 

Задача 2. Исполнитель Черепашка, перемещаясь на экране компьютера, оставляет след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды:

       ВПЕРЕД  n (где n – целое число), вызывающая передвижение Черепашки на n шагов в направлении движения.

       НАПРАВО m   (где m – целое число), вызывающая изменение движения на m градусов по часовой стрелке.

      Запись  ПОВТОРИ k [Команда 1 Команда 2 Команда 3] означает, что последовательность команд в скобках повторится k раз

     Черепашке был задан для исполнения следующий алгоритм:

ПОВТОРИ 6  [НАПРАВО 60  ВПЕРЕД  15]

      Какая фигура появится на экране?

     1) правильный пятиугольник           2) правильный треугольник     3) правильный 6-угольник      4) правильный 12-угольник

 

 

Решение: Вспомним, что выпуклый многоугольник называется правильным, если у него все стороны равны и все углы равны.

Рассмотрим группу команд в скобках: [НАПРАВО 60  ВПЕРЕД  15]

Черепашка должна поворачиваться в одном направлении – НАПРАВО, на один и тот же угол и прочерчивает отрезки одинаковой длины. Эти действия Черепашка совершит 6 раз.

После исполнения алгоритма Черепашка совершит поворот на 6 * 60 = 360 градусов.

Известно, что сумма внешних углов многоугольника = 3600. Следовательно, должна получиться замкнутая ломаная, образующая правильный многоугольник, состоящий из 6 равных сторон.

 

 

Ответ: 3

 

Задания 14. Простой линейный алгоритм для формального исполнителя

 

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

             1. вычти 3

             2. умножь на 4

Например, программа 21211 – это программа, содержащая команды:

    умножь на 4

    вычти 3

    умножь на 4

    вычти 3

    вычти 3

Преобразует число 5 в число 62.

 

Запишите порядок команд в программе получения из числа 2 числа 500, содержащей не более 5 команд, указывая лишь номера команд.

 

Решение:

2 * 4 = 8                

8 * 4 = 32

32 * 4 = 128

128 - 3  = 125

125 * 4 = 500

 

Ответ: 22212

 

 

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

1. вычти 1

2. возведи в квадрат 

Первая из них уменьшает число на экране на 1, вторая возводит его во вторую степень. Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 5 числа 80, содержащий не более 5 команд.

В ответе запишите только номера команд.  Если таких алгоритмов более одного, то запишите любой из них.

 

 Решение:

Заметим, что 81 = 92. Из числа 5 число 9 можно получить последовательностью команд 112. Следовательно, искомый алгоритм: 11221.

 

Ответ: 11221

 

Задания 16. Алгоритм, записанный на естественном языке, обрабатывающий цепочки символов или списки

 

Задача 5. Некоторый алгоритм изодной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она нечётна, то удаляется средний символ цепочки, а если чётна, то в начало цепочки добавляется символ Л. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А — на Б, Б — на В и т. д., а Я — на А). Получившаяся таким образом цепочка является результатом работы алгоритма.

Например, если исходной была цепочка РУКА, то результатом работы алгоритма будет цепочка МСФЛБ, а если исходной была цепочка СОН, то результатом работы алгоритма будет цепочка ТО.

Дана цепочка символов РОГ. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т. е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

 

Решение: Применим алгоритм: РОГ (нечётное) → РГ → СД. Применим его ещё раз: СД (чётное) → ЛСД → МТЕ.

Ответ: МТЕ

 

Задача 6. Автомат получает на вход четырёхзначное десятичное число. По полученному числу строится новое десятичное число по следующим правилам.

1. Вычисляются два числа — сумма первой и второй цифр и сумма третьей и четвёртой цифр заданного числа.

2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей). 

 

             Пример. Исходное число: 2177. Поразрядные суммы: 3, 14. Результат: 314. 

 

Определите, сколько из приведённых ниже чисел могут получиться в результате работы автомата. 

        1915     20     101    1213    1312    312    1519    112    1212 

В ответе запишите только количество чисел.

 

Решение: Проанализируем каждое число.

Число 1915 не может быть результатом работы автомата, поскольку число 19 невозможно получить сложением двух цифр.

Число 20 не может быть результатом работы автомата, поскольку полученные два числа записываются друг за другом в порядке неубывания.

Число 101 не может быть результатом работы автомата, поскольку  первая его часть − 1, а вто­рая − 01 − это не число.

Число 1213 может быть результатом работы автомата, в этом случае исходное число могло быть 6667.

Число 1312 не может быть результатом работы автомата, поскольку  полученные два числа записываются друг за другом в по­рядке неубывания.

Число 312 может быть результатом работы автомата, в этом случае исходное число могло быть 2166.

Число 1519 не может быть результатом работы автомата, поскольку числа записываются в порядке неубывания, а число 19 невозможно получить сложением двух цифр.

Число 112 может быть результатом работы автомата, в этом случае исходное число могло быть 1011.

Число 1212 может быть результатом работы автомата, в этом случае исходное число могло быть 6666.

Ответ: 4