Задание 11 ЕГЭ по информатике · 824B06
Найти минимальную длину номераПовышеннаяКЭС 2.2
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 4070-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 960 серийных номеров отведено более 212 Кбайт памяти. Определите минимально возможную длину серийного номера. В ответе запишите только целое число.
Показать ответ
140
Подсказки (3)
- Сначала найдите общее количество символов алфавита и минимальное число бит на один символ.
- В алфавите 10+26+4070=4106 символов, поэтому на один символ требуется 13 бит, так как 212<4106≤213.
- Для n символов один номер занимает ⌈13n8⌉ байт. Поскольку 960 номеров занимают более 212⋅1024 байт, минимальное подходящее значение — n=140.
Решение
1. Определим мощность алфавита серийного номера:
10+26+4070=4106
2. Найдём минимальное одинаковое число бит для кодирования одного символа. Поскольку 212=4096<4106≤213=8192, требуется 13 бит на символ.
i=13
3. Для серийного номера длины n количество информации равно 13n бит, поэтому отведённый объём в байтах равен:
b=⌈13n8⌉
4. Память для 960 номеров должна быть больше 212 Кбайт:
960b>212⋅1024
5. Следовательно, на один номер требуется не менее 227 байт. Проверяем минимальную длину: при n=140 получаем ⌈13⋅1408⌉=⌈227,5⌉=228 байт, а при n=139 — ⌈13⋅1398⌉=226 байт. Значит, минимальная длина равна 140.
⌈13⋅1398⌉=226,⌈13⋅1408⌉=228
10+26+4070=4106
2. Найдём минимальное одинаковое число бит для кодирования одного символа. Поскольку 212=4096<4106≤213=8192, требуется 13 бит на символ.
i=13
3. Для серийного номера длины n количество информации равно 13n бит, поэтому отведённый объём в байтах равен:
b=⌈13n8⌉
4. Память для 960 номеров должна быть больше 212 Кбайт:
960b>212⋅1024
5. Следовательно, на один номер требуется не менее 227 байт. Проверяем минимальную длину: при n=140 получаем ⌈13⋅1408⌉=⌈227,5⌉=228 байт, а при n=139 — ⌈13⋅1398⌉=226 байт. Значит, минимальная длина равна 140.
⌈13⋅1398⌉=226,⌈13⋅1408⌉=228
Частые ошибки
- Считать, что для 4106 символов достаточно 12 бит, хотя 4106>212.
- Не округлять объём одного серийного номера вверх до целого числа байт.
- Использовать 1000 байт в одном Кбайте вместо принятого в задаче значения 1024 байта.
Источник: Открытый банк ФИПИ · openfipi.devinf.ru
Похожие задания
11На предприятии каждой изготовленной детали присваивается серийный номер, содержащий десятичные цифры, 26…Найти минимальную длину номера11На предприятии каждой изготовленной детали присваивается серийный номер, содержащий десятичные цифры, 26…Найти минимальную длину номера11На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52…Найти минимальную длину номера11На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры и символы…Найти минимальную длину номера · 4D432F11На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52…Найти минимальную длину номера · A7B37511На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 26…Найти минимальную длину номера · D9271C
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.