ЕГЭ · краткий ответ

Задание 5 ЕГЭ по информатике — анализ алгоритма для автомата (двоичная запись числа)

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

66заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 5 ЕГЭ

Автомат получает число N, переводит его в двоичную (троичную и т. п.) запись, дописывает или меняет разряды по правилу и выдаёт новое число R. Нужно найти наименьшее N или наибольшее R при условии. Надёжнее всего — смоделировать алгоритм на Python и перебрать N.

КЕГЭ, задание 566 заданий в банке ИнфДоски

Типичные ошибки

  • Дописывают бит чётности по исходной записи, когда по правилу его считают уже по изменённой.
  • Забывают перевести результат обратно в десятичную систему.
  • Перебирают слишком маленький диапазон N и не находят ответ.
  • Путают «R больше 130» и «R не меньше 130».

Пример с решением

Условие

Автомат получает на вход натуральное число N и строит число R так: 1) строится двоичная запись N; 2) к ней справа дописывается 0, если в записи чётное число единиц, и 1 — если нечётное; 3) шаг 2 повторяется для полученной записи. Укажите наименьшее N, для которого R больше 130.

Решение

Моделируем алгоритм: функция строит запись по правилам и переводит её в десятичное число. Перебираем N по возрастанию, первое подходящее — ответ.

def R(n):
    b = bin(n)[2:]
    for _ in range(2):
        b += '0' if b.count('1') % 2 == 0 else '1'
    return int(b, 2)

print(min(n for n in range(1, 1000) if R(n) > 130))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 33

Задания из банка

В банке ИнфДоски 66 заданий этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Алгоритмы для исполнителей Открыть на доске →

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

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

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

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на дописывается в конец числа (справа). Например, запись преобразуется в запись ;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на .

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

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

Ответ
402
Задание 2 Алгоритмы для исполнителей Открыть на доске →

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

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

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

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на дописывается в конец числа (справа). Например, запись преобразуется в запись ;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на .

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

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

Ответ
58
Задание 3 Алгоритмы для исполнителей Открыть на доске →

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

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

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

Например, двоичная запись числа будет преобразована в , а двоичная запись числа будет преобразована в .

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

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

Ответ
77
Задание 4 Алгоритмы для исполнителей Открыть на доске →

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

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

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

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на дописывается в конец числа (справа). Например, запись преобразуется в запись ;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на .

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

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

Ответ
25
Задание 5 Алгоритмы для исполнителей Открыть на доске →

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

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

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

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

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

Ответ
24
Задание 6 Алгоритмы для исполнителей Открыть на доске →

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

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

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

а) складываются все цифры двоичной записи, и остаток от деления суммы на дописывается в конец числа (справа). Например, запись преобразуется в запись ;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на .

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

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

В ответе это число запишите в десятичной системе счисления.

Ответ
112
Задание 7 Алгоритмы для исполнителей Открыть на доске →

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается , а затем два левых разряда заменяются на ;

б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается , а затем два левых разряда заменяются на .

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

Например, для исходного числа результатом является число , а для исходного числа результатом является число .

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

Ответ
11
Задание 8 Алгоритмы для исполнителей Открыть на доске →

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на , то к этой записи дописываются три последние двоичные цифры;

б) если число N на не делится, то остаток от деления умножается на , переводится в двоичную запись и дописывается в конец числа.

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

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

Например, для исходного числа результатом является число , а для исходного числа это число .

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

Ответ
127
Задание 9 Алгоритмы для исполнителей Открыть на доске →

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на , то к этой записи дописываются три последние двоичные цифры;

б) если число N на не делится, то остаток от деления умножается на , переводится в двоичную запись и дописывается в конец числа.

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

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

Например, для исходного числа результатом является число , а для исходного числа результатом является число .

Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем .

Ответ
16
Задание 10 Алгоритмы для исполнителей Открыть на доске →

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

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

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на , то к этой записи дописываются две последние троичные цифры;

б) если число N на не делится, то остаток от деления умножается на , переводится в троичную запись и дописывается в конец числа.

Полученная таким образом запись является троичной записью искомого числа R.

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

Например, для исходного числа результатом является число , а для исходного числа это число .

Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, не меньшее .

Ответ
11
ИнфДоска

Разбирайте задание 5 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ