5 задание ЕГЭ информатика на анализ алгоритмов

Дата изменения: 15 апреля 2021
Урок посвящен тому, как решать 5 задание ЕГЭ по информатике

Назад
К оглавлению
Далее

Объяснение 5 задания

5-е задание: «Анализ алгоритмов и исполнители»
Уровень сложности — базовый,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 4 минуты.
  
Проверяемые элементы содержания: Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд
До ЕГЭ 2021 года — это было задание № 6 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:

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

ФГБНУ "Федеральный институт педагогических измерений"

Проверка числовой последовательности на соответствие алгоритму

  • для выполнения некоторых заданий необходимо повторить тему системы счисления;
  • максимальное значение суммы цифр десятичного числа — это 18, так как 9 + 9 = 18;
  • для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было четным, то добавляется 0, если нечетным — добавляется 1:
    • например: 
 310 = 112 
после добавления бита четности: 110
----
 410 = 1002 
после добавления бита четности: 1001
  • добавление к двоичной записи числа нуль справа увеличивает число в 2 раза:
    • например:
1112 - это 710
добавим 0 справа:
11102 - это 1410

Теперь будем рассматривать конкретные типовые экзаменационные варианты по информатике с объяснением их решения.

Разбор 5 задания

Задание демонстрационного варианта 2021 года ФИПИ

Решение задания про алгоритм, который строит число R

5_11: Задание 5 (6) ЕГЭ по информатике 2017 ФИПИ вариант 2 (Крылов С.С., Чуркина Т.Е.):

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

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

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

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

  
Подобные задания для тренировки

✍ Решение:

  • Заметим, что после выполнения второго пункта задания, будут получаться только четные числа! Наименьшим возможным четным числом, превышающим 129, является число 130. С ним и будем работать.
  • Переведем 130 в двоичную систему счисления. Используя компьютер это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(130). Получим: 
    • 13010 = 100000102
  • Это двоичное число получилось из исходного двоичного, после того как дважды был добавлен остаток от деления суммы цифр на 2. Т.е.: 
    • в обратном порядке:
было 1000001 -> стало 10000010 
еще раз то же самое: 
было 100000 -> стало 1000001
  • Значит, необходимое нам двоичное число — это 100000.
  • Переведем 100000 в 10-ю систему. Для этого можно воспользоваться калькулятором, либо использовать интерпретатор Питона: int('100000',2).
    • 1000002 = 3210
  • Так как по условию у нас 4*N, то 32 делим на 4 — > 8.

Результат: 8

Для более детального разбора предлагаем посмотреть видео решения данного 5 задания ЕГЭ по информатике:

5_12: Демоверсия ЕГЭ 2018 информатика:

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

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

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

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

✍ Решение:

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

Результат: 86

Подробное решение данного 5 (раньше №6) задания из демоверсии ЕГЭ 2018 года смотрите на видео:

5_13: Разбор 5 задания ЕГЭ вариант № 1, 2019 Информатика и ИКТ Типовые экзаменационные варианты (10 вариантов), С.С. Крылов, Т.Е. Чуркина:

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

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

Например, двоичная запись 1001 числа 9 будет преобразована в 100101, а двоичная запись 1100 числа 12 будет преобразована в 110000.

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

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

✍ Решение:

  • Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые < 100 — это число 99. Переведем его в двоичную систему. На компьютерном ЕГЭ это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(99). Получим:
    • 99 = 11000112
  • По алгоритму это число получилось путем добавления справа двух разрядов, значение которых зависит от исходного N:
    • 1100011
  N
  • Т.е. в конце были добавлены две единицы — по алгоритму это значит, что исходное N должно в остатке при делении на 4 давать 3. Переведем найденное N в десятичную систему. Можно использовать калькулятор либо консоль пайтон: int('11000',2)
    • 11000 = 2410
  • 24 делится на 4 нацело, т.е. в конце по алгоритму должны были добавиться два разряда — 00. У нас же в конце 11. Т.е. число 99 не подходит. Проверим следующее — 98.
    • 98 = 11000102  : 10 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 10 
98 - не подходит

97 = 11000012 : 01 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 01 
97 - не подходит

96 = 11000002 : 00 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, у нас 00 - верно!
96 - подходит!

Результат: 96

Предлагаем посмотреть видео решения:

5_14: Разбор 5 задания ЕГЭ с сайта К. Полякова (№ 138):

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

1. Строится двоичная запись числа N.
2. К этой записи дописывается (дублируется) последняя цифра.
3. Затем справа дописывается бит чётности: 0, если в двоичном коде полученного числа чётное число единиц, и 1, если нечётное.
4. К полученному результату дописывается ещё один бит чётности.
  
Полученная таким образом запись (в ней на три разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

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

Типовые задания для тренировки  

✍ Решение:

  • В постановке задания задано R > 114. R — это результат работы алгоритма. Для того, чтобы определить наименьшее возможно N, переведем сначала 114 в двоичную систему счисления и выделим в нем три добавленные по алгоритму цифры (перевод можно выполнить в консоли Питона: bin(114))
    • 114 = 11100102
  • Проанализируем, как могло бы получиться двоичное число 114 (R) по алгоритму:

    • 2. В полученное числе N = 1110 дублируется последняя цифра и получается 11100.
    3. Поскольку число единиц (3) — нечетное, то справа добавляется 1: 111001.
    4. Т.к. в полученном наборе цифр четное число единиц, то добавляем 0: 1110010

  • Поскольку из числа N = 1110 по алгоритму могла получиться только такая последовательность цифр (1110010), то для получения минимального R, но большего чем R = 114, увеличим в N = 1110 самый младший разряд на единицу и рассмотрим работу алгоритма с полученным числом:
    • 1. N = 1110 + 1 = 1111

Работа по алгоритму:
2. 11111 - дублирование последней цифры.
3. 111111 - справа дописываем единицу, т.к. в полученном числе 5 единиц (нечетное)
4. 1111110 - дописываем ноль, т.к. в полученном числе четное число единиц.
  • Ответ нужно получить в десятичной системе счисления (для перевода можно воспользоваться интерпретатором Питона: int('1111110',2)):
    • min R = 11111102 = 12610

Результат: 126

5_17: Досрочный вариант 1 ЕГЭ по информатике 2020, ФИПИ:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
  — если N чётное, в конец числа (справа) дописываются два нуля, в противном случае справа дописываются две единицы.
 

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

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

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

Ответ: 33
  
Видео 

5_16: Разбор 5 задания ЕГЭ с сайта К. Полякова (№ 159):

Автомат обрабатывает целое число N (0 ≤ N ≤ 255) по следующему алгоритму:

1. Строится восьмибитная двоичная запись числа N.
2. Все цифры двоичной записи заменяются на противоположные (0 на 1, 1 на 0).
3. Полученное число переводится в десятичную запись.
4. Из нового числа вычитается исходное, полученная разность выводится на экран.
  
Какое число нужно ввести в автомат, чтобы в результате получилось 45?

✍ Решение:

  • Результатом выполнения алгоритма является число 45. Алгоритм работает в двоичной системе счисления, поэтому переведем число:
    • 45 = 001011012
  • Пронумеруем биты слева направо, начиная с единицы. Рассмотрим каждый бит отдельно, начиная с левого бита под номером 1.
  • 1. Так как биты в уменьшаемом и вычитаемом должны быть различны, то единица в результате может получится только 1 - 0, с учетом, что у разряда с единицей заняли. То есть бит:
    •    .
_  1 _ _ _ _ _ _ _    N инвертируемое
=  0 _ _ _ _ _ _ _    N исходное
   0 0 1 0 1 1 0 1  = 45   результат
  • 2. 1 - 0 не может в результате дать 0, так как у следующей слева единицы мы заняли. Значит, 0 - 1. Чтобы не получить единицу в ответе, необходимо у нуля тоже занять:
    •    . .
_  1 0 _ _ _ _ _ _ 
=  0 1 _ _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 3. 1 - 0 не может быть, так как у следующего слева нуля мы заняли.
    Значит 0 - 1. То есть как раз чтобы получить единицу (10 - 1 = 1), занимаем у следующих слева разрядов:
    •    . .
_  1 0 0 _ _ _ _ _ 
=  0 1 1 _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 4. 0 - 1 не может быть. Значит, чтобы получить в результате ноль, берем 1 - 0, у единицы должно быть занято.
    •    . .   .
_  1 0 0 1 _ _ _ _ 
=  0 1 1 0 _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 5. 1 - 0 не может быть. Так как слева у единицы занято. Значит, чтобы получить в результате 1, берем 0 - 1:
    •    . .   .
_  1 0 0 1 0 _ _ _ 
=  0 1 1 0 1 _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 6. 0 - 1 не даст в ответе единицу, значит, имеем 1 - 0:
    •    . .   .
_  1 0 0 1 0 1 _ _ 
=  0 1 1 0 1 0 _ _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 7. 0 - 1 не может быть, значит, 1 - 0. Чтобы получить в результате 0, необходимо, чтобы у 1 было занято:
    •    . .   .     .
_  1 0 0 1 0 1 1 _ 
=  0 1 1 0 1 0 0 _ 
   0 0 1 0 1 1 0 1  = 45   результат
  • 8. Чтобы получить 1, имеем 0 - 1:
    •    . .   .     .
_  1 0 0 1 0 1 1 0 
=  0 1 1 0 1 0 0 1
   0 0 1 0 1 1 0 1  = 45   результат
  • Полученное число (вычитаемое) и есть искомое N. Переведем его в 10-ю с.с.:
    • 01101001 = 10510

Ответ: 105

Смотрите разбор задания на видео и подписывайтесь на наш канал:

Решение заданий для темы Проверка числовой последовательности (Автомат)

5_7: ЕГЭ по информатике задание 5 с сайта К. Полякова (задание под номером Р-06):

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

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

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

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

✍ Решение:

Результат: 2949

Процесс решения данного 5 задания представлен в видеоуроке:

5_8: Задание 5 (раньше №6) ЕГЭ по информатике 2017 ФИПИ (Крылов С.С., Чуркина Т.Е.) вариант 13:

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

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

    • Пример: Исходное число: 7531. Суммы: 7+5=12; 5+3=8; 3+1=4. Результат: 4812.

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

✍ Решение:

Результат: 9320

Подробное решение данного 5 задания можно просмотреть на видео:

5_9: Задание 5 (раньше №6) ЕГЭ по информатике 2017 ФИПИ (Ушаков Д.М.) вариант 2:

Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам:

  1. Вычисляются два шестнадцатеричных числа — сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
  2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке убывания (без разделителей).

    3. Пример: Исходные числа: 25, 66. Поразрядные суммы: 8, B. Результат: B8.

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

Варианты:
A) 127
B) C6
C) BA
D) E3
E) D1

✍ Решение:

Результат: BC

Подробное решение данного 5 задания можно просмотреть на видео:

5_10: 5 задание ЕГЭ. Задание 4 ГВЭ 11 класс 2018 год ФИПИ

Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 7 (если в числе есть цифра больше 7, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

1. Вычисляются два шестнадцатеричных числа: сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.

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

Варианты:
1) AD
2) 64
3) CF
4) 811

✍ Решение:

Результат: 1

Решение 4 задания ГВЭ 11 класса смотрите на видео:

5_15: Задание 5 с сайта К. Полякова (задание под номером 109):

Автомат получает на вход натуральное число X. По этому числу строится трёхзначное число Y по следующим правилам:
1. Первая цифра числа Y (разряд сотен) – остаток от деления X на 7.
2. Вторая цифра числа Y (разряд десятков) – остаток от деления X на 2.
3. Третья цифра числа Y (разряд единиц) – остаток от деления X на 5.

Пример. Исходное число: 55. Остаток от деления на 7 равен 6; остаток от деления на 2 равен 1; остаток от деления на 5 равен 0. Результат работы автомата: 610.

  
Сколько существует двузначных чисел, при обработке которого автомат выдаёт результат 312?

Типовые задания для тренировки

✍ Решение:

  • Обозначим каждую цифру числа Y согласно заданию:
    • Y =    3       1       2
       x mod 7    x mod 2    x mod 5
  • Сделаем выводы:

    • 1. x mod 2 = 1 => значит, X — нечетное число
    2. x mod 5 = 2 => значит, X — либо ?2, либо ?7.
    3. раз x — нечетное, то из пред. пункта получаем x = ?7
    4. x mod 7 = 3 => переберем все варианты:

    97 - не подходит, 
87 - подходит (87 / 7 = 12, остаток = 3)
77 - не подходит,
67 - не подходит,
57 - не подходит,
47 - не подходит,
37 - не подходит,
27 - не подходит,
17 - подходит (17 / 7 = 2, остаток = 3)

Результат: 2

Назад
К оглавлению
Далее

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить