Исполнители. Вопросы:6, 14, 20.1

Тема:  Поиск алгоритма минимальной длины для исполнителя.

Что нужно знать:

·    каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом

·    исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

Характеристики исполнителя:

•  среда "обитания" - обстановка, в которой действует исполнитель;
•   СКИ - Система Команд Исполнителя - набор команд, понятных исполнителю

Этой теме посвящено три вопроса. 

Часть 1. Вопрос 6.

Первый способ:

Начальные координаты (0,0)

Первая серия смещений:

После первого смещения (-2,-3)

После второго - (3-2, 2-3)=(1,-1)

После третьего (-4+1,0-1)=(-3,-1)

Вторая серия смещений:

После первого смещения (-2-3, -3-1)=(-5,-4)

После второго - (3-5, 2-4)=(-2,-2)

После третьего (-4-2,0-2)=(-6,-2)

Третья серия смещений:

После первого смещения (-2-6,-3-2)=(-8,-5)

После второго - (3-8, 2-5)=(-5,-3)

После третьего (-4-5,0-3)=(-9,-3)

После всех смещений координаты точки -9,-3, из предложенных вариантов это соответствует первому ответу 1)

Второй способ:

Значения векторов по х складываем и умножаем на 3 х=(-2+3-4)*3=-9

То же проделывеам с координатами точки по y=(-3+2+0)*3=-3

Ответ (-9,-3)

Разбор похожих заданий с роботом

Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную

Решение (способ 1, моделирование движения Робота):

1)      отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет

2)      можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота:

1)      поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке):

вниз вниз вправо

2)      есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз

3)      таким образом, ответ – 3.

Решение (способ 2, анализ программы):

1)      можно решить задачу без повторения движений Робота

2)      обратим внимание, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают  Робота, поэтому все такие пары можно выкинуть из программы

3)      поскольку стенок нет, все равно где стоят парные команды в программе, вычеркиваем их:

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

4)      смотрим, какие команды остались (они отмечены желтым маркером), их всего 3

5)      таким образом, ответ – 3.

Задачи для тренировки

1)      Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:

Сместиться на вектор (а, Ь) – исполнитель  перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по  вертикали.

Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:

Сместиться на вектор (5,2)

Сместиться на вектор (-3, 3)

Повторить 3[Сместиться на вектор (1,0)]

Сместиться на вектор (3, 1)

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

2)      Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

влево
вверх
вверх
влево
вниз
вправо
вправо
вправо

Укажите наименьшее возможное число команд в программе, Робота из той же начальной клетки в ту же конечную.

3)      Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вверх

влево

влево

вниз

вниз

вправо

вправо

вниз

вправо

вверх

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

4)      Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вправо

вниз

вправо

вверх

влево

вверх

вверх

влево

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

5)      Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вниз

влево

вниз

влево

вверх

вправо

вверх

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

Часть 2. Вопрос 14

Первый способ решения.

1) 65-1=64 (2)

2)64:2=34 (1)

3)32:2=16 (1)

4)16:2=8 (1)

5) 8:2=4 (1)

Ответ: 21111

Второй способ решения

Его можно использовать в более сложных случаях

Действия производятся в обратном порядке от результата:

1) 4*2=8 (1)

2) 8*2=16 (1)

3) 16*2=32 (1)

4) 32*2=64 (1)

5) 64+1=65 (2)

Порядок действий записываем снизу вверх

Ответ: 21111

Задачи для тренировки

1)      У исполнителя Утроитель две команды, которым присвоены номера:

1. вычти 2

2. умножь на три

Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:

умножь на три

вычти 2

умножь на три

вычти 2

вычти 2,

которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.)

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

1. прибавь 2

2. умножь на 3

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

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

которая преобразует число 1 в 19).

3)      У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:

1. вычти 1

2. умножь на 3

Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.

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

(Например, программа 21211 это программа

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1

которая преобразует число 1 в 4.)

4)      Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:

Вперед N (Кузнечик прыгает вперед на N единиц);

Назад M (Кузнечик прыгает назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

5)      Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

1.     Умножь на 2

2.     Вычти 2

Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя

команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не

более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.

Например, программа 11221 – это программа:

Умножь на 2;  

Умножь на 2;

Вычти 2;

Вычти 2;

Умножь на 2,

которая преобразует число 5 в число 32.

6)      Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

1. умножь на 3

2. вычти 2

Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 3, а выполняя

команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не

более 5 команд, которая из числа 1 получает число 23. Укажите лишь номера команд.

Например, программа 11221 – это программа:

умножь на 3

умножь на 3

вычти 2

вычти 2

умножь на 3,

которая преобразует число 1 в число 15.

7)      Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

1.     Вычти 3

2.     Умножь на 2

Выполняя команду номер1, КАЛЬКУЛЯТОР вычитает из числа на экране 3, а выполняя

команду номер 2, умножает число на экране на 2. Напишите программу, содержащую не

более 5 команд, которая из числа 5 получает число 25. Укажите лишь номера команд.

Например, программа 22221 – это программа:

Умножь на 2

Умножь на 2

Умножь на 2

Умножь на 2

Вычти 3,

которая преобразует число 1 в число 13.

8)      Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

1. Умножь на 2

2. Вычти 1

Выполняя команду номер 1, КАЛЬКУЛЯТОР умножает число на экране на 2, а выполняя

команду номер 2, вычитает из числа на экране 1. Напишите программу, содержащую не

более 4 команд, которая из числа 7 получает число 52. Укажите лишь номера команд.

Например, программа 12121 - это программа:

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Умножь на 2

которая преобразует число 5 в число 34.
http://kpolyakov.spb.ru