Разбор задач из ЕГЭ №6 по информатике

6. Выполнение и анализ простых алгоритмов

Задачи

  1. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
    1. Складываются отдельно первая и вторая, а также вторая и третья цифры.
    2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.
    Пример. Исходное число: 872. Суммы: 8 + 7 = 15; 7 + 2 = 9. Результат: 915.
    Укажите наименьшее число, при обработке которого автомат выдаёт
    результат 812. [Я. Н. Зайдельман, М. А. Ройтберг, Информатика и ИКТ. Подготовка к ЕГЭ в 2019 году. Диагностические работы. ФГОС.— М.: МЦНМО, 2019., стр 9, №6]
    Решение:
    Результат работы автомата – это число составленное из сумм цифр исходного числа, записанные в порядке неубывания, следовательно 812 можно единственным образом разбить на две суммы 8 и 12. В каждой из этих сумм должно присутствовать одинаковое слагаемое.
    8 = a + b = 1 + 7.
    12 = b + c = 7 + 5.
    Искомое число – 175.
    Ответ: 175.
  2. Автомат получает на вход четырёхзначное число (число не может начинаться с нуля). По этому числу строится новое число по следующим правилам.
    1. Складываются отдельно первая и вторая, вторая и третья, третья
    и четвёртая цифры заданного числа.
    2. Наименьшая из полученных трёх сумм удаляется.
    3. Оставшиеся две суммы записываются друг за другом в порядке неубывания без разделителей.
    Пример. Исходное число: 1982. Суммы: 1 + 9 = 10, 9 + 8 = 17, 8 + 2 = 10.
    Удаляется 10. Результат: 1017.
    Укажите наибольшее число, при обработке которого автомат выдаёт
    результат 613. [Я. Н. Зайдельман, М. А. Ройтберг, Информатика и ИКТ. Подготовка к ЕГЭ в 2019 году. Диагностические работы. ФГОС.— М.: МЦНМО, 2019., стр 63, №6]
    Решение:
    Результат работы автомата – это число составленное из сумм цифр исходного числа, записанные в порядке неубывания, следовательно 613 можно единственным образом разбить на две суммы 6 и 13. В каждой из этих сумм должно присутствовать одинаковое слагаемое.
    6 = a + b= 2 + 4.
    13 = b + c= 9 + 4.
    Искомое число – 9424.
    Ответ: 9424
  3. Автомат обрабатывает натуральное трёхзначное число N по следующему алгоритму:
    1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее возможные двузначные числа (числа не могут начинаться с нуля).
    2. На экран выводится разность полученных двузначных чисел.
    Пример. Дано число N = 238. Алгоритм работает следующим образом:
    1. Наибольшее двузначное число из заданных цифр – 83, наименьшее – 23.
    2. На экран выводится разность 83 – 23 = 60.
    Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 70? [Тренировочная работа №4 по информатике, 4 марта 2020 года, Вариант ИН1910401]
    Решение:
    Заметим, что числа, из которых строится разность – двузначные.
    80 – 10 = 70, минимальное число, которое можно составить из цифр – 108.
    Но если число 108 подать на вход автомата, то получим следующую разность:
    81-10 = 71.
    Поэтому 108 не удовлетворяет условию задачи.
    81 – 11 = 70, минимальное число, которое можно составить из цифр – 118.
    Ответ: 118
  4. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
    1) Строится двоичная запись числа N.
    2) К этой записи дописываются справа ещё два разряда по следующему правилу:
    а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
    б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
    Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
    Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе. [Образовательный портал «Решу ЕГЭ», https://ege.sdamgia.ru/, №8094]
    Решение:
    Согласно условию задачи, если в числе было нечётное количество единиц, то в конец допишется 10. Если чётное, то 00. Таким образом, нужно найти первое число, большее 43, у которого в двоичной записи чётное количество единиц, а на конце 10 или 00. Имеем:
    44 = 1011002 – не подходит, так как в двоичной записи числа содержится нечетное количество единиц.
    45 = 1011012 – не может получиться в результате работы алгоритма, так как двоичная запись данного числа оканчивается на 01.
    46 = 1011102 – удовлетворяет всем условиям.
    Ответ: 46
  5. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
    1) Строится двоичная запись числа N.
    2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.
    Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.
    Укажите минимальное число N, для которого результат работы алгоритма будет больше 134. В ответе это число запишите в десятичной системе счисления. [Образовательный портал «Решу ЕГЭ», https://ege.sdamgia.ru/, №8094]
    Решение:
    Заметим, что если число чётное, то в конец его двоичной записи добавляются цифры 00, а если нечётное — цифры 11.
    Рассмотрим числа, большие 134, и найдем минимальное число, которое является результатом работы алгоритма.
    135 = 100001112 — может являться результатом работы алгоритма.
    Выполним обратное преобразование числа 135 согласно алгоритму:
    100001112→ 1000012 → 33.
    Получаем ответ — 33.
    Ответ: 33
  6. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.

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

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы. Например, двоичная запись 1001 числа 9 будет преобразована в 100111.

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

Укажите максимальное число N, для которого результат работы алгоритма будет меньше 134. В ответе это число запишите в десятичной системе счисления. [ЕГЭ — 2020. Досрочная волна. Вариант 2]

Решение:

Если число чётное, то в конец его двоичной записи добавляются цифры 00, а если нечётное — цифры 11.

Рассмотрим числа, меньшие 134, и найдем максимальное число, которое является результатом работы алгоритма.

133 =100001012 – не может являться результатом работы алгоритма, так как двоичная запись данного числа оканчивается на 01.

132 =100001002 – не может являться результатом работы алгоритма, так как если отбросить два последних разряда, то полученное число будет нечетным, а значит, согласно алгоритму к нему должно быть дописано 11, а не 00.

131 =100000112 – не может являться результатом работы алгоритма, так как если отбросить два последних разряда, то полученное число будет четным, а значит, согласно алгоритму к нему должно быть дописано 00, а не 11.

130 =100000102 – не может являться результатом работы алгоритма, так как двоичная запись данного числа оканчивается на 10.

129 =100000012 – не может являться результатом работы алгоритма, так как двоичная запись данного числа оканчивается на 01.

128 =100000002 – удовлетворяет всем условиям.

Выполним обратное преобразование числа 128 согласно алгоритму:

100000002→1000002 → 32.

Получаем ответ — 32.

Ответ: 32

Информационные источники

  1. «ФИПИ. Открытый банк тестовых заданий», http://os.fipi.ru/tasks/5/a
  2. Материалы для подготовки к ЕГЭ по информатике К.Ю. Полякова, http://kpolyakov.spb.ru/school/ege.htm
  3. Образовательный портал «Решу ЕГЭ», https://ege.sdamgia.ru/
  4. Я.Н.Зайдельман , ЕГЭ 2020. Информатика и ИКТ. Подготовка к ЕГЭ в 2020 году. Диагностические работы. ФГОС. — М.: МЦНМО, 2019.
  5. Я. Н. Зайдельман, М. А. Ройтберг, Информатика и ИКТ. Подготовка к ЕГЭ в 2019 году. Диагностические работы. ФГОС.— М.: МЦНМО, 2019.