В данной статье разберем с вами подробное решение типовых задач, с которыми приходится сталкиваться ученикам при подготовке к ЕГЭ по информатике. Эти задания еще долго будут актуальны при подготовке к ЕГЭ. Некоторые задачи, связанные с программированием, я попытался разобрать двумя способами:
1 способ: аналитическое решение, которое можно выполнить на черновике без компьютера
2 способ: численное решение, реализованное с помощью метода грубой силы (брутфорс или перебор решений с помощью модернизации исходного кода программы). Если вам что-то будет непонятно, то пишите свои вопросы в комментариях на Дзен к этой статье. А если вам понадобятся индивидуальные занятия по физике, математике или информатике, то мои контакты вы сможете найти выше.
А пока попрошу подписаться на мой канал в telegram IT mentor . Краткие заметки и наблюдения по физике, математике, программированию, железу и технике В моем telegram я выкладываю компактные решения в виде pdf. Советую подписаться 🙂
Задание №6 ЕГЭ по информатике: анализ программ (задача из статграда)
Задача 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.
Решение 2 задания || ЕГЭ Информатика
Суммарная минимальная длина кода для всех пяти букв будет:
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₂:
Определите при каком наибольшем введенном значении переменной s программа выведет число 101
Задание ЕГЭ по информатике
Линия заданий — 6
Наслаждайтесь интересным учебником и решайте десятки тестов на Studarium,
мы всегда рады вам! =)
18983. Определите, при каком введённом значении переменной s программа выведет число 10.
Проверить Показать подсказку
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке 😉
При обращении указывайте id этого вопроса — 18983.
Источник: studarium.ru
Определите при каком наибольшем введенном значении переменной s программа выведет число 101
Ответ:
Объяснение:
пользовался программой на Python’е
for i in range(-1000, 1000):
etojan 1 год назад
Светило науки — 151 ответ — 1186 раз оказано помощи
За каждую итерацию цикла n возрастает на 8. Нам нужно минимум 125 итераций, чтоб получить n > 1000, потому что 4 + 8*125 > 1000, а 4 + 8*124 < 1000. Можно и больше 125 итераций, об этом дальше
За каждую итерацию цикла s растёт на 5, пока не превысит 400. Нам нужно как минимум 125 итераций, как мы выяснили, а для этого стартовое значение s должно быть больше чем
400 — 5*125 = 400 — 625 = -225, но меньше или равно
400 — 5*124 = 400 — 620 = -220.
Ну и на отрезке (-225; -220] максимум найти несложно.
Если число итераций N будет больше 125, то больше будет разница 400 — 5*N , а значит меньше будет стартовое значение S, что нас не устраивает.
Ответ: -220
Источник: znanija.pro