Как делать 5 задание егэ информатика

ЕГЭ по информатике 2021 — Задание 5 (Алгоритмы, Автоматы)

Привет! Сегодня исследуем интересное 5 задание из ЕГЭ по информатике нового формата 2021.

Пятое задание ЕГЭ по информатике в основном связано с алгоритмами и автоматами.

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

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

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

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

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

У нас на вход поступает натуральное (обычное, не дробное, положительное) число N.

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

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

Про первый дополнительный разряд написано в пункте a второго правила: «складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 10000 преобразуется в запись 100001».

Если сказать более просто, то автомат подсчитывает количество единиц у первоначального двоичного числа N, полученного в первом пункте. Если количество чётное, то автомат в первый дополнительный разряд должен поставить 0. Если количество нечётное, то автомат в первый дополнительный разряд должен поставить 1.

Про второй дополнительный разряд сказано в пункте б второго правила. Автомат сделает тоже самое, что и в предыдущем пункте, только теперь подсчёт единиц будет происходить не только в двоичной записи числа N, но и в первом дополнительном разряде.

В вопросе просят указать входящее наименьшее число N, чтобы автомат выдал число R больше 97.

Т.к. число R должно быть больше 97, то переведём число 98 (97 + 1) в двоичный вид, чтобы можно было оценить входящее число N.

Получилось число 1100010. Будем рассматривать (начиная с 1100010) числа на выполнение правил, которые заданы для автомата. Если все правила будут выполнены, значит, мы получили то число, по которому вычислим изначальное N. Нам нужно получить именно минимальное число, поэтому мы и начали с минимального возможного претендента для числа R (98).

Видим, что подходит число 1100110. В части числа, которая является двоичным представлением N, количество единиц равно 3. Число 3 нечётное, значит, в первом дополнительном разряде должна стоять 1 (единица).

Проверим второй дополнительный разряд. Теперь считаем единицы не только в двоичном представлении числа N, но так же и в первом дополнительном разряде! Количество единиц равно 4. Число 4 чётное. Значит, во втором дополнительном разряде должен стоять 0 (ноль). Все правила работы автомата выполняются в числе 1100110.

Чтобы найти искомое число N, отбросим два дополнительных разряда от найденного 1100110.

Правило: Если от двоичного числа отбросить младший разряд, то оно разделится на 2 целочисленным образом (т.е. делим на 2, если есть остаток, убираем его).

Найдём полученное минимальное число R 1100110 в десятичном представлении. Число 1100010 — 98, 1100011 — 99, 1100100 — 100, 1100101 — 101, 1100110 — 102.

Уберём второй дополнительный разряд у числа 1100110, получается 102 / 2 = 51 (110011). Уберём ещё и первый дополнительный разряд , получается 51 / 2 = 25 (11001).

Значит двоичное представление искомого числа N равно 11001, а десятичное 25.

Изучим ещё одну классическую задачу задания 5 из ЕГЭ по информатике.

Задача (классическая, Автомат)
Автомат получает на вход пятизначное число. По этому числу строится новое число по следующим правилам.
1. Складываются отдельно первая, третья и пятая цифры, а также вторая и четвёртая цифры.
2. Полученные два числа записываются друг за другом в порядке неубывания без разделителей.
Пример. Исходное число: 63 179. Суммы: 6 + 1 + 9 = 16; 3 + 7 = 10. Результат: 1016.
Укажите наименьшее число, при обработке которого автомат выдаёт результат 723.

В подобных задачах из ЕГЭ по информатике нумерация происходит начиная со старшего разряда.

Составим краткую запись для первого правила:

Второе правило заключается в том, что мы «соединяем» два числа, полученных в первом пункте, причём, сначала идёт меньшее число, а затем большее.

Рассмотрим число 723.

Разбить на числа 72 и 3 нельзя, т.к. вначале пишется меньшее число. Значит, разбиваем на 7 и 23.

Первое число (сумма 1, 3, 5 разрядов) будет 23, т.к. только сумма трёх цифр может дать число 23. Сумма двух цифр максимум может быть 9+9=18. Тогда 7 — это второе число (сумма 2 и 4 разряда.)

Нам нужно указать наименьшее пятизначное входящее число, поэтому стремимся более старшие разряды сделать как можно меньше! Пусть самый старший разряд (1 разряд) равен 1 (минимальное значение для старшего разряда). Тогда нужно с помощью суммы 3-его и 5-ого разряда набрать 22. Но это не возможно, т.к. максимум с двух разрядов получается 9+9=18. Поэтому приходим к выводу, что самое маленькое значение для 1-ого разряда будет 23-18=5, а третий и пятый разряд будут по 9.

Т.к. 7 — это сумма второго и четвёртого разряда, то сделаем второй разряд 0(нулём), а четвёртый 7, чтобы пятизначное число было минимальным.

Получаем окончательный результат 50979.

Ответ: 50979

Следующая задача иногда встречается в тренировочных вариантах ЕГЭ по информатике.

Задача (Кузнечик)
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 7 – Кузнечик прыгает вперёд на 7 единиц,
Назад 5 – Кузнечик прыгает назад на 5 единиц.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 5», чтобы Кузнечик оказался в точке 19?

В данной задаче у нас есть числовая ось на которой живёт кузнечик.

Кузнечик может прыгать либо на 7 шагов вперёд, либо на 5 шагов назад. На другое количество шагов Кузнечик прыгать не может!

Обозначим за x — количество прыжков на 7 шагов вперёд, а за y — количество прыжков на 5 шагов назад. x и у — должны быть целые неотрицательные числа.

Если бы Кузнечик начинал не с нулевой отметки, мы бы прибавили начальную координату к левой части уравнения.

Выражение в правой части 5y — делиться на 5, значит и 7x — 19 должно делиться на 5. Чтобы выражение в левой части делилось на 5, нужно чтобы 7x оканчивалось либо на 4, либо на 9 (Тогда и выражение 7x — 19 будет оканчиваться либо на 5, либо на 0).

Вспомним таблицу умножения:

Нам не подходит 14, т.к. 14-19 5y = 49 — 19 = 30.
y = 6
Ответ: 6.

Задача из ЕГЭ по информатике на побитовый сдвиг:

Задача(редкая, сдвиг влево)
У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, причём на место освободившегося бита ставится 0. Выполняя вторую команду исполнитель вычитает из числа 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.

Здесь есть всего две команды у исполнителя: сдвинуть биты влево и вычесть 1.

Правило: Если к двоичному числу приписать справа ноль, то это число увеличится в два раза.

Сдвиг влево: Возьмём число 150 (1001 0110). После сдвига влево к двоичному числу приписывается справа ноль (т.е. число умножается на 2) 300(1 0010 1100), а левый бит, если общее количество битов больше 8, отбрасывается (т.к. у нас однобайтовое число). Получается 44 (0010 1100) — нули в начале числа тоже отбрасываются. А 44 — остаток от деления 300/256

В нашей задаче число однобайтовое, значит число не превышает 255. Если при умножении на 2, получаем число большее, чем 255, то мы должны взять остаток от деления на 256

осталось проделать цепочку команд 112112.

91 * 2 = 182 (182
182 * 2 = 364 (364 / 256 — остаток 108)
108 — 1 = 107
107 * 2 = 214 (214
214 * 2 = 428 (428 / 256 — остаток 172)
172 — 1 = 171

Если была бы команда сдвиг вправо, то тогда у числа просто убирался бы правый бит (т.е. происходило бы целочисленное деление на 2)

В задании 5 ЕГЭ по информатике может встретится задача на исполнителя чертёжника.

Задача (Исполнитель Чертежник)
Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:
Сместиться на вектор (а, Ь) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.
Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:
Сместиться на вектор (5,2)
Сместиться на вектор (-3, 3)
Повторить 3[Сместиться на вектор (1,0)]
Сместиться на вектор (3, 1)
На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

После первой команды Сместиться на вектор (5,2) Исполнитель чертёжник окажется:

После второй команды Сместиться на вектор (-3, 3)

Следующая команда Повторить 3[Сместиться на вектор (1,0)]

Следующая команда Сместиться на вектор (3, 1)

Расстояние от начала координат находит по теореме Пифагора:

Значит, расстояние равно 10.

Последняя задача довольно часто печатается в тренировочных заданиях по ЕГЭ по информатике.

Задача (Исполнитель)
У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:
1. вычти 1
2. умножь на 3
Первая из них уменьшает число на экране на 1, вторая – увеличивает его в три раза.
Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.

(Например, программа 21211 это программа

умножь на 3
вычти 1
умножь на 3
вычти 1
вычти 1

которая преобразует число 1 в 4.)

У нас есть две команды: вычитание 1 и умножить число на 3. Другие действия мы производить не можем!

Нужно получить из 3 -> 16.

В похожих задачах ЕГЭ по информатике лучше всего начать с конца. Шестнадцать умножением на 3 мы никак не получим. Значит, последний командой будет вычитание. Семнадцать (16 + 1) тоже умножением на 3 не получить. Значит, предпоследней командой тоже будет вычитание. Восемнадцать (17 + 1), скорее всего получили умножением на 3! Шесть (18 / 3), получили умножением 2 на 3. Два — это 3 — 1.

Таким образом, получается цепочка команд 1 -> 2 -> 2 -> 1 -> 1

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

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

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

До ЕГЭ 2021 года — это было задание № 6 ЕГЭ
Типичные ошибки и рекомендации по их предотвращению:

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

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

Исполнитель для возведения в квадрат, деления, умножения и сложения

• в задаче, для которой требуется определить все возможные результаты работы алгоритма какого-либо исполнителя, можно исходные данные обозначить переменными и вычислить алгоритм с этими переменными;
• в задаче, для которой требуется найти оптимальную программу (или наиболее короткую), и которая с помощью заданного набора команд преобразует некоторое число в другое, лучше для решения строить дерево возможных вариантов; таким образом, вычисляя, какие результаты получатся после одного шага, после двух шагов и т.д. В результате найдется общее решение;
• если среди заданных в задании команд исполнителя есть необратимая команда (например, исполнитель работает с целыми числами и есть команда возведения в квадрат – любое число можно возвести в квадрат, но не из любого числа можно извлечь квадратный корень, получив при этом целое), то дерево вариантов лучше строить с конца, т.е. в обратном порядке, двигаясь от конечного числа к начальному; тогда как получившаяся при этом в результате последовательность команд программы необходимо записать от начального числа к конечному.

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

• для выполнения некоторых заданий необходимо повторить тему системы счисления;
• максимальное значение суммы цифр десятичного числа — это 18, так как 9 + 9 = 18;
• для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было четным, то добавляется 0, если нечетным — добавляется 1:

например: 310 = 112 после добавления бита четности: 110 ---- 410 = 1002 после добавления бита четности: 1001

например: 1112 - это 710 добавим 0 справа: 11102 - это 1410

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

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

Задание демонстрационного варианта 2022 года ФИПИ
Плейлист видеоразборов задания на YouTube:

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

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

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

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

✍ Решение:

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

13010 = 100000102

в обратном порядке: было 1000001 -> стало 10000010 еще раз то же самое: было 100000 -> стало 1000001 

1000002 = 3210

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

PascalAbc.Net:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

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.

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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_ = 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

Результат: 8

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

�� YouTube здесь
�� Видеорешение на RuTube здесь (теоретическое решение)

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

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

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

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

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

✍ Решение:

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

84 = 1010100

86 = 1010110

Результат: 86

Подробное решение данного 5 (раньше №6) задания из демоверсии ЕГЭ 2018 года смотрите на видео:
Видеорешение с программированием (PascalAnc.Net):
�� YouTube здесь
�� Видеорешение на RuTube здесь
Аналитическое видеорешение:

�� Видеорешение на RuTube здесь -> аналитическое решение

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

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

✍ Решение:

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

PascalAbc.Net:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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.

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

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_ = 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

Ответ: 79

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

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

✍ Решение:

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

PascalAbc.Net:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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_ = 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

Ответ: 65

На вход алгоритма подается натуральное число 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 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

✍ Решение:

• Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые bin(99) . Получим:

99 = 11000112 

1100011 N 

11000 = 2410 

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

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

�� YouTube здесь
�� Видеорешение на RuTube здесь (теоретическое решение)

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

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

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

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

✍ Решение:

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

114 = 11100102 

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

1. N = 1110 + 1 = 1111 Работа по алгоритму: 2. 11111 - дублирование последней цифры. 3. 111111 - справа дописываем единицу, т.к. в полученном числе 5 единиц (нечетное) 4. 1111110 - дописываем ноль, т.к. в полученном числе четное число единиц.

min R = 11111102 = 12610

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

PascalAbc.Net:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

n_ = 1 while True: n = n_ r = str(bin(n)) # строковое значение r = r[2:] # убираем 0b r=r+r[-1] for i in range (2): if r.count('1') % 2 == 0: r = r+'0' else: r = r+'1' r = int(r,base = 2) # в 10-ю с.с. if r > 114: print(r) break n_+= 1

n_ = 1 while True: n = n_ r = str(bin(n)) # строковое значение r = r[2:] # убираем 0b r=r+r[-1] for i in range (2): if r.count(‘1′) % 2 == 0: r = r+’0′ else: r = r+’1’ r = int(r,base = 2) # в 10-ю с.с. if r > 114: print(r) break n_+= 1

Результат: 126

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

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

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

Ответ: 33

Видео -> теоретическое решение
�� Видеорешение на RuTube здесь -> теоретическое решение

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

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

Какое число нужно ввести в автомат, чтобы в результате получилось 45?

✍ Решение:

• Результатом выполнения алгоритма является число 45. Алгоритм работает в двоичной системе счисления, поэтому переведем число:

45 = 001011012

. _ 1 _ _ _ _ _ _ _ N инвертируемое = 0 _ _ _ _ _ _ _ N исходное 0 0 1 0 1 1 0 1 = 45 результат

. . _ 1 0 _ _ _ _ _ _ = 0 1 _ _ _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат

. . _ 1 0 0 _ _ _ _ _ = 0 1 1 _ _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат

. . . _ 1 0 0 1 _ _ _ _ = 0 1 1 0 _ _ _ _ 0 0 1 0 1 1 0 1 = 45 результат

. . . _ 1 0 0 1 0 _ _ _ = 0 1 1 0 1 _ _ _ 0 0 1 0 1 1 0 1 = 45 результат

. . . _ 1 0 0 1 0 1 _ _ = 0 1 1 0 1 0 _ _ 0 0 1 0 1 1 0 1 = 45 результат

. . . . _ 1 0 0 1 0 1 1 _ = 0 1 1 0 1 0 0 _ 0 0 1 0 1 1 0 1 = 45 результат

. . . . _ 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 результат

01101001 = 10510

Ответ: 105

Смотрите теоретический разбор задания на видео и подписывайтесь на наш канал:
�� YouTube здесь
�� Видеорешение на RuTube здесь -> теоретическое решение

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

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

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

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

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

✍ Решение:

Результат: 2949

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

�� YouTube здесь
�� Видеорешение на RuTube здесь -> теоретическое решение

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

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

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

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

✍ Решение:

12=9+3

Результат: 9320

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

�� YouTube здесь
�� Видеорешение на RuTube здесь -> теоретическое решение

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

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

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

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

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

✍ Решение:
Проанализируем все варианты:

Результат: BC

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

�� YouTube здесь
�� Видеорешение на RuTube здесь -> теоретическое решение

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

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

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

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

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

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

✍ Решение:

Результат: 1

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

�� YouTube здесь
�� Видеорешение на RuTube здесь -> теоретическое решение

Автомат получает на вход натуральное число 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

Задание 5 ЕГЭ по информатике

Сборник необходимой теории и практики к заданию №5 ЕГЭ 2023 по информатике «Выполнение и анализ простых алгоритмов».

• Вся теория по информатике для ЕГЭ
• Тренировочные варианты ЕГЭ по информатике

Формулировка задания №5 ЕГЭ 2023 из демоверсии ФИПИ

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

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

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

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

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

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

Самое необходимое по заданию №5 в формате видеоурока

Как решать задание №5

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

1. Строится двоичная запись числа N.
2. Запись «переворачивается», то есть читается справа налево. Если при этом появляются ведущие нули, они отбрасываются.
3. Полученное число переводится в десятичную запись и выводится на экран.

Какое наименьшее число, превышающее 500, после обработки автоматом даёт результат 19?

Решение: Наименьшим возможным числом, превышающим число 500, является число 501. Переведём число 501 в двоичную систему:

• 501₁₀ = 2 8 + 2 7 + 2 6 + 2 5 + 2 4 + 2 2 + 2 0 = 111110101₂

Переведём число 19 в двоичную систему:

Перевернём число 19: 11001. К числу 11001 в конец нужно приписать нули так, чтобы оно превысило 501: 1100100000.

• 1100100000₂ = 2 9 + 2 8 + 2 5 = 512 + 256 + 32 = 800₁₀.

Ответ: 800.

Ниже представлены замечательные материалы, подготовленные Поляковым Константином Юрьевичем, доктором технических наук. В них вы найдёте всё самое полезное для себя — теория, решения заданий и практика.

ЕГЭ по информатике с решением

На рисунке представлена схема дорог около города Умь. В таблице звездочкой обозначено наличие дороги из одного населённого пункта в другой, отсутствие звездочки означает, что такой дороги нет. Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно.

Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам Б и Д на схеме. В ответе запишите эти два номера в порядке возрастания без пробелов и знаков препинания.

Рассмотрим наш граф. Заметим, что город С уникален в том смысле, что из него выходит уникальное число дорог, а именно 5. По таблице легко понять, что С = П4. Заметим, что город Б едиственный не связан дорогой с городом С. Так как нам известно, С = П4. По таблице строки П4 мы видим, что единственный пункт, не связанный с П4, – это П6. Таким образом, понимаем, что Б = П6. Теперь найдем номер города Д. Он связан с городом Б, также мы знаем, что из него выходят три дороги. По строке П6 из таблицы мы видим, что город Б связан с П1 и П7. Из П1 выходят три дороги, из П7 – две. Из графа видим, что от Д – три дороги, от Г – две. Следовательно, Д = П1. В ответ записываем два номера в порядке возрастания – 16.

Задание 2 #10267

Саша и Максим потерялись в лесу. На рисунке представлена схема тропинок в лесу между столетними дубами. В таблице содержатся сведения о длине тропинки от одного дуба к другому. Отсутствие значения означает, что такой тропинки нет. Каждому дубу на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Помогите Саше и Максиму определить длину тропинки между дубами Ж и З.

Рассмотрим наш граф. Заметим, что дубы Б и А уникальны в том смысле, что от них выходит уникальное число тропинок: из Б – одна, из А – пять. Следовательно, мы сразу можем определить, что Б = Д8 и А = Д3. Далее из таблицы мы видим, что Д8 связан с Д7, следовательно, Г = Д7. Нам нужно определить номер дуба З. Посмотрим на строчку Д7 таблицы: кроме того, что он связан с Д8 и Д3 (Б и А соответственно), также он связан с Д4 и Д5. Эти номера могут соответствовать дубам В и З. Заметим из таблицы, что Д4 связан с Д3 (то есть Д4 связан с А – видим из графа, что З не связан с А, то есть Д4 – это В), а значит, З = Д5. Далее по таблице определяем, что Д5 связан с Д6 и Д7 (т.е. З связан с Д6 и Г), а значит, Ж = Д6. По таблице определяем искомую длину тропинки между Д5 и Д6 – 4.

Задание 3 #10268

На рисунке представлена схема дорог около города Максимовка. В таблице звездочкой обозначено наличие дороги из одного населённого пункта в другой, отсутствие звездочки означает, что такой дороги нет. Каждому населенному пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно.

Определите, какие номера населенных пунктов в таблице могут соответствовать населенным пунктам Ж и З на схеме. В ответе запишите эти два номера в порядке возрастания без пробелов и знаков препинания.

Рассмотрим наш граф. Заметим, что пункт А уникален том смысле, что из него выходит уникальное число дорог, а именно одна. Следовательно, мы сразу можем определить его номер по таблице: А = П4. Также мы сможем определить номер города Б, так как он единственный связан дорогой с городом А: Б = П2. Заметим, что городов, от которых выходит по четыре дороги, всего два – Б и Ж. Следовательно, мы можем определить номер пункта Ж, так как Б нам уже известен: Ж = П1. Теперь поймем, какой номер соответствует городу З. Так как из него выходят две дороги так же, как из пункта В, то и З, и В могут соответствовать номера 7 и 8. Заметим из таблицы, что П8 связан с П2, следовательно, П8 – это город В. Тогда З = П7. В ответ запишем номера искомых пунктов в порядке возрастания – 17.

Задание 4 #10269

Аня и Таня нашли карту сокровищ. На рисунке представлена схема мостов между островами в океане Z. В таблице содержатся сведения о длине моста от одного острова к другому. Отсутствие значения означает, что такого моста нет. Каждому острову на схеме соответствует его номер в таблице, но неизвестно, какой именно. Чтобы спланировать путешествие, Ане и Тане нужно определить длину моста между островами Ж и Е.

Рассмотрим наш граф. Заметим, что острова Д и Е уникальны в том смысле, что от них построено уникальное число мостов: от Д – два, от Е – четыре. Следовательно, мы сразу можем определить по таблице, что Д = О7 и Е = О8. Заметим, что от остальных островов отходит по три моста. Но острова Б и З не связаны с островом Е, следовательно, им могут соответствовать номера 1 и 6 (определяем по строке О8: смотрим, с какими номерами отсутствует связь, – это номера 1, 6 и 7, но мы знаем, что О7 = Д). Далее по таблице определяем, с каким номером у О1 и О6 общая связь (смотрим на строки О1 и О6 и видим, что есть мост между О1 и О5 – и мост между О6 и О5). Следовательно, О5 = Ж. Далее находим длину моста между Ж и Е (то есть между О5 и О8). Искомая длина – 17.

Задание 5 #10270

Артём и Саша гуляют по парку аттракционов. На рисунке представлена схема проходов между аттракционами. В таблице звездочкой обозначено наличие прохода от одного аттракциона к другому, отсутствие звездочки означает, что такого прохода нет. Каждому аттракциону на схеме соответсвует его номер в таблице, но неизвестно, какой именно.

Определите, какие номера в таблице могут соответствовать аттракционам В и З на схеме. В ответе запишите эти два номера в порядке возрастания без пробелов и знаков препинания.

Рассмотрим наш граф. Заметим, что аттракционы Д и Б уникальны в том смысле, что из них выходит уникальное число проходов: из Д – четыре, от Б – два. Следовательно, мы сразу можем определить по таблице, что Д = А8 и Б = А5. Заметим, что Б связан с пунктами Е и З, причем из Е существует два прохода, а из З – три. Следовательно, по таблице мы можем определить, что З = А4 (находим строку А5 в таблице, определяем, что он связан с А4 и А6, из А4 – три прохода, из А6 – два). Далее заметим, что у нас два аттракциона, из которых выходят два прохода – Е и В. Так как мы знаем, что Е = А6, В = А7. В ответ запишем номера аттракционов в порядке возрастания: 47.

Задание 6 #10278

На рисунке представлена схема дорог около города Утьского района. В реестре учета дорог этого города содержатся сведения об их длине. Отсутствие значения означает, что такой дороги нет. Обозначения пунктов в реестре и на схеме не совпадают. Определите, какова длина пути из пункта Б в пункт Г. В ответе запишите только число.

Рассмотрим наш граф. Заметим, что из пунктов Б и Г выходит по четыре дороги. Из таблицы видим, что им могут соответствовать пункты под номерами 3 и 4. Так как нам нужна длина дороги между этими пунктами, необязательно точно определять их номера. Из таблицы находим искомую длину (длина пути из 3 пункта в 4 – или наоборот) – 8.