Разбор задач ЕГЭ. Анализ и построение алгоритмов для исполнителей. В1

Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.
Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.
(Например, программа 21211 это программа
умножь на 3
вычти 1
умножь на 3
вычти 1
вычти 1
которая преобразует число 1 в 4.)

Задача 1.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 16 к числу 3, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.
1) Число 16 не делится на 3, значит, оно получено вычитанием единицы из числа 17: 16 = 17 - 1 (команда 1).
Повторим рассуждение для числа 17: 17 = 18 - 1 (команда 1).
2) Т. к. мы хотим получить не более 5 команд, то для получения числа 18 выгодно использовать умножение: 18 = 6 * 3 (команда 2).
Для числа 6 применяем второе рассуждение: 6 = 2 * 3(команда 2), а число 2 получено как 2 = 3 - 1 (команда 1).
Ответ: 12211.

Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 5 – Кузнечик прыгает вперёд на 5 единиц,
Назад 3 – Кузнечик прыгает назад на 3 единицы.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21?

Задача 2.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Обозначим через количество команд «Вперед 5» в программе, а через – количество команд «Назад 3», причём и могут быть только неотрицательными целыми числами.
Для того, чтобы КУЗНЕЧИК попал в точку 21 из точки 0, должно выполняться условие:
Представим его в виде:
5*х-3*у=21
5*х=21+3*у
Из последнего уравнения видно, что правая часть должна делиться на 5.
Из всех решений нас интересует такое, при котором – наименьшее возможное число.
Используя метод подбора находим: .
Ответ: 3

Задача 3.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:
вверх
влево
влево
вниз
вниз
вправо
вправо
вниз
вправо
вверх
Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

Задача 3.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
2 команды вверх + 3 команды вниз = 1 команда вниз.
2 команды влево + 3 команды вправо = 1 команда вправо.
Чтобы вернуться назад, надо использовать 2 команды:
вверх
Влево
Ответ 2.

Задача 4.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:
Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.
Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.
Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:
Сместиться на вектор (5,2)
Сместиться на вектор (-3, 3)
Повторить 3[Сместиться на вектор (1,0)]
Сместиться на вектор (3, 1)

Задача 4.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?
Решение.
Здесь нужно сложить смещение по Х и по У как при работе с векторами.
По X: 5-3+3*1+3=8 абсолютное смещение по X
По Y: 2+3+3*0+1=6 абсолютное смещение по Y
Расстояние от точки до точки находим по формуле :
Ответ 10.

Задача 5.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N – Кузнечик прыгает вперед на N единиц
Назад M – Кузнечик прыгает назад на M единиц
Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад 4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?

Задача 5.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N – Кузнечик прыгает вперед на N единиц
Назад M – Кузнечик прыгает назад на M единиц
Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад 4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?
Решение.
Команд «Назад» было 8, команд «Вперёд» 12. Команды «Назад» будем рать с минусом.
Посчитаем абсолютное смещение:
8*(-4)+12*3 = -32+36 = 4.
Можно осуществить данное смещение одной командой: Ответ: Вперёд 4
Обратите внимание на запись ответа!

Задача 6.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

Задача 6.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
Решение.
Если в старшем разряде двоичного числа нет единицы, то команда 1 удваивает число, если единица есть (т. е. десятичное число не меньше 128), то выводится остаток от деления удвоенного числа на 256. Таким образом, получим следующее:
1: 91 => 182,
1: 182 => 108 (остаток от 364 / 256 ),
2: 108 => 107,
1: 107 => 214,
1: 214 => 172 (остаток от 428 / 256 ),
2: 172 => 171.
Ответ: 171.
Число одноайтовое, т.е. содержит всегда только 8 разрядов. При смещении происходит следущее: было 01011011, стало 10110110, затем 01101100, проверьте первые две команды.

Вопросы.
ИНФОРМАТИКА
2014г. Кирсанов Илья Андреевич ©
На экране есть два окна, в каждом из которых записано по числу. Исполнитель СУММАТОР имеет только две команды, которым присвоены номера:
1. Запиши сумму чисел в первое окно
2. Запиши сумму чисел во второе окно
Выполняя команду номер 1, СУММАТОР складывает числа в двух окнах и записывает результат в первое окно, а выполняя команду номер 2, заменяет этой суммой число во втором окне. Напишите программу, содержащую не более 5 команд, которая из пары чисел 1 и 2 получает пару чисел 13 и 4. Укажите лишь номера команд.
Например, программа 21211 – это программа:
Запиши сумму чисел во второе окно
Запиши сумму чисел в первое окно
Запиши сумму чисел во второе окно
Запиши сумму чисел в первое окно
Запиши сумму чисел в первое окно
которая преобразует пару чисел 1 и 0 в пару чисел 8 и 3.
Ответ: 22111