- Задание 11. Вычисление количества информации.. ЕГЭ 2024 по информатике
- Что нужно знать, чтобы решить задание 11:
- Задачи для практики
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Задача 5
- Задача 6
- Задача 7
- Задача 8
- Задача 9
- Задача 10
- Задача 11
- Задача 12
- Задача 13
- Задача 14
- Задача 15
- Задача 16
- Теория для 11 задания ЕГЭ по информатике
- Практика
Задание 11. Вычисление количества информации.. ЕГЭ 2024 по информатике
Средний процент выполнения: 57.5%
Ответом к заданию 11 по информатике может быть последовательность цифр, чисел или слов. Порядок записи имеет значение.
Что нужно знать, чтобы решить задание 11:
- Арифметические операции в вашем языке программирования
- Условный оператор
- Функции и процедуры
Теория к 11 заданию: читать
Задачи для практики
Задача 1
Каждый пользователь сети обладает паролем вида XXYYYXZ, где X — строчная буква английского алфавита, Y —цифра 0, 1, · · · , 9 и Z — либо 0, либо 1. Кодирование паролей осуществляется посимвольно. Каждый из символов X, Y и Z кодируется минимально возможным количеством бит, а каждый пароль занимает одинаковое целое число байт. Определите объём памяти (в байтах), необходимый для хранения 18 паролей. В ответе запишите только число, слово «байт» писать не нужно.
Решение
Всего три строчных буквы в пароле (X) и на их кодирование потребуется: всего 26 букв, значит на одну букву 5 бит, а на три буквы 15 бит;
Всего три цифры в пароле (Y) и на их кодирование потребуется: всего 10 цифр, значит на одну цифру 4 бита, а на три цифры 12 бит;
На конце пароля символ Z, на кодирование которого потребуется 1 бит, поскольку всего 2 различных значения.
Итого 15+12+1=28 бит или 28/8=3.5=4 байта. На 18 паролей: 18 * 4 = 72
Задача 2
В книгохранилище специальное устройство каждый час записывает время замера (в часах—от 0 до 23), показания относительной влажности (от 48% до 62%) и температуры воздуха (от 13 ◦C до 22 ◦C). Для записи каждого из трёх показателей используется минимально возможное количество бит, одинаковое для всех показателей одного типа.
Определите информационный объём сообщения (в битах), записанного устройством после того, как было сделано 30 замеров.
Решение
На запись часов потребуется 5 бит, поскольку всего 24 различных значения
На запись влажности потребуется 4 бита, поскольку всего 15 различных значений
На запись температуры потребуется 4 бита, поскольку всего 10 различных значений
Итого: 5+4+4=13 бит на запись одного замера. На 30 замеров = 30*13=390 бит
Задача 3
В соревнованиях по тяжёлой атлетике результат по сумме двух упражнений может принимать целочисленное значение от 210 кг до 240 кг. Специальное устройство регистрирует результат каждого участника, записывая его номер от 1 до 120 (с использованием минимально возможного количества бит) и результат спортсмена по сумме двух упражнений (также с использованием минимально возможного количества бит).
Определите информационный объём сообщения (в битах), записанного устройством после окончания соревнований, если в соревнованиях участвовало 120 спортсменов.
Решение
Для кодирования числа от 210 до 240, то есть одного из 30 чисел потребуется 5 бит.
Номер участника представляет из себя одно из 120 чисел, значит на запись номера потребуется 7 бит.
Запись об одном спортсмене -это его номер и информация о двух упражнениях, то есть $7 + 5 = 12 $ бит
Информация о 120 спортсменах — это $120 * 12 = 1440$ бит
Задача 4
В некоторой стране автомобильный номер длиной в 5 символов составляют из заглавных букв (всего используется 24 различные буквы) и десятичных цифр, записанных в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование: каждый символ кодируется одинаковым и минимально возможным количеством бит). Определите объём памяти (в байтах), отводимый этой программой для записи 40 номеров.
Решение
Для кодирования 24 различных букв и 10 цифр потребуется 6 бит.
Для хранения всего номера: 5 * 6 = 30 бит или 4 байта, поскольку записывается минимально возможным и одинаковым целым количеством байт
Тогда для записи 40 номеров: 40 * 4 = 160 байт
Задача 5
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов.Пароль содержит только символы из следующего набора: 22 фиксированные строчные буквы латинского алфавита, хотя бы две десятичные цифры и хотя бы два из символов: !, @, #, $, +, ^, &, *, %.
При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. Кроме собственно пароля, о каждом пользователе в системе хранятся дополнительные сведения, для чего выделено 4 байта для каждого пользователя.
Сколько байт потребуется для хранения данных о 80 пользователях? В ответе запишите только целое число—количество байт.
Решение
Пароль составляется из набора, содержащего 22+10+9=41 символа, на кодирование которых потребуется 6 бит, значит на кодирование пароля потребуется 7 * 6 = 42 бита или 6 байт (42 / 8 = 5.25)
Тогда информация о пользователе (пароль + доп.сведения) будет весить: 6 + 4 = 10 байт
Информация о 80 пользователях будет весить 80*10 = 800 байт
Задача 6
Идентификационный номер состоит из 8 символов. В качестве первого символа используют 26 различных букв, остальные символы — десятичные цифры (пример номера Z1234567). Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом для первого символа отводится один байт, а каждая цифра кодируется одинаковым, минимально возможным количеством бит. Определите объём памяти (в байтах), отводимый этой программой для записи 50 номеров.
Решение
Для кодирования каждой цифры необходимо 4 бита. Следовательно, для кодирования 7-ми цифр потребуется 4 · 7 = 28 бит. Определим минимальное количество байтов для кодирования этих цифр: 28/8 = 3,5. Следовательно, необходимо 4 байта.
Так как ещё один байт требуется для кодирования первого символа, то для одного номера необходимо 4 + 1 = 5 байтов. Значит, 50 номеров займут 5 · 50 = 250 байт.
Задача 7
В некоторой стране автомобильный номер длиной 8 символов составляют из заглавных букв (всего используется 20 различных букв) и десятичных цифр, записанных в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование: каждый символ кодируется одинаковым и минимально возможным количеством бит). Определите объём памяти (в байтах), отводимый этой программой для записи 30 номеров.
Решение
Найдём наименьшее количество бит, которым можно закодировать не менее 30 символов: 20 различных букв и 10 десятичных цифр. Для этого найдём такое наименьшее натуральное число N, при котором 2N ≥ 30. Так как 24 < 30 < 25, то минимальное количество бит, необходимое для кодирования 30 символов, равно 5. Значит, для кодирования одного символа требуется 5 бит. Номер состоит из 8 символов. Для его кодирования потребуется 5 ∗ 8 = 40 бит. Поскольку номер кодируется минимально возможным количеством байт, то для его кодирования используют 5 байт. Следовательно, для 30 номеров отводится 5 ∗ 30 = 150 байт.
Задача 8
Запись для каждого пользователя при регистрации состоит из логина и пароля. Логин состоит из 12 символов, которые пользователь придумывает сам из 14 фиксированных строчных букв латинского алфавита и 6 цифр. Каждый такой логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Далее к логину каждого пользователя дописывается пароль, автоматически сгенерированный системой.
Для хранения сведений о 100 пользователях потребовалось 1100 байт. Сколько байт выделено для хранения пароля одного пользователя? В ответе запишите только целое число—количество байт.
Решение
Определим минимальное количество бит, необходимое для кодирования логина пользователя. n битами можно закодировать 2n различных значений. По условию задачи для логина используется 14 фиксированных строчных букв латинского алфавита и 6 цифр, то есть всего 20 различных символов. Следовательно, необходимо определить наименьшее количество бит, которыми можно закодировать не менее 20 различных значений. То есть найти такое наименьшее натуральное число N, при котором 2N ≥ 20. Так как 24 < 20 < 25, то минимальное количество бит, необходимое для кодирования одного символа, равно 5. Логин состоит из 12 символов. Следовательно, для его записи потребуется 12 · 5 = 60 бит.
По условию задачи логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт. Для нахождения необходимого количества байтов округляем в большую сторону значение 60/8. То есть для логина потребуется 8 байт.
Так как для хранения записей о 100 пользователях потребуется 1100 байт, то на одного пользователя программой отводится 1100/100 == 11 байт.
Учитывая, что 8 байт отводится под логин, получаем, что для пароля отводится 3 байта.
Задача 9
Каждый пользователь сети обладает паролем вида XXZXYXXZ, где X — строчная буква английского алфавита (всего используется 26 различных символов), Y — цифра 0, 1, · · · , 9 и Z — либо 0, либо 1. Кодирование паролей осуществляется посимвольно. Каждый из символов X, Y и Z кодируется минимально возможным количеством бит, а каждый пароль занимает одинаковое целое число байт. Определите объём памяти (в байтах), необходимый для хранения 20 паролей. В ответе запишите только число, слово «байт» писать не нужно.
Решение
Задача 10
Запись для каждого пользователя при регистрации состоит из логина и пароля. Логин состоит из 15 символов, которые пользователь придумывает сам, и содержит только символы из 17-символьного набора: А, В, C, D, Е, F, G, H, K, L,M, N, O, P, Q, R, S.
Каждый такой логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование, и все символы кодируются одинаковым и минимально возможным количеством бит). Далее к логину каждого пользователя дописывается пароль, автоматически сгенерированный системой.
Для хранения сведений о 40 пользователях потребовалось 640 байт. Сколько байт выделено для хранения пароля одного пользователя? В ответе запишите только целое число—количество байт.
Решение
Задача 11
Запись для каждого пользователя при регистрации состоит из логина и пароля. Логин состоит из 25 символов, которые пользователь придумывает сам, и содержит только символы из 14-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N, O, P. Каждый такой логин в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование, и все символы кодируются одинаковым и минимально возможным количеством бит). Далее к логину каждого пользователя дописывается пароль, автоматически сгенерированный системой.
Для хранения сведений о 50 пользователях потребовалось 1000 байт. Сколько байт выделено для хранения пароля одного пользователя? В ответе запишите только целое число—количество байт.
Решение
Задача 12
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов. Пароль содержит прописные и строчные латинские буквы (алфавит содержит 26 букв), хотя бы 3 десятичные цифры и хотя бы один из символов: !, @, #, $, %, ^, &, *. При этом используют посимвольное кодирование паролей, все символы кодируют минимально возможным количеством бит (возможно, неодинаковым).
В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт.
Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт, одинаковое для каждого пользователя.
Для хранения сведений о 30 пользователях потребовалось 660 байт. Сколько байт выделено для хранения дополнительных сведений для одного пользователя? В ответе запишите только целое число—количество байт.
Решение
Задача 13
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 12 символов. Пароль содержит прописные и строчные латинские буквы (алфавит содержит 26 букв), хотя бы две десятичные цифры и хотя бы один из символов: !, @, #, $, %, ^, &, *. При этом используют посимвольное кодирование паролей, все символы кодируют минимально возможным количеством бит (возможно, неодинаковым). В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт, одинаковое для каждого пользователя.
Для хранения сведений о 25 пользователях потребовалось 675 байт. Сколько байт выделено для хранения дополнительных сведений для одного пользователя? В ответе запишите только целое число—количество байт.
Решение
Задача 14
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов. Из соображений информационной безопасности каждый пароль должен содержать только символы из следующего набора: прописные и строчные латинские буквы (алфавит содержит 26 букв), хотя бы одну десятичную цифру и хотя бы один из 8 символов: &, #, $, *, !, @, +, —.
При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимальное возможное целое число байт.
Сколько байт потребуется для хранения 120 паролей? В ответе запишите только целое число—количество байт.
Решение
Задача 15
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов. Пароль содержит только символы из следующего набора: строчные латинские буквы (алфавит содержит 26 букв), хотя бы две десятичные цифры и хотя бы один из символов: !, %, *. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. Кроме собственно пароля, о каждом пользователе в системе хранятся дополнительные сведения, для чего выделено целое число байт—одинаковое для каждого пользователя.
Для хранения сведений о 50 пользователях потребовалось 800 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число— количество байт.
Решение
Задача 16
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов. Пароль содержит только символы из следующего набора: прописные и строчные латинские буквы (алфавит содержит 26 букв), хотя бы две десятичные цифры и хотя бы один из символов: !, %. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. Кроме собственно пароля, о каждом пользователе в системе хранятся дополнительные сведения, для чего выделено целое число байт—одинаковое для каждого пользователя.
Для хранения сведений о 80 пользователях потребовалось 1200 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.
Решение
Теория для 11 задания ЕГЭ по информатике
Для начала разберёмся с понятием Рекурсия.
Рекурсия — вызов функции внутри самой себя.
Давайте разберёмся на примере. Предположим, вы где-то работаете и вам каждый день платят по 1000 рублей. Вы хотите узнать, сколько у вас сейчас денег. Давайте попробуем их посчитать через рекурсию.
Сегодняшняя сумма ваших денег — это вчерашняя сумма, увеличенная на 1000 рублей.
А вчерашняя сумма денег — это позавчерашняя сумма, увеличенная на 1000 рублей.
И так можно продолжать до бесконечности. Ситуацию можно описать формулой:
F(n) = F(n-1)+1000, где F(n) — сумма денег в n-ый день, а F(n-1) — сумма денег в предыдущий n-1-ый день. Такая формула называется рекуррентной.
Но так мы можем считать до бесконечности. Сумма, которая была у нас 451 день назад = сумме, которая была 452 назад, увеличенной на 1000. Именно поэтому нам необходимо условие выхода из рекурсии:
Предположим, что в 1-ый день у нас было 0 рублей. А сейчас 100-ый день, тогда если n > 1, то нашу сумму можно посчитать по формуле
F(n) = F(n-1)+1000,
а если n = 1, то
F(n) = 0 — это и есть условие выхода из рекурсии.
В виде кода (язык Python) это можно записать как:
def f(n):
ᅠif n > 1:
ᅠᅠreturn f(n-1)+1000
ᅠelse:
ᅠᅠreturn 0
Практика
Пример
На рисунке записан рекурсивный алгоритм F. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(4)?
Решение
Обратим внимание, что вывод значения на экран происходит в тот момент, когда запускается наша процедура. Следовательно, как только мы вызвали F(4), на экране появилось первое число. Консоль вывода будет выглядеть так:
| 4
Далее проверяется условие n > 1. 4 явно больше 1, значит заходим внутрь условного оператора, оказываемся на строчке f(n-1). Эта строчка запускает процедуру f(n-1). Важный момент: сейчас текущая процедура f(n) встала на паузу и ждёт, пока процедура f(n-1) полностью завершит свою работу. Это как в Марио попасть с основного уровня на бонусный. Пока мы на бонусном уровне, основной уровень стоит на паузе.
Схему проще всего представлять в виде дерева:
Теперь запустилась процедура F(3). Сразу же в консоль отправляется число «3». Теперь в консоли мы наблюдаем:
| 4 3
Далее проверяется условие n > 1. 3 больше, чем 1, значит вновь оказываемся на строчке f(n-1) и запускаем f(2):
F(2) выводит на экран число «2»:
| 4 3 2
2 > 1, значит F(2) запускает F(n-1), то есть F(1):
F(1) выводит на экран число «1»:
| 4 3 2 1
Проверка условия n > 1 даёт нам False. 1 не больше, чем 1. Значит процедура F(1) завершает свою работу. Возвращаемся в процедуру F(2). Там мы остановились на строчке F(n-1), которая только что успешно завершила свою работу. Переходит к следующей строчке: F(n-2), которая вызовет F(0):
F(0) выведет на экран 0 и тут же завершит свою работу, не пройдя условие n > 1:
| 4 3 2 1 0
Больше в F(2) делать нечего, она тоже завершает свою работу. Мы возвращаемся в F(3), где остановились на строчке F(n-1). Теперь переходим к строчке F(n-2) и вызываем F(1):
Мы уже вызывали F(1) ранее, но сейчас он вызывается заново, выводит на экран «1» и завершается, не пройдя условие n > 1:
| 4 3 2 1 0 1
Возвращаемся в F(3), она завершила свою работу. Теперь возвращаемся в самое начало — процедуру F(4). Напоминаю, что в ней мы остановились на строчке F(n-1). Теперь, когда она полностью завершила свою работу, мы приступаем к следующей строке F(n-2) и вызываем F(2). Ранее мы уже вызывали F(2) и знаем, что дерево выглядеть будет так:
И выведет поочередно «2» «1» «0»:
| 4 3 2 1 0 1 2 1 0
После чего все процедуры завершат свою работу, а значит и программа завершит свою работу. Осталось сложить числа, выведенные на экран, согласно условию:
4+3+2+1+0+1+2+1+0=14
Ответ: 14