6-2 (базовый уровень, время – 4 мин)

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

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

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

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

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

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

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

Р-03. У исполнителя Аккорд две команды, которым присвоены номера:

1. отними 1

2. умножь на x

где x – неизвестное положительное число. Выполняя первую из них, Аккорд отнимает от числа на экране 1, а выполняя вторую, умножает это число на x.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12121 переводит число 4 в число 23. Определите значение x.

Решение (составление уравнения):

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

Вход: 4

1: 4 – 1 = 3

2: 3·x = 3x

1: 3·x – 1

2: (3·x – 1) ·x = 3x2x

1: 3x2x 1 = 23

2)      остаётся решить уравнение  или

3)      это уравнение имеет 2 корня, x1= 3 и x2= – 2,666

4)      нас интересует только целое положительное решение, поэтому ответ – 3

5)      Ответ: 3.

Решение (метод перебора):

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

2)      пусть x = 2, тогда при выполнении программы 12121 для числа 4 получаем

4 ® 3 ® 6 ® 5 ® 10 ®

что не совпадает с заданным значением 23

3)      берём следующее значение, пусть x = 3, тогда при выполнении программы 12121 для числа 4 получаем

4 ® 3 ® 9 ® 8 ® 24 ® 23

что совпадает с заданным результатом.

4)      Ответ: 3.

Ещё пример задания:

Р-01. У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

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

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

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

1.       вычти 1

2.       раздели на 2 (только для чётных чисел)

2)      получим с помощью Раздвоителя число 3 из 63 (идём в обратную сторону)

3)      будем использовать следующий (в данном случае – оптимальный) алгоритм: если число нечётное, вычитаем единицу (команда 1), потому что делить его на 2 нельзя; если число чётное, делим его на два; сверху записаны номера выполняемых команд:

      1         2         1         2        1         2      1      2

63 ® 62 ® 31 ® 30 ® 15 ® 14 ® 7 ® 6 ® 3

таким образом, выполняя программу 12121212, Раздвоитель получает число 3 из 63

4)      программу для Удвоителя (выполняющего обратную цепочку действий) запишем в обратном порядке: 21212121

5)      Ответ: 21212121

Ещё пример задания:

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

1. прибавь 3

2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

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

умножь на 4

прибавь 3

умножь на 4

прибавь 3

прибавь 3

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

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

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

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

8)      на первом шаге с помощью имеющихся команд из числа 3 можно получить 6 или 12;

9)      на втором шаге из 6 можно получить 9 и 24, а из 12 – 15 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

10)   уже чувствуется, что дерево сильно разрастается, на следующем уровне будет уже 8 вариантов, потом – 16 и т.д. (на каждом следующем уровне – в 2 раза большем, чем на предыдущем)

11)   нужно выбрать такой план дальнейшего перебора вариантов, который может быстрее всего привести к цели (числу 57)

12)   видим, что после второй операции ближе всего к результату оказалось число 48, попробуем начать анализ с этой ветки; если не получится – возьмем число 24 и т.д.

13)   ветка дерева, начиная от числа 48, построена на рисунке справа; красный крестик показывает, что полученное значение превышает 57

14)   итак, мы вышли на число 57 в результате такой последовательности команд: 22111, ее длина равна 5, что удовлетворяет условию задачи.

15)   таким образом, правильный ответ – 22111.

Возможные ловушки и проблемы:

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

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

 

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

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

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

3)      очевидно, что последней командой не может быть умножение на 4 (57 на 4 не делится), поэтому последняя команда – сложение (прибавь 3), над стрелкой записан номер команды:

4)      число 54 также не делится на 4, поэтому предыдущая команда – тоже сложение:

5)      аналогично для числа 51:

6)      число 48 делится на 4, поэтому используем умножение:

7)      наконец, добавив в начало программы еще одно умножение, получаем полную цепочку:

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

Возможные ловушки и проблемы:

·    иногда может потребоваться «откат» назад, например, если исходное число – 6, то применив деление на 4 для 12 мы «проскакиваем» его (получаем 12/4=3<6), поэтому нужно возвращаться обратно к 12 и дважды применять сложение; в этом случае ответ будет такой:

 

Почему здесь «обратный ход» лучше?:

·    обратим внимание, что когда мы «шли» в обратном направлении, от конечного числа к начальному, часто очередную операцию удавалось определить однозначно (когда число не делилось на 4)

·    это связано с тем, что среди допустимых команд есть «не всегда обратимая» операция – умножение: умножить целое число на 4 можно всегда, а разделить нацело – нет; в подобных случаях результат быстрее получается именно «обратным ходом», во время которого сразу отбрасываются невозможные варианты


Еще пример задания:

У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

Решение:

1)      важно, что числа однобайтовые – на число отводится 1 байт или 8 бит

2)      главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса:

 

 

7

6

5

4

3

2

1

0

 

?

 

0

0

1

0

1

1

0

1

= 45

 

 

 

 

0

0

 

0

1

0

1

1

0

1

0

= 90

             бит
                переноса

можно доказать, что в большинстве случаев результат этой операции – умножение числа на 2, однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна[1], поэтому мы получим остаток от деления числа 2x на 28=256

3)      попутно заметим, что при сдвиге вправо[2] в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка

4)      таким образом, фактически команда сдвинь влево означает умножь на 2

5)      поэтому последовательность команд 11221 выполняется следующим образом

Код команды

Действие

Результат

Примечание

 

 

104

 

1

умножь на 2

208

 

1

умножь на 2

160

остаток от деления 208*2 на 256

2

вычти 1

159

 

2

вычти 1

158

 

1

умножь на 2

60

остаток от деления 158*2 на 256

6)      правильный ответ – 60.

Еще пример задания:

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

      3233241

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

Решение:

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

2)      поэтому для того, чтобы не разрушиться на обратном пути, Робот должен идти точно по тому же пути в обратном направлении

3)      нарисуем путь Робота, который выполнил программу 3233241:

?

?

?

?

?

?

?

 

?

?

?

?

?

 

 

 

?

?

?

?

 

 

?

?

?

?

?

?

?

Робот начал движение из клетки, отмеченной красной точкой, и закончил в клетке, где стоит синяя точка

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

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

 

Еще пример задания:

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

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

вниз

вниз

вправо

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

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

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

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

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

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

вправо

вверх

влево

влево

вниз

вниз

вправо

вправо

вправо

вниз

влево

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

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

Еще пример задания:

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

  Вперед 4 – Кузнечик прыгает вперед на 4 единицы,

  Назад 3 – Кузнечик прыгает назад на 3 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27?

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

1)      обозначим через  количество команд «Вперед 4» в программе, а через  – количество команд «Назад 3»

2)      для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие

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

4)      из всех решений нас интересует такое, при котором  – наименьшее возможное неотрицательное (!) число

5)      представим уравнение в виде

нужно подобрать минимальное неотрицательное , при котором правая часть делится на 4

6)      дальше используем метод подбора (или перебора), начиная от 1; получаем

7)      видим, что первое , при котором  делится на 4, это  (при этом ).

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


Задачи для тренировки[3]:

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

1. вычти 2

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

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

умножь на три

вычти 2

умножь на три

вычти 2

вычти 2,

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

11121

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

1. прибавь 2

2. умножь на 3

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

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

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

121211

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

1. вычти 1

2. умножь на 3

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

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

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

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1

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

12211

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

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

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

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

Назад5

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

1.     Умножь на 2

2.     Вычти 2

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

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

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

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

Умножь на 2;  

Умножь на 2;

Вычти 2;

Вычти 2;

Умножь на 2,

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

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

1. умножь на 3

2. вычти 2

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

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

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

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

умножь на 3

умножь на 3

вычти 2

вычти 2

умножь на 3,

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

11122

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

1.     Вычти 3

2.     Умножь на 2

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

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

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

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

Умножь на 2

Умножь на 2

Умножь на 2

Умножь на 2

Вычти 3,

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

21221

 

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

1. Умножь на 2

2. Вычти 1

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

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

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

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

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Умножь на 2

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

1211

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

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

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

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

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

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

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

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

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

10

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

1.  Умножь на 2

2.  Прибавь 1

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

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

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

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

Умножь на 2

Прибавь 1

Умножь на 2

Прибавь 1

Прибавь 1

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

22112

11)   У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

171

 

12)   У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь вправо

2. прибавь 4

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд вправо, а выполняя вторую, добавляет к нему 4. Исполнитель начал вычисления с числа 191 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

16

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

1.  Вычти 1

2.  Умножь на 2

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

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

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

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

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Вычти 1

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

1222

14)   Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера:

1.  Возведи в квадрат

2.  Прибавь 1

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

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

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

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

Прибавь 1

Возведи в квадрат

Прибавь 1

Прибавь 1

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

1221

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

1.     Вычти 1

2.     Умножь на 2

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

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

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

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

Вычти 1

Умножь на 2

Умножь на 2

Вычти 1

Вычти 1,

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

2212

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

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

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

2

17)   На экране есть два окна, в каждом из которых записано по числу. Исполнитель СУММАТОР имеет только две команды, которым присвоены номера:

1.  Запиши сумму чисел в первое окно

2.  Запиши сумму чисел во второе окно

Выполняя команду номер 1, СУММАТОР складывает числа в двух окнах и записывает результат в первое окно, а выполняя команду номер 2, заменяет этой суммой число во втором окне. Напишите программу, содержащую не более 5 команд, которая из пары чисел 1 и 2 получает пару чисел 13 и 4. Укажите лишь номера команд.

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

Запиши сумму чисел во второе окно

Запиши сумму чисел в первое окно

Запиши сумму чисел во второе окно

Запиши сумму чисел в первое окно

Запиши сумму чисел в первое окно

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

22111

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

1.  Вычти 1

2.  Умножь на 3

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

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

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

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

Умножь на 3

Вычти 1

Умножь на 3

Вычти 1

Вычти 1

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

12211

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

1. прибавь 3

2. умножь на 2

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

умножь на 2

прибавь 3

умножь на 2

прибавь 3

прибавь 3,

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

121221

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

 1132432

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

142

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

 33233241

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

4144

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

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

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

Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад  4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?

Вперед4

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

вверх

влево

влево

вниз

вниз

вправо

вправо

вниз

вправо

вверх

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

2

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

вправо

вниз

вправо

вверх

влево

вверх

вверх

влево

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

2

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

вниз

влево

вниз

влево

вверх

вправо

вверх

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

1

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

вверх

влево

влево

вверх

вправо

вверх

вправо

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

3

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

 2324142

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

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

1. прибавь 2

2. умножь на 3

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

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

которая преобразует число 2 в 28).  12221

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

1. прибавь 1

2. умножь на 3

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

умножь на 3

прибавь 1

умножь на 3

прибавь 1

прибавь 1,

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

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

1.  Вычти 1

2.  Умножь на 2

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

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

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

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

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Вычти 1

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

2122

31)   Исполнитель КВАДРАТОР имеет только две команды, которым присвоены номера:

1.  Возведи в квадрат

2.  Прибавь 1

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

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

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

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

Возведи в квадрат

Прибавь 1

Возведи в квадрат

Прибавь 1

Прибавь 1

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

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

1. прибавь 1

2. умножь на 3

Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 3 числа 34, содержащей не более 5 команд, указывая лишь номера команд.

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

умножь на 3

прибавь 1

умножь на 3

прибавь 1

прибавь 1

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

33)   Исполнитель Вычислитель работает с целыми положительными однобайтными числами. Он может выполнять две команды:

1. сдвинь биты числа влево на одну позицию

2. прибавь 1

Например, число 7 (000001112) преобразуется командой 1 в 14 (000011102). Для заданного числа 14 выполнена последовательность команд 11222. Запишите полученный результат в десятичной системе счисления.  59

34)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 6 – Кузнечик прыгает вперёд на 6 единиц,

Назад 4 – Кузнечик прыгает назад на 4 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 4», чтобы Кузнечик оказался в точке 28?  2

35)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 5 – Кузнечик прыгает вперёд на 5 единиц,

Назад 3 – Кузнечик прыгает назад на 3 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21?  3

36)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 7 – Кузнечик прыгает вперёд на 7 единиц,

Назад 5 – Кузнечик прыгает назад на 5 единиц.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 5», чтобы Кузнечик оказался в точке 19?  6

37)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 10. Система команд Кузнечика:

Вперед 7 – Кузнечик прыгает вперёд на 7 единиц,

Назад 4 – Кузнечик прыгает назад на 4 единицы.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 4», чтобы Кузнечик оказался в точке 43? 4

38)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 15. Система команд Кузнечика:

Вперед 17 – Кузнечик прыгает вперёд на 17 единиц,

Назад 6 – Кузнечик прыгает назад на 6 единиц.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 6», чтобы Кузнечик оказался в точке 36? 5

39)   Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 20. Система команд Кузнечика:

Вперед 3 – Кузнечик прыгает вперёд на 3 единицы,

Назад 5 – Кузнечик прыгает назад на 5 единиц.

За какое наименьшее количество команд можно перевести Кузнечика в точку (-4)?  8

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

1. прибавь 1

2. умножь на 3

Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 4 числа 51, содержащей не более 5 команд, указывая лишь номера команд.

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

умножь на 3

прибавь 1

умножь на 3

прибавь 1

прибавь 1

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

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

1.  Прибавь 1

2.  Умножь на 2

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

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 17 число 729. 13

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

1.  Прибавь 1

2.  Умножь на 2

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

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 21 число 813. 12

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

1.  Прибавь 1

2.  Умножь на 2

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

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 19 число 629. 8

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

1.  Прибавь 1

2.  Умножь на 3

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

команду номер 2, умножает число на экране на 3. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 37 число 1013.

7

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

1.  Прибавь 1

2.  Умножь на 2

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

команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 23 число 999.

16

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

1.  Прибавь 7

2.  Раздели на 4

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

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

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

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

   Раздели на 4

Прибавь 7

Раздели на 4

Прибавь 7

Прибавь 7

которая преобразует число 20 в число 17. 12121

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

1.  Прибавь 5

2.  Умножь на 3

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

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

более 5 команд, которая из числа 3 получает число 59.  11121

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

1.   прибавь 2,

2.   умножь на 3.

Первая из них увеличивает число на экране на 2, вторая утраивает его.

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

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

1.  прибавь 1,

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

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

Запишите программу для исполнителя Квадр, которая преобразует число 5 в число 2500 и содержит не более 6 команд. Если таких программ более одной, то запишите любую из них. 11212

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

1.  прибавь 1,

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

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

Запишите программу для исполнителя Квадр, которая преобразует число 3 в число 10001 и содержит не более 6 команд. Если таких программ более одной, то запишите любую из них.

21221

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

1.   прибавь 2,

2.   умножь на 3.

Первая из них увеличивает число на экране на 2, вторая утраивает его.

Запишите порядок команд в программе преобразования числа 12 в число 122, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них. 21121

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

1.  прибавь 2,

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

Первая из этих команд увеличивает число на экране на 2, вторая – возводит в квадрат. Программа для исполнителя Квадр - это последовательность номеров команд.

Запишите программу для исполнителя Квадр, которая преобразует число 1 в число 123 и содержит не более 5 команд. Если таких программ более одной, то запишите любую из них. 12121

53)   (http://ege.yandex.ru) У исполнителя Калькулятор две команды, которым присвоены номера:

1.  отними 2

2.  раздели на 3

Выполняя первую из них, Калькулятор отнимает от числа на экране 2, а выполняя вторую, делит его на 3 (если деление нацело невозможно, Калькулятор отключается).

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

54)   (http://ege.yandex.ru) У исполнителя Калькулятор две команды, которым присвоены номера:

1.  отними 1

2.  раздели на 3

Выполняя первую из них, Калькулятор отнимает от числа на экране 1, а выполняя вторую, делит его на 3 (если деление нацело невозможно, Калькулятор отключается).

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

55)   (http://ege.yandex.ru) У исполнителя Калькулятор две команды, которым присвоены номера:

1.  отними 1

2.  раздели на 5

Выполняя первую из них, Калькулятор отнимает от числа на экране 1, а выполняя вторую, делит его на 5 (если деление нацело невозможно, Калькулятор отключается).

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

56)   (http://ege.yandex.ru) У исполнителя Калькулятор две команды, которым присвоены номера:

1.  отними 1

2.  раздели на 10

Выполняя первую из них, Калькулятор отнимает от числа на экране 1, а выполняя вторую, делит его на 10 (если деление нацело невозможно, Калькулятор отключается).

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

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

1.  отними 2

2.  раздели на 5

Выполняя первую из них, Калькулятор отнимает от числа на экране 2, а выполняя вторую, делит его на 5 (если деление нацело невозможно, Калькулятор отключается).

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

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

1.  отними 2

2.  раздели на 5

Выполняя первую из них, Калькулятор отнимает от числа на экране 2, а выполняя вторую, делит его на 5 (если деление нацело невозможно, Калькулятор отключается).

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

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

1.  прибавь 2

2.  прибавь 3

3.  умножь на 10

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, выполняя вторую – прибавляет 3, а выполняя третью – умножает его на 10.

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

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

1.  отними 1

2.  умножь на 5

Выполняя первую из них, Калькулятор отнимает от числу на экране 1, выполняя вторую –умножает его на 5. Запишите порядок команд в программе получения из числа 1 числа 99, содержащей не более 5 команд, указывая лишь номера команд.  21221

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

1.  прибавь 3

2.  умножь на 2

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, выполняя вторую –умножает его на 2. Запишите порядок команд в программе получения из числа 12 числа 123, содержащей не более 5 команд, указывая лишь номера команд. 12221

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

1.  прибавь 3

2.  умножь на 2

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, выполняя вторую –умножает его на 2. Запишите порядок команд в программе получения из числа 11 числа 103, содержащей не более 5 команд, указывая лишь номера команд. 21221

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

1.  прибавь 1

2.  умножь на 2

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

122212

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

1.   прибавь 2

2.   умножь на x

где x – неизвестное положительное число. Выполняя первую из них, Аккорд добавляет к числу на экране 2, а выполняя вторую, умножает это число на x.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12211 переводит число 1 в число 52. Определите значение x.

4

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

1.   прибавь 3

2.   умножь на x

где x – неизвестное положительное число. Выполняя первую из них, Аккорд добавляет к числу на экране 1, а выполняя вторую, умножает это число на x.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12112 переводит число 3 в число 36. Определите значение x.

2

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

1.   прибавь x

2.   умножь на 2

где x – неизвестное положительное число. Выполняя первую из них, Аккорд добавляет к числу на экране x, а выполняя вторую, умножает это число на 2.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12121 переводит число 4 в число 65. Определите значение x.

7

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

1.   вычти x

2.   умножь на 3

где x – неизвестное положительное число. Выполняя первую из них, Аккорд вычитает из числа на экране x, а выполняя вторую, умножает это число на 3.

Программа для исполнителя Аккорд – это последовательность номеров команд.

Известно, что программа 12211 переводит число 12 в число 53. Определите значение x.

5

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

1.  прибавь 2

2.  умножь на 5

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, выполняя вторую –умножает его на 5. Запишите порядок команд в программе получения из числа 2 числа 24, содержащей не более 4 команд, указывая лишь номера команд. 1211

 



[1] Используя ассемблер (язык машинных кодов с символьными командами), можно добраться до бита переноса и использовать его.

[2] Кроме логического сдвига вправо, о котором идет речь, есть еще арифметический, при котором старший бит не меняется.

[3] Источники заданий:

1.   Демонстрационные варианты ЕГЭ 2004-2013 гг.

2.   Тренировочные работы МИОО.

3.   Гусева И.Ю. ЕГЭ. Информатика: раздаточный материал тренировочных тестов. — СПб: Тригон, 2009.

4.   Крылов С.С., Лещинер В.Р., Якушкин П.А. ЕГЭ-2010. Информатика. Универсальные материалы для подготовки учащихся / под ред. В.Р. Лещинера / ФИПИ. — М.: Интеллект-центр, 2010.

5.   Якушкин П.А., Ушаков Д.М.  Самое полное издание типовых вариантов реальных заданий ЕГЭ 2010. Информатика.  — М.: Астрель, 2009.

6.   М.Э. Абрамян, С.С. Михалкович, Я.М. Русанова, М.И. Чердынцева. Информатика. ЕГЭ шаг за шагом. - М.: НИИ школьных технологий, 2010.

7.   Самылкина Н.Н., Островская Е.М. ЕГЭ 2011. Информатика. Тематические тренировочные задания. — М.: Эксмо, 2010.