Задание 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. Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: 3. Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу: вниз влево вниз влево вверх вправо вверх Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.
4. Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды: 4. Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды: Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали. Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз. Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм: Сместиться на вектор (5,2) Сместиться на вектор (-3, 3) Повторить 3[Сместиться на вектор (1,0)] Сместиться на вектор (3, 1) На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?
5.На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 5.На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом. 1. Строится двоичная запись числа N. 2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи, если а) сумма нечетная к числу дописывается 11, б) сумма четная, дописывается 00. Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления. Источник: ЕГЭ — 2018. Досрочная волна. Вариант 1., ЕГЭ — 2018. Досрочная волна. Вариант 2.
6. Автомат обрабатывает натуральное число N по следующему алгоритму: 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.
