Информатика ЕГЭ 5 задание разбор

5-е задание: «Анализ алгоритмов и исполнители» Уровень сложности — базовый, Требуется использование специализированного программного обеспечения — нет, Максимальный балл — 1, Примерное время выполнения — 4 минуты.

Проверяемые элементы содержания: Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд

Плейлист видеоразборов задания на YouTube:

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

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

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

Ответ: 8

✎ Решение аналитическим способом:

✎ Решение с использованием программирования:

uses school; begin var n_ := 1; while True do begin var n := 4*n_; var ost := bin(n).CountOf('1') mod 2; // остаток при делении на 2 n := 2 * n + ost; //в двоичной с.с. добавляем разряд (*2) и остаток к этому разряру (+ost) ost := bin(n).CountOf('1') mod 2; // остаток при делении на 2 n := 2 * n + ost; if n > 129 then begin println(n_); break end; n_ += 1; end; end.

n_ = 1 while True: n = 4*n_ r = str(bin(n)) r = r[2:] for i in range(2): if r.count('1') % 2 == 0: r+='0' else: r+='1' n = int(r, base=2) if n > 129: print(n_) break n_+=1

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

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

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

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

Ответ: 86

• Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
• Наименьшим возможным числом, превышающим 83, является число 84. С ним и будем работать.
• Переведем 84 в двоичную систему счисления. На компьютерном ЕГЭ это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(84) . Получим:
• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как оно нечетное. А мы имеем 0. Соответственно, это оно не подходит.
• Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:
• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Соответственно, оно подходит.

Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом: 1. Строится двоичная запись числа N . 2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется цифра, которая встречается реже. 3. Шаг 2 повторяется ещё два раза. 4. Результат переводится в десятичную систему счисления.

При каком наименьшем исходном числе N > 65 в результате работы алгоритма получится число, кратное 4?

Ответ: 79

✎ Решение с использованием программирования:

uses school; begin var n_ := 1; while True do begin var n := n_; for var i := 1 to 3 do begin if bin(n).CountOf('1') = bin(n).CountOf('0') then // сравниваем if n mod 2 = 0 then // если четное, то в конце 0 n := 2 * n // добавляем разряд = 0 else n := 2 * n + 1 // иначе добавляем разряд = 1 else if bin(n).CountOf('1') > bin(n).CountOf('0') then n := 2 * n else n := 2 * n + 1 end; if (n_ > 65) and (n mod 4 = 0) then begin println(n_); break end; n_ += 1; end; end.

n_ = 1 while True: n = n_ r = str(bin(n)) r = r[2:] for i in range(3): if r.count('1') == r.count('0'): r+=r[-1] elif r.count('1')>r.count('0'): r+='0' else: r+='1' n = int(r, base=2) if n_ > 65 and n % 4 == 0 : print(n_,n) break n_+=1

На вход алгоритма подаётся натуральное число N . Алгоритм строит по нему новое число R следующим образом. 1) Число N переводим в двоичную запись. 2) Инвертируем все биты числа кроме первого. 3) Переводим в десятичную запись. 4) Складываем результат с исходным числом N . Полученное число является искомым числом R .

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

Ответ: 65

✎ Решение с использованием программирования:

n_ = 1 while True: n = n_ r = str(bin(n)) r = r[2:] for i in range(1,len(r)): if r[i]== '0': r=r[:i]+'1'+r[i+1:] else: r=r[:i]+'0'+r[i+1:] n = int(r, base=2) n+=n_ if n > 99 and n_ % 2 != 0 : print(n_,n) break n_+=1

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

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

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

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

Ответ: 96

• Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые bin(99) . Получим:
• По алгоритму это число получилось путем добавления справа двух разрядов, значение которых зависит от исходного N:
• Т.е. в конце были добавлены две единицы — по алгоритму это значит, что исходное N должно в остатке при делении на 4 давать 3. Переведем найденное N в десятичную систему. Можно использовать калькулятор либо консоль пайтон: int('11000',2)
• 24 делится на 4 нацело, т.е. в конце по алгоритму должны были добавиться два разряда — 00. У нас же в конце 11. Т.е. число 99 не подходит. Проверим следующее — 98.