Автоматы (алгоритмизация)

Задание 5. Алгоритмы, автоматы

5-е задание:  «Анализ алгоритмов и исполнители» Уровень сложности  — базовый, Требуется использование специализированного программного обеспечения  — нет, Максимальный балл  — 1, Примерное время выполнения  — 4 минуты.    Проверяемые элементы содержания:  Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд

Типичные ошибки и рекомендации по их предотвращению:

• "Как и в других заданиях базового уровня сложности, источником ошибок служит недостаточная внимательность и отсутствие или поверхностность самостоятельной проверки полученного ответа"

• Что нужно знать :
• сумма двух цифр в десятичной системе счисления находится в диапазоне от 0 до 18 (9+9)
• в некоторых задачах нужно иметь представление о системах счисления (могут использоваться цифры восьмеричной и шестнадцатеричной систем счисления)
• бит чётности – это дополнительный контрольный бит, который добавляется к двоичному коду так, чтобы количество единиц в полученном двоичном коде стало чётным; если в исходном коде уже было чётное количество единиц, дописывается 0, если нечётное – дописывается 1.
• при добавлении к двоичной записи числа нуля справа число увеличивается в 2 раза
• чтобы отбросить последнюю цифру в двоичной записи, нужно разделить число на 2 нацело (остаток отбрасывается

Таблицы соответствия 8 и 16 систем счисления систем

Выбор кода при неиспользуемых сигналах

• 1 . На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1.  Строится двоичная запись числа N. 2.  К этой записи дописываются справа ещё два разряда по следующему правилу:    а)  складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа).
• Например, запись 11100 преобразуется в запись 111001;
•   б)  над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число  N , для которого результат работы данного алгоритма  больше числа 77 .  В ответе это число запишите в десятичной системе счисления.

2. Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 10. Система команд Кузнечика:   Вперед 7  – Кузнечик прыгает вперёд на 7 единиц, Назад 4  – Кузнечик прыгает назад на 4 единицы.   Какое наименьшее количество раз должна встретиться в программе команда «Назад 4», чтобы Кузнечик оказался в точке 43?

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

вниз

влево

вниз

влево

вверх

вправо

вверх

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

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

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

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

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

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

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

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

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

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

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

5.На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи, если

а) сумма нечетная к числу дописывается 11,

б) сумма четная, дописывается 00.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Источник: ЕГЭ — 2018. Досрочная волна. Вариант 1., ЕГЭ — 2018. Досрочная волна. Вариант 2.

6. Автомат обрабатывает натуральное число  N  по следующему алгоритму:

1. Строится двоичная запись числа  N .

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число  N  = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа  N : 1101.

2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.

3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4. На экран выводится число 54.

Какое наименьшее число, большее 93, может появиться на экране в результате работы автомата?

7.Автомат обрабатывает натуральное число  N  по следующему алгоритму: 1. Строится двоичная запись числа  N . 2. К этой записи дописываются справа ещё два разряда по следующему правилу: если  N  чётное, в конец числа (справа) дописывается 10, в противном случае справа дописывается 01. Например, двоичная запись 1001 числа 9 будет преобразована в 100101. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа  N ) является двоичной записью числа — результата работы данного алгоритма. Укажите максимальное число  R , которое не превышает 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления. Источник: ЕГЭ по информатике 28.05.2018. Основная волна, вариант А. Имаева — «Котолис».

8.На вход алгоритма подаётся натуральное число  N . Алгоритм строит по нему новое число следующим образом. 1) Строится двоичная запись числа  N . 2) К этой записи дописываются справа ещё два разряда по следующему правилу: если  N  чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа  N ) является двоичной записью числа — результата работы данного алгоритма. Укажите максимальное число  N , для которого результат работы алгоритма будет меньше 134. В ответе это число запишите в десятичной системе счисления. Источник: ЕГЭ — 2020. Досрочная волна. Вариант 2.

9.У исполнителя Калькулятор две команды, которым присвоены номера: 1. возведи в квадрат, 2. прибавь 1.  Первая из них возводит число на экране в квадрат, вторая увеличивает его на 1. Запишите порядок команд в программе, которая преобразует число 1 в число 10 и содержит не более 4 команд. Указывайте лишь номера команд. (Например, программа  2122  — это программа прибавь 1, возведи в квадрат, прибавь 1, прибавь 1.  Эта программа преобразует число 3 в число 18.)

10.У исполнителя Калькулятор1 две команды, которым присвоены номера: 1. прибавь 1, 2. умножь на 5. Выполняя первую из них, Калькулятор1 прибавляет к числу на экране 1, а выполняя вторую, умножает его на 5. Программа для этого исполнителя — это последовательность номеров команд. Например, программа 121 задаёт такую последовательность команд: прибавь 1, умножить 5, прибавь 1, Эта программа преобразует, например, число 7 в число 41. Запишите в ответе программу, которая содержит не более шести команд и переводит число 3 в число 506.

11.У исполнителя Аккорд-4 две команды, которым присвоены номера:   1. вычти 1 2. умножь на 4  Выполняя первую из них, Аккорд-4 вычитает из числа на экране 1, а выполняя вторую, умножает это число на 4. Запишите порядок команд в программе, которая содержит не более пяти команд и  преобразует число 5 в число 62.  Если таких программ более одной, то запишите любую из них. В ответе указывайте лишь номера команд. Так, для программы умножь на 4 вычти 1 вычти 1 нужно написать: 211. Эта программа преобразует, например, число 7 в число 26.

12.Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам: 1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа. 2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей). Пример. Исходное число: 2366. Суммы: 2 + 3 = 5; 6 + 6 = 12. Результат: 512. Укажите наибольшее число, в результате обработки которого автомат выдаст число 117.