5. Анализ и построение алгоритмов

Демонстрационный вариант ЕГЭ по информатике 2021 г. задания №5

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

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

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

Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.


Демонстрационный вариант ЕГЭ 2019 г. – задание №6

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если N нечётное, справа дописывается сначала единица, а затем ноль.
Например, двоичная запись 100 числа 4 будет преобразована в 10001, а двоичная запись 111 числа 7 будет преобразована в 11110.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R – результата работы данного алгоритма.
Укажите минимальное число R, которое больше 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления


Демонстрационный вариант ЕГЭ 2018 г. – задание №6

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


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

Демонстрационный вариант ЕГЭ 2017 г. – задание №6


Демонстрационный вариант ЕГЭ 2016 г. – задание №6 а

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

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

2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

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

Ответ:


 Демонстрационный вариант ЕГЭ 2016 г. – задание №6 б

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

1. прибавь 2,
2. умножь на 5.

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

Например, программа 2121 – это программа
умножь на 5,
прибавь 2,
умножь на 5,
прибавь 2,
которая преобразует число 1 в число 37.

Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.

 


Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E, не стоящая в цепочке на первом месте. Какая из перечисленных цепочек создана по этому правилу?

1) CBE   2) ADD  3) ECE   4) EAD


Джентльмен пригласил даму в гости, но вместо кода цифрового замка своего подъезда отправил ей такое сообщение: «В последовательности 52186 все четные цифры нужно разделить на 2, а из нечетных вычесть 1. Затем удалить из полученной последовательности первую и последнюю цифры». Определите код цифрового замка.

1) 104    2) 107    3) 218    4) 401


Вася забыл пароль к Windows, но помнил алгоритм его получения из строки подсказки «23ABN12QR8N»: если последовательности символов «AB» и «QR» поменять местами, а затем из получившейся строки удалить все символы «N», то полученная последовательность и будет паролем. Определите пароль:

1) 23AB12QR8   2) 23QR12AB8   3) 23QRAB8        4) 23QR128


Пятизначное число формируется из цифр 0, 1, 3, 5, 7, 9. Известно, что число строится по следующим правилам: а) число делится без остатка на 10; б) модуль разности любых двух соседних цифр не менее 1. Какое из следующих чисел удовлетворяет всем условиям?

1) 56710                  2) 19910                     3) 75310                     4) 11110


Предлагается некоторая операция над двумя произвольными трехзначными десятичными числами:

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

Какое из перечисленных чисел могло быть построено по этому правилу?

1) 141215            2) 121514            3) 141519            4) 112112


Автомат получает на вход четырехзначное десятичное число. По этому числу строится новое число по следующим правилам

  1. Складываются первая и вторая, а также третья и четвёртая цифры
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей)

Пример. Исходное число: 8754. Суммы: 8+7 = 15; 5+4 = 9. Результат: 915.

Определите, какое из следующих чисел может быть результатом работы автомата

1) 219                      2) 118                                3) 1411                        4) 151


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

Пример. Исходные цифры: A, A, 3. Разности: A16 — A16 = 0; A16 — 316 = 10 – 3 = 7. Результат: 70. Укажите, какое из следующих чисел может быть получено в результате.

1) 131                      2) 133                                3) 212                          4) D1


Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 411.

Укажите минимальное число, в результате обработки которого, автомат выдаст число 79.


Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и третья, а также вторая и четвёртая цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 6 = 9; 1 + 5 = 6. Результат: 69.

Укажите максимальное число, в результате обработки которого, автомат выдаст число 35.


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

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

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно.

б) к этой записи справа дописывается остаток от деления количества единиц на 2.

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


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

  1. Умножь на 2
  2. Вычти 2

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

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

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

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

  • Умножь на 2;  
  • Умножь на 2;
  • Вычти 2;
  • Вычти 2;
  • Умножь на 2,

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


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

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

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


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

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

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


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

 33233241

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


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

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

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

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


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

  1. Прибавь 1
  2. Умножь на 2

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

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


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

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

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

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

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


Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. В конец записи (справа) добавляется (дублируется) последняя цифра.
3. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 14. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1110.
2. Дублируется последняя цифра, новая запись 11100.
3. Сумма цифр полученной записи 3, остаток от деления на 2 равен 1, новая запись 111001.
4. На экран выводится число 57.
Какое наименьшее число, большее 107, может появиться на экране в результате работы автомата?

Источник: onlyege