6261 подписчик

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

17 января 202317 янв 2023

370

9 мин

Оглавление

Задача 1
Задача 2
Задача 3

В данной статье разберем с вами подробное решение типовых задач, с которыми приходится сталкиваться ученикам при подготовке к ЕГЭ по информатике. Эти задания еще долго будут актуальны при подготовке к ЕГЭ. Некоторые задачи, связанные с программированием, я попытался разобрать двумя способами:
1 способ: аналитическое решение, которое можно выполнить на черновике без компьютера
2 способ: численное решение, реализованное с помощью метода грубой силы (брутфорс или перебор решений с помощью модернизации исходного кода программы). Если вам что-то будет непонятно, то пишите свои вопросы в комментариях на Дзен к этой статье. А если вам понадобятся индивидуальные занятия по физике, математике или информатике, то мои контакты вы сможете найти выше.

А пока попрошу подписаться на мой канал в telegram IT mentor . Краткие заметки и наблюдения по физике, математике, программированию, железу и технике 💡 В моем telegram я выкладываю компактные решения в виде pdf. Советую подписаться :)

Задача 1

Логическая функция F задается выражением x ꓥ (y ꓥ z ꓦ y ꓥ ¬w ꓦ ¬z ꓥ ¬w) = 1. На рисунке приведен фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция Fистинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

Решение:
Упростим наше логическое выражение:

Отсюда уже следует, что 4-й столбец соответствует x, т.к. если будет хоть один ноль, то вся функция будет обнуляться, что недопустимо, т.к. в самом правом столбце значений функции стоят единицы.

Рассмотрим 2-ю строку:

Делаем вывод, что 1-й столбец соответствует y.

Рассмотрим 3-ю строку:

Делаем вывод, что:
3-й столбец соответствует z;
2-й столбец соответствует w;
Ответ: YWZX

Задача 2

По каналу связи передаются сообщения, содержащие только пять букв: Р, А, Н, Е, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы А используется кодовое слово 0; для буквы Е используется кодовое слово 10. Какова минимальная общая длина кодовых слов для всех пяти букв?

Решение:

Если идти по порядку, то нужно каждый раз проверять условия Фано. Что это за условия? Давайте вспоминать. Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода. Отсюда видно, что для следующего кода мы не можем взять 11, потому что тогда мы «закроем» наше дерево и для всех кодов, длина которых больше двух символов, не будут выполняться условия Фано (так как такие коды будут начинаться на 10… или 11… и как их отличать тогда?). Мы также не можем взять 100 или 101, потому что они включают в себя код буквы «Е». Тогда ближайший код, подходящий для нас будет 110. Закодируем Р – 110. Тогда у нас будет свободная ветка 111*, которую мы разделим для букв Н и Т, получив соответственно Н – 1110 и Т – 1111.
Суммарная минимальная длина кода для всех пяти букв будет:
S = 1 + 2 + 3 + 4 + 4 = 14

Наглядная иллюстрация к задаче:

Задача 3

Определите, при каком наибольшем введенном значении переменной s программа выведет число, меньшее, чем 1000.

Решение:

Пусть k - количество итераций цикла.
Тогда, чтобы на экран вывелось число, не большее, чем 1000, необходимо, чтобы цикл выполнился не более чем 333 раза.

Значение s функционально меняется как s = s - k. Но с учетом условного выражения в цикле while, самое последнее s должно быть не менее 20, чтобы цикл работал, потому что

Тогда получаем:

Это легко проверить программным перебором всех вариантов:

Задача 4

Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код, состоящий из двух частей. Первая часть содержит 10 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода содержит 5 символов, каждый из которых может быть одной из десятичных цифр. При этом в базе данных сервере формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для этой части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 40 пользователях потребовалось 1800 байт. Сколько байтов выделено для хранения дополнительной информации о одном пользователе? В ответе запишите только целое число – количество байтов.

Решение:

Пусть V - объем в байтах для одного пользователя. Тогда

Это объем информации складывается из памяти, выделенной на код и на дополнительную информацию о пользователе:

Каждый символ буквенной части кода кодируется минимально возможным одинаковым числом бит:

Каждый символ численной части кода кодируется минимально возможным одинаковым числом бит:

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

То есть на дополнительную информацию выделяется 36 байт. Ответ: 36 байт.

Задача 5

Автомат обрабатывает натуральное число N > 1 по следующему алгоритму:
1) Строится двоичная запись числа N.
2) В конец записи (справа) дописывается вторая справа цифра двоичной записи.
3) В конец записи (справа) дописывается вторая слева цифра двоичной записи.
4) Результат переводится в десятичную систему.
Пример. Дано число N = 11. Алгоритм работает следующим образом.
1) Двоичная запись числа N: 11 = 1011₂.
2) Вторая справа цифра 1, новая запись 10111₂.
3) Вторая слева цифра 0, новая запись 101110₂.
4) Десятичное значение полученного числа 46.
При каком наименьшем значении N в результате работы алгоритма получится R > 100 ? В ответе запишите это число в десятичной системе счисления.

Решение:

Исходное число N → результат получается R. Условие для результата: R > 100. Переведем границу в двоичную систему:

Первым же предположением стоит проверить десятичной число 101₁₀, которое в двоичной будет 1100101₂:

Мы уже нашли наименьшее подходящее число в первом же предположении, поэтому дальше можно было не рассматривать. Но если вам интересно, то следующее подходящее число будет:

Мы же оставномися на 101₁₀ = 1100101₂ и его исходной части до обработки алгоритмом: 11001₂ = 25₁₀

Тогда исходное число получаем, убирая пару разрядов справа:

Ответ: 25

Задача 6

Значение выражения (66 + 6²⁰¹⁹)*6²⁰¹⁹ + 66 + 6⁶ записали в системе счисления с основанием 6. Укажите сумму цифр этой записи.

Решение:

Это задание интересно тем, что число очень большое и на калькуляторе такое сделать не получится. Здесь необходимо понимать принцип решения таких заданий.

Для начала нужно упростить выражение до форму записи в шестеричной системе счисления:

Само число записать полностью не удастся, но структуру можно показать на схеме (в верхней строке порядковые номера разрядов, а в нижней строке - сами разряды в шестиричной системе):

Сумма цифр записи данного выражения: S = 1 + 1 + 5 + 1 + 1 + 5 = 14.

Задача 7

Ниже записана программа. Получив на вход число x, эта программа печатает два числа L и M. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 7.

Решение:

Добавим немного объяснений к данному коду, прокомментировав каждую инструкцию для того, чтобы было понятно начинающим:

1. Введенное значение перевели в число и записали в x
2. Начальная инициализация основных переменных L и M
3. Цикл выполняется до тех пор, пока x остается положительным.
4. L увеличивается на 1 каждую итерацию, поэтому хранит в себе смысл количества шагов цикла.
5. Если x четное, тогда:
→→ в M складывается половинка последнего разряда
6. Число xобрезается справа, т.к. x // 10 – возвращает число без последней цифры (целая часть от деления на 10).

Нам нужно найти наибольшее значение x при котором:

L = 3 ← выполнилось 3 шага цикла
Т.к. на каждом из 3 шагов цикла обрезается последняя цифра от x, тогда x - трехзначное число.

M = 7 ←здесь сумма половинок от четных цифр, входящих в число x. Стоит обратить внимание, что половинки разрядов будут получаться целыми числами, т.к. сложение обернуто в условный оператор, который проверяет текущую цифру x на четность.
Десятичные разряды = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Четные десятичные разряды = {0, 2, 4, 6, 8}
Половинки четных разрядов = {0, 1, 2, 3, 4}
Сумма: 7 = 4 + 3 + 0 = 4 + 2 + 1 = 3 + 2 + 2 = ... Что нам выбрать? Нам нужно собрать число 7 в виде суммы из трех чисел, которые являются половинками четных разрядов. Нужно максимизировать разряды, т.к. необходимо найти наибольшее число x. Получается, что мы могли бы взять 4, 3 и 0 в виде половинок четных разрядов. Однако, 0 – может обозначать, что оператор if просто не сработал (вернул false) и попалась нечетная цифра. Тогда мы можем взять максимально возможную нечетную цифру – 9, и поставить её в самый старший разряд.

Получится:

Поиск ответа также можно найти методом грубой силы, который базируется на переборе всех вариантов решения:

Ответ: 986

💡 Подбора статей по информатике

Разбор 12 задания из ЕГЭ по информатике

Как перенести названия всех файлов текущей директории в текстовый файл .txt в Python?

Среднее арифметическое чисел от a до b

Написал свой калькулятор выхода на пенсию (FIRE)

Работа со StringGrid в Lazarus (Object Pascal)

Введение в работу со строками на языке программирования C (Си)

Как ускорить выполнение цикла? Алгоритм оптимизации циклов

Оптимизация поиска количества делителей | Ускоряем программу в 58 раз | Разбор ЕГЭ по информатике

Работаем с файлами и строками в Pascal : на примере 24 задачи из ЕГЭ по информатике

Работа со строками в C++ : выбрать имена, в которых нет заданной буквы

Задание 25 из ЕГЭ по информатике: разбираемся с делителями

Разбор 26 задачи ЕГЭ по информатике: серьезный подвох

Что делать, если программирование кажется сложным, но очень хочется разобраться в нем? #1

Как оптимизировать программы | Разбор задачи из ЕГЭ по информатике

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

📚 На Дзен недавно появился интересный канал «Читающий Лингвист». Автор канала пишет замечательные рецензии на зарубежную литературу, рассказывает о прочитанном и делает заметки на околокнижные лингвистические наблюдения.

Советую подписаться на этот авторский канал «Читающего Лингвиста»