Исполнители алгоритмов

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

  1. вычти 1;
  2. умножь на 3;

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

Например, 12211 - программа:

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

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

Решение: Поиск программы лучше начать с конца - результата выполнения программы. 17 не делиться на 3, но ближайшее большее число 18 - делится. Следовательно последняя команда в программе будет 1. Число 18 можно получить умножив 6 на 3, число 6 - умножив 2 на 3, следовательно последние три команды программы - 221. Число 2 можно получить, если дважды вычесть 1 из исходного числа 4, Вся программа будет выглядеть: 11221. Программа содержит 5 команд - условие задачи выполнено. Ответ: 11221

 

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

  1. прибавь 1;
  2. умножь на 3;

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

Решение: Для решения задачи составим таблицу, в которой в одном столбце число, а во втором- количество программ, которыми можно это число получить:

Таблица количества программ

Ответ: 15

 

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

Вперед n, где n - целое число, вызывающая передвижение черепашеки на n шагов в направлении движения;

Направо m, где m - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.

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

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

Повтори 5 [Повтори 2 [Вперед 40 Направо 60 Вперед 40 Направо 120] Направо 90]

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

Варианты ответа

Решение: В результате исполнения внутреннего цикла черепашка рисует ромб, так как за один шаг она рисует две линии одинаковой длины, при этом поворачивается на 180 градусов. За второй шаг рисуются линии в обратном направлении. Согласно внешнему циклу черепашка рисует ромб пять раз, при этом за 4 шага она поворачивается на 360 градусов, а пятый ромб будет нарисован поверх первого. Ответ: 3

 

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

11313142

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

Решение: Отразим путь, который проделал Робот, графически:

Путь робота

Буквой A обозначим клетку, в которой находился Робот до выполнения программы, а буквой B - клетку, в которой оказался после. Из рисунка видно, что вернуться из точки B в точку A можно по прорамме: вниз, влево, вниз, вниз, то есть 2422. Ответ: 2422

 

Задача: Дана система команд исполнителя, "живущего" в прямоугольном лабиринте на клетчатой плоскости.

Поле для робота

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

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

сверху свободно

снизу свободно

слева свободно

справа свободно

Если Робот начнет движение в сторону стены, то он разрушится.

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

НАЧАЛО

ПОКА справа свободно ДЕЛАТЬ вправо

ПОКА снизу свободно ДЕЛАТЬ ввниз

ПОКА слева свободно ДЕЛАТЬ влево

ПОКА сверху свободно ДЕЛАТЬ вверх

КОНЕЦ

В ответе запишите число - количество таких клеток, а далее, через запятые, их адреса (сначала латинская буква столбца, а затем цифра строки, например, нижний левый угол лабиринта имеет адрес A1).

Решение: Согласно последнему циклу программы Робот должен остановится в клетке, которая ограничена стеной сверху, при этом в лабиринте он должен описать прямоугольник. Проверяем все такие клетки: клетки верхнего ряда, B6, H6, C5, D4, E2, G1. Только начав движение из клетки A8, Робот остановится в ней же после выполнения программы. Ответ: 1,A8

 

Задача: Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: Вперед N (Кузнечик прыгает на N единиц вперед); Назад M (Кузнечик прыгает на M единиц назад). Переменные N и M могут принимать любые целые значения. Известно, что Кузнечик выполнил программу из 51 команды, в которой команд Назад 2 в 2 раза больше, чем команд Вперед 3, Других команд в программе не было, На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

Решение: Вычислим, сколько каких команд выполнил Кузнечик. Получаем: 51 / 3 = 17. Команд Вперед было 17, а Назад 2 было 34. Кузнечик прыгнул вперед на 17 ⋅ 3 = 51 единиц, а назад на 34 ⋅ 2 = 68. Тем самым он оказался на 68 - 51 = 17 единиц назад от первоначальной точки. Последовательность команд в алгоритме в данном случае не имеет значения. Ответ: Назад 17

 

Задача: Цепочка из трех бусин формируется по следующему правилу: на первом месте в цепочке стоит одна из бусин М, Н, О. На втором - одна из бусин Л, М, 0. На третьем  месте - одна из бусин Л, М, 0, не стоящая в цепочке на первои или на втором месте.

Какая из следующих цепочек создана по этому правилу:

1) НОН       2) НОМ        3) МНЛ       4) МНО

Решение: Можно решать задачу, составляя все варианты цепочек, но эффективней решать методом исключений. Правилу первой буквы удовлетворяют все цепочки. В 3-ей и 4-ой цепочках нарушено правило второй буквы. В 1-ой цепочке нарушено правило третьей буквы. Ответ: 2

 

Задача: Цепочки символов (строки) создаются по следующему правилу.

Первая строка состоит из одного символа - цифры 1.

Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число - номер строки по порядку ( на i-ом шаге дописывается число i). 

Вот первые 4 строки, созданные по этому правилу*

1) 1

2) 112

3) 1121123

4) 112112311211234

Какая цифра стоит в восьмой строке на 250-м месте (считая слева направо)?

Решение: Найдем длину восьмой строки, По условию длина каждой последующей строки увеличивается в 2 раза по сравнению с предыдущей плюс еще один символ. Длина строк составит:

1) 1

2) 1 ⋅ 2 + 1 =3

3) 3 ⋅ 2 + 1 = 7

4) 7 ⋅ 2 + 1 =15

5) 15 ⋅ 2 + 1 = 31

6) 31 ⋅ 2 = 1 = 63

7) 63 ⋅ 2 + 1 = 127

8) 127 ⋅ 2 + 1 = 255

Так как требуется найти 250-ую цифру, а всего в строке - 255, то искомая цифра шестая с конца. На каждом шаге к строке добавляется номер строки, поэтому последние 8 цифр будут выглядеть так: 12345678, Шестая цифра с конца - 3. Ответ: 3.

 

Задача: Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А) заменить (v, w). Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150. Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку. 

Б) нашлось (v). Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.

Цикл
    ПОКА условие
        последовательность команд
    КОНЕЦ ПОКА
выполняется, пока условие истинно.

 В конструкции

    ЕСЛИ условие
        ТО команда1
        ИНАЧЕ команда2
    КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 68 идущих подряд цифр 8? В ответе запишите полученную строку.

НАЧАЛО
 ПОКА нашлось (222) ИЛИ нашлось (888)
    ЕСЛИ нашлось (222
        ТО заменить (222, 8)
        ИНАЧЕ заменить (888, 2)
    КОНЕЦ ЕСЛИ
 КОНЕЦ ПОКА
 КОНЕЦ

Решение: Первые три шага цикла алгоритма заменят группу из 9-ти восьмерок на 222, а четвертый шаг заменит 222 на 8. Поэтому 7 групп по девять восьмерок заменяться на семь восьмерок и в итоге в строке их останется 7 + 68 - 9 ⋅ 7 = 12. Из этих 12-ти восьмерок девять опять будут заменены на одну восьмерку - останется в строке их четыре. Три восьмерки заменятся на двойку - получится 28. Ответ: 28

 

Задача: Два игрока играют в следующую игру:

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

Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре - первый или второй игрок.

Решение: Для решения задачи составим дерево игры, что удобней сделать в виде таблицы. В первом столбце - начальная позиция, в остальных столбцах - возможные варианты ходов игроков.

Таблица - дерево игры в камешки

Рассмотрим во втором столбце - четыре варианта хода 1-го игрока. Утроить количество камней в первой и во второй кучах 1-ый ирок не может, потому что при правильных ходах 2-го игрока (оранжевый фон ячейки таблицы) он проигрывает. Если он утроит количество камней в третьей куче, то он проиграет при первом же ходе 2-го игрока. 1-ый игрок выиграет при любом ответе 2-го игрока, если первым своим ходом добавит в каждую из куч по 3 камня. Ответ: 1-ый игрок

 

Задачи для самостоятельного решения