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

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

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

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

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

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

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

Вопрос 6

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя 

след  в  виде  линии.  Чертёжник  может  выполнять  команду 

Сместиться на (a, b)  (где a, b – целые числа), перемещающую Чертёжника 

из  точки c координатами (x, y) в  точку  с координатами (x + a, y + b). Если 

числа  a,  b  положительные,  значение  соответствующей  координаты 

увеличивается; если отрицательные – уменьшается. 

Например,  если  Чертёжник  находится  в  точке  с  координатами (9, 5),  то 

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

Запись  

Повтори k раз 

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

конец 

означает,  что  последовательность  команд  Команда1  Команда2  Команда3 

повторится k раз. 

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

Повтори 3 раз 

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

конец  

На  какую  одну  команду  можно  заменить  этот  алгоритм,  чтобы  Чертёжник 

оказался в той же точке, что и после выполнения алгоритма? 

 1) Сместиться на (–9, –3) 

  

2) Сместиться на (–3, 9) 

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

  

4) Сместиться на (9, 3) 

  

Ответ:

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

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

Из рисунка видно, что правильный ответ под номером 1.

Решение (способ 2, сложение векторов):

1). подсчитываем сумму первого повтора

х=(-2+(+3)+(-4)*3)=-3*3=-9

y=(-3+2+0)*3=-1*3=-3

Ответ:сместиться(-9,-3)

Нужно выбрать тот способ решения, которым вы более владеете,и который более экономичен по времени.

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

Вопрос 14 (время решения 10 мин)

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

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

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

У исполнителя Делитель две команды, которым присвоены номера:
1. раздели на 2
2. вычти 1
Первая  из  них  уменьшает  число  на  экране  в 2  раза,  вторая  уменьшает  его
на 1.
Исполнитель работает только с натуральными числами.
Составьте  алгоритм  получения из числа 65 числа 4,  содержащий  не  более
5 команд. В ответе запишите только номера команд.

(Например, 12112 – это алгоритм:
раздели на 2
вычти 1
раздели на 2
раздели на 2
вычти 1,
который преобразует число 42 в число 4).

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

 Ответ: _____

Решение (вариант 1, «прямой ход»):

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

2)      начнем решать задачу, «отталкиваясь» от начального числа

3)      на первом шаге с помощью имеющихся команд из числа 65 можно получить 65-1=64 делить нельзя;

4)      на втором шаге из 64 можно получить 32 и 63, а из 32 – 16 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

Ответ:11112

Возможные ловушки и проблемы: ·    большую схему неудобно рисовать, в ней легко запутаться ·    не всегда можно сразу угадать нужную ветку «дерева», то есть, ту, которая быстрее всего приведет к успеху

Решение (вариант 2, «обратный ход»):

1)      нам нужно увеличить число (с 4 до 65), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях

2)      попробуем решить задачу «обратным ходом», начав с числа 65;

8)      таким образом, правильный ответ записывается снизу вверх – 11112, эта программа состоит из 5 команд.

Ответ:11112

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

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.) 

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

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

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

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

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

1.     Умножь на 2

2.     Вычти 2

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

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

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

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

Умножь на 2;  

Умножь на 2;

Вычти 2;

Вычти 2;

Умножь на 2,

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

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

1. умножь на 3

2. вычти 2

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

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

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

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

умножь на 3

умножь на 3

вычти 2

вычти 2

умножь на 3,

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

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

1.     Вычти 3

2.     Умножь на 2

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

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

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

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

Умножь на 2

Умножь на 2

Умножь на 2

Умножь на 2

Вычти 3,

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

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

1. Умножь на 2

2. Вычти 1

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

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

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

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

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Умножь на 2

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

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

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

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

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

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

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

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

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

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

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

Умножь на 2

Прибавь 1

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

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

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

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

Умножь на 2

Прибавь 1

Умножь на 2

Прибавь 1

Прибавь 1

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

http://kpolyakov.narod.ru

Вопрос 16 (время решения 5 мин)

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

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

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

Не­ко­то­рый ал­го­ритм из одной це­поч­ки сим­во­лов по­лу­ча­ет новую це­поч­ку Автомат  получает  на  вход  трёхзначное  десятичное  число. По  полученному числу строится новое десятичное число по следующим правилам. 

1. Вычисляются  два  числа –  сумма  старшего  и  среднего  разрядов,  а  также сумма среднего и младшего  разрядов заданного числа.  

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

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

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

1616  169  163  1916 1619 316  916 116 

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

Решение:

1)     Анализируем предложенные числа с целью выявления не отвечающих условию задачи: все 4-х значные числа 1616 не отвечает 2 условию, 1916 и 1619 из-за числа 19=10+9, одно слагаемое меньше 10

2)      исключаем числа 316, 916 не соответствуют пункту 2

3)    число 163 исключается, т.к. число 16 может быть получено: 8+8, 7+9, 9+7, а число 3 не получается,
Таким образом остаются числа 169, 116.
Ответ: 2