1. Главная
2. Обучение
3. ЕГЭ информатика

---

Исполнение алгоритмов

Документы по теме:

Задания для самостоятельного решения

Разбор заданий разных типов.

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

1. Из цифр, образующих десятичную запись N, строятся наибольшее и наименьшее
   возможные двузначные числа (числа не могут начинаться с нуля).
2. На экран выводится разность полученных двузначных чисел.

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

1. Наибольшее двузначное число из заданных цифр – 53, наименьшее – 13.
2. На экран выводится разность 53 – 13 = 40.

Чему равно наименьшее возможное трёхзначное число N, в результате обработки которого на экране автомата появится число 40?

Решение:

• расставим цифры числа в порядке возрастания: a, b, c (среди них могут быть и одинаковые)
• сначала рассмотрим случай, когда a = b = 0, c ¹ 0; при этом максимальное и минимальное двузначные числа совпадают и равны 10c, а их разность равна 0
• пусть теперь a = 0, b ¹ 0 и c ¹ 0; тогда максимальное двузначное число – 10c + b, а минимальное – 10b; их разность равна 10(c – b) + b; чтобы эта разность была равна 40, необходимо, чтобы b = 0, а это противоречит исходному предположению
• остаётся один случай – среди цифр нет нулей; тогда максимальное двузначное число – 10c + b, а минимальное – 10a + b;
• их разность равна 10(c – a); чтобы эта разность была равна 40, необходимо, чтобы c – a = 4, то есть минимальные значения цифр – c = 5, a = 1; поскольку все цифры ненулевые, то b = 1
• для получения минимального числа цифры 5, 1 и 1 нужно расставить в порядке неубывания
• Ответ: 115.

Пример 2. 

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

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

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

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

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

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

Решение:

• фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль
• если в конце двоичной записи числа стоит 0, значит, оно чётное; поэтому мы в результате работы алгоритма должно обязательно получиться чётное число
• по условию, мы должны получить чётное число, большее 137; числа-кандидаты – 138, 140, 142, 144, …
• проверяем число 138: после выполнения шага 2б оно увеличилось вдвое (приписали 0), поэтому до выполнения этого шага у нас было число 138 : 2 = 69 = 1000101₂; в этом двоичном коде нечётное число единиц (3), поэтому оно не подходит по условию (после шага 2а количество единиц должно стать чётным, так как мы добавили бит чётности)
• проверяем следующее число-кандидат: 140 : 2 = 70 = 1000110₂, тут тоже 3 единицы, оно тоже не подходит
• следующее чётное число, 142, при делении на 2 даёт число 71 = 1000111_2, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма; на этом шаге к нему был добавлен бит чётности, выделенный жёлтым фоном
• убираем последний бит числа 71 (бит чётности), получаем 35 = 100011₂

 

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

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

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

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

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

Решение:

• фактически на шаге 2а добавляется бит чётности так, чтобы количество единиц в двоичной записи нового числа стало чётным;
• на шаге 2б всегда дописывается 0, поскольку после шага 2а число единиц уже чётно;
• если двоичная запись числа оканчивается на 0, то число чётно, поэтому имеет смысл искать число-результат R среди чётных чисел
• возьмём первое чётное число, большее, чем 77, и переведём его в двоичную систему:
  78 = 1001110₂ ; 
• видим, что все условия выполняются: в двоичной записи числа 78 чётное число единиц (четыре), поэтому оно могло быть получено в результате работы приведённого алгоритма
• во время работы алгоритма к двоичной записи приписали сзади две цифры, их нужно отбросить 
• Ответ: 19.

---

Форма отчёта обучающегося: Нет работы

Работы не принимаются в цифровой форме