Это третья часть статьи, в которой мы разбираем алгоритм решения задания 11 ЕГЭ по информатике.
Остальные статьи доступны по ссылкам:
В прошлых статьях мы научились решать 11 задания, в которых требуется определить объем памяти, необходимый для хранения заданного числа идентификаторов, и минимально или максимально возможную длину идентификатора.
Сегодня же познакомимся с последним типом задания 11, где нужно будет определять возможную мощность алфавита.
Для начала давайте вкратце повторим основные формулы. Итак, мощность алфавита означает количество символов, которые можно использовать для записи какого-либо сообщения (идентификатора, пароля, серийного номера и так далее). Вычисляется мощность алфавита по формуле Хартли:
Для её вычисления нам необходимо знать вес одного символа (i). Его же мы можем получить, поделив вес одного сообщения на его длину. Обычно эти значения в том или ином виде уже даны в условии задания.
Но иногда приходится вычислять, например, вес одного сообщения. В таком случае нам должны быть известны количество сообщений и объём памяти, которое занимает это количество сообщений. Тогда останется лишь поделить занимаемый объём памяти на количество этих сообщений.
При делениях почти всегда будут возникать дробные числа, которые требуется округлить в большую или меньшую сторону. Например, если в условии написано, что на N серийных номеров отводится не более M байт, то округлять вес одного серийного номера нужно в меньшую сторону. В противном случае заданное количество серийных номеров просто не поместится в отведённый под них объем памяти.
На этом можем закончить повторение теории и перейти к решению 11 заданий третьего типа. Как и в прошлой статье, сначала подробно распишем полностью ручное решение одного задания, а затем уже порешаем два примера в среде разработки Python.
В прошлый раз мы решали два примера исключительно по формулам в среде разработки. Теперь же закрепим вариант решения через перебор значений в цикле и посвятим уже этому варианту два примера.
Ручное решение
Начнём разбор алгоритма решения с такой формулировки:
«На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 248 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 75 600 серийных номеров требуется более 16 Мбайт памяти.
Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число»
Итак, выпишем имеющиеся у нас данные:
- Длина серийного номера: 248 символов
- Количество хранимых номеров: 75 600 штук
- Объем памяти, необходимый для хранения 75 600 номеров: более 16 Мбайт
Для начала давайте переведём объем памяти из мегабайтов в байты так, как по условию нам сказано «для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт».
Следовательно, нужно число 16 Мбайт умножить на 2 в 20-ой степени:
Именно столько байт требуется, чтобы сохранить в базе данных все серийные номера. Зная это число, можем найти объём памяти, требуемый для хранения всего одного серийного номера:
Получили дробное число, давайте решать, в какую сторону будем его округлять. В условии чётко сказано, что на хранение «75 600 серийных номеров требуется более 16 Мбайт памяти». Ключевое слово здесь – более. Оно и позволяет нам округлять число «221,9» в большую сторону до 222 байт на один серийный номер.
Далее найдём вес одного символа (i), поделив число 222 на количество символов, из которых состоит один серийный номер (248 символов). При этом помните, что вес одного символа исчисляется в битах! Так что сначала переводим число 222 байта в биты и только потом делим на 248:
И снова, все по той же фразе из условия про «более 16 Мбайт» округляем полученное значение «7,1» в большую сторону до 8 бит.
А, чтобы вычислить мощность алфавита, нам достаточно число 2 возвести в 8-ю степень:
Но ответ давать пока рано! От нас требуется найти «минимально возможную мощность алфавита». Следовательно, нам нужно найти такое минимальное число, для хранения которого понадобится 8 бит. Этим числом будет число 129, которое ровно на 1 больше самого большого числа, для хранения которого требуется 7 бит:
И уже число 129 можем смело записывать в ответ.
Перебор значений. Пример 1
Следующим на очереди будет задание с такой формулировкой:
«На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 246 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 703 569 серийных номеров доступно не более 77 Мбайт памяти.
Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число»
Обратите внимание, что это задание является неким «антиподом» предыдущего: теперь у нас выделено «не более» памяти, а искать мы будем уже максимально возможную мощность алфавита, а не минимальную.
Что мы имеем из условия:
- Длина серийного номера: 246 символов
- Количество хранимых номеров: 703 569
- Объем памяти, необходимый для хранения 703 569 номеров: не более 77 Мбайт
Запишем все эти значения в виде переменных, не забыв при этом импортировать функции ceil() и log2() из модуля math:
Далее нам необходимо в цикле перебирать все возможные значения для мощности алфавита в некотором диапазоне. Для таких ситуаций рекомендуем брать диапазоны, допустим, от 1 до 10 и, пока не получите нужный ответ, увеличивать верхний предел.
Поскольку нам нужно найти максимально возможную мощность алфавита, то значения диапазона следует перевернуть через срез [::-1]:
Далее две строки, практически такие же, как были в решении самого первого типа 11 заданий: в них мы вычисляем вес одного символа в битах:
И вес всего сообщения в байтах:
Эти две строки будут идентичны во всех решениях!
Ну а дальше идём по условию: нам сказано, что вес 703 569 номеров (переменная nums) должен быть меньше или равен 31 Мбайт (переменная memory_size). Так и запишем:
Если условие выполнится, то выводим найденную мощность алфавита (переменная alphabet) и завершаем цикл:
Полный код для решения этого задания будет следующим:
После завершения работы программы видим на экране число 8, которое и будет ответом на это задание.
Перебор значений. Пример 2
И заключительная формулировка у нас будет такой:
«На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит.
Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число»
Что мы имеем из условия:
- Длина серийного номера: 2 783 символа
- Количество хранимых номеров: 3 845 627
- Объем памяти, необходимый для хранения 3 845 627 номеров: не менее 11 Гбайт
Все также выписываем данные из условия:
И перебираем значения мощности алфавита в цикле. Работаем с довольно большими значениями, так что возьмём диапазон до 1000:
А весь код программы будет выглядеть так:
В результате работы программа выдаёт значение 257. Его и запишем в ответ на это здание.
А больше задач по этой теме можете найти у нас на сайте.