Задание 11 ЕГЭ по информатике · C12A06
Найти мощность алфавитаПовышеннаяКЭС 2.2
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 196 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 564 895 серийных номеров потребовалось не менее 145 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
Показать ответ
1025
Подсказки (3)
- Сначала определите минимальное число байт, необходимое для хранения одного серийного номера.
- Если один символ кодируется k битами, то номер занимает ⌈196k8⌉ байт. Общий объём должен быть не меньше 145⋅220 байт.
- Получается, что k=11. При k битах мощность алфавита может быть не больше 2k, а для минимального значения при ровно 11 битах достаточно взять 210+1=1025 символов.
Решение
1. Переведём минимальный требуемый объём памяти в байты и найдём, сколько байт должно приходиться на один серийный номер.
145⋅220=152043520 байт
2. Делим общий объём на количество серийных номеров. Так как объём должен быть не меньше указанного, требуется не менее 270 байт на один номер.
⌈152043520564895⌉=270 байт
3. Пусть один символ кодируется k битами. Тогда один номер занимает ⌈196k8⌉ байт. Проверяем минимальное подходящее значение: при k=10 получаем 245 байт, а при k=11 — 270 байт.
⌈196⋅108⌉=245,⌈196⋅118⌉=270
4. Чтобы кодировать символы 11 битами, алфавит должен содержать больше 210 символов, но не больше 211. Минимальная возможная мощность такого алфавита равна 210+1.
210+1=1025
145⋅220=152043520 байт
2. Делим общий объём на количество серийных номеров. Так как объём должен быть не меньше указанного, требуется не менее 270 байт на один номер.
⌈152043520564895⌉=270 байт
3. Пусть один символ кодируется k битами. Тогда один номер занимает ⌈196k8⌉ байт. Проверяем минимальное подходящее значение: при k=10 получаем 245 байт, а при k=11 — 270 байт.
⌈196⋅108⌉=245,⌈196⋅118⌉=270
4. Чтобы кодировать символы 11 битами, алфавит должен содержать больше 210 символов, но не больше 211. Минимальная возможная мощность такого алфавита равна 210+1.
210+1=1025
Частые ошибки
- Использовать 145000000 байт вместо перевода 145 Мбайт в двоичные байты.
- Забыть округлить число байт на один серийный номер вверх.
- Взять мощность алфавита равной 211 вместо минимального значения 210+1.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
11На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 315 символов. В базе…Найти мощность алфавита · 2F2F9611На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе…Найти мощность алфавита · 35BCB411На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 76 символов. В базе…Найти мощность алфавита · 53E29711На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 124 символов. В базе…Найти мощность алфавита · 64B72411На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 204 символов. В базе…Найти мощность алфавита · D70A5011На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 199 символов. В базе…Найти мощность алфавита · 9BDB2511На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 212 символов. В базе…Найти мощность алфавита · B097BE
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.