О задании
Задание 11 ЕГЭ по информатике нацелено на проверку умений учащихся подсчитывать информационный объём сообщения. Это задание в целом очень похоже на рассмотренное ранее задание 7, где требовалось подсчитать вес изображения, звукового или видеофайла.
Но в случае с 11 заданиями, мы будем работать только с текстовой информацией. Это во многом упрощает решение задания 11, однако, в нём присутствует ряд моментов, на которые стоит обратить внимание, чтобы не случайно не допустить ошибку в ответе.
В заданиях 11 обычно вы можете столкнуться с тремя формулировками условий:
- Определить минимально / максимально возможную длину серийного номера / идентификатора
- Определить объём памяти, необходимый для хранения заданного числа серийных номеров / идентификаторов
- Определить минимально / максимально возможную мощность алфавита
Как вы уже могли догадаться, каждой из этих формулировок будет посвящена отдельная статья. Сегодня же мы поговорим про нахождение длины серийного номера или идентификатора.
Остальные статьи доступны по ссылкам:
Объём текстового сообщения
Итак, в прошлой статье, мы уже разобрались с тем, как хранится информация на компьютере и как найти вес одного символа, зная мощность алфавита. Сейчас мы не будем останавливаться на этом, так что настоятельно рекомендуем ознакомиться с прошлой статьёй и освежить знания.
С символом-то мы уже умеем работать, но, как нетрудно догадаться, одного символа нам явно не хватит, чтобы закодировать нужное сообщение. Этим сообщением, к примеру, может быть как любая текстовая информация, так и пароль, идентификатор или серийный номер изделия.
Что мы знаем точно, так это то, что у этого сообщения должна быть определённая длина — количество символов, из которых состоит каждое сообщение. Тогда, зная вес одного символа (i) и длину сообщения (L), можем вычислить и объём всего сообщения (I):
Если же требуется определить максимально возможную длину одного сообщения (или как в 11 заданиях, длину серийного номера / идентификатора), то из формулы выше выразим значение L:
При этом результат формулы может оказаться дробным. Здесь вспоминаем случай с вычислением веса символа и действуем наоборот: если получилась длина сообщения «2,322», то вместить 3 символа мы никак не сможем. И округлять здесь нужно в меньшую сторону!
Алгоритм решения
Что же, у нас на руках есть все формулы, необходимые для решения этого задания:
Все, то от нас требуется — правильно произвести расчеты, не ошибиться в округлении и перевести результат в нужную размерность.
Правда, при решении 11 заданий есть два варианта:
- Можно решать прямо по формулам как вручную, так и в среде разработке, как мы это делали в задании 7
- Можно перебирать искомые значения в цикле до тех пор, пока не выполнится нужное условие
Мы же рассмотрим решение обоими вариантами, каким из них пользоваться – выбирать вам.
Ручное решение
Итак, начнём мы, конечно же, с самого распространённого и практичного решения – ручного. Первым будет у нас задание с такой формулировкой:
«На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы (с учётом регистра) и символы из 963-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2000 серийных номеров отведено не более 693 Кбайт памяти. Определите максимально возможную длину серийного номера. В ответе запишите только целое число»
Давайте распишем решение этого задания полностью, как если бы мы решали его на бумаге. Для начала найдём мощность алфавита (N):
N = 10 цифр + 52 латинские буквы + 963 спецсимвола = 1025 символов
Отсюда же можем найти вес одного символа (i). Для этого требуется вычислить логарифм по основанию 2 от числа 1025. Что же, ближайшее число к 1025 это 2^10 = 1024. Если бы не последний 1025-ый символ, то мы бы взяли за вес одного символа 10 бит.
Но ради этого символа придётся добавлять еще один бит для веса одного символа, тогда все символы нашего алфавита точно поместятся. Значит, делаем вывод, что вес одного символа (i) равен 11 битам.
Идём дальше, хранятся у нас 2000 сообщений и занимают они до 693 Кбайт памяти, в байтах это будет: 693 · 2^10 байт на все сообщения. Давайте подсчитаем, сколько памяти выделяется на одно сообщение:
Получили дробное число, придётся округлять. Сразу встаёт вопрос, в какую сторону здесь округляем?
Давайте рассуждать. Итак, это вес одного сообщения. На все сообщения у нас выделено не более 693 Кбайт. В таком случае, если вес сообщения будет 355 байт, то 2000 таких сообщений будут весить примерно 693, 35 Кбайт, что нарушает условие задания.
Следовательно, здесь вес одного сообщения нужно округлять в меньшую сторону (354 байт)!
Все, осталось вычислить длину серийного номера по формуле, не забыв перевести 354 байта в биты:
В ответе нас просят записать только целое число, следовательно, записываем 257.
Решение кодом
Далее рассмотрим решение 11 задания первого типа все теми же формулами, но считать будем не вручную, а расписывая все формулы в среде разработки Python.
Этот вариант является более надёжным и точным, который избавит вас от возможных математических ошибок и в явном виде покажет результаты вычислений на каждом этапе.
Формулировка здесь будет следующая:
«При регистрации в компьютерной системе каждому объекту присваивается идентификатор, содержащий десятичные цифры, 26 латинских букв в верхнем регистре и символы из 2013-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 2050 идентификаторов отведено более 709 Кбайт памяти. Определите минимально возможную длину идентификатора. В ответе запишите только целое число»
Для начала импортируем нужные функции. Здесь нам понадобится математическая функция ceil() для округления «вверх», то есть до большего числа и функция логарифма log(). Обе они из модуля math:
Выпишем из условия мощность алфавита, вес 2050 идентификаторов и количество этих идентификаторов:
Далее все, как и в ручном методе. Ищем вес одного символа и округляем значение до большего числа:
Аналогично поступаем и с весом одного идентификатора:
Осталось лишь найти длину идентификатора (L) и вывести её на экран:
Весь код для решения этого задания будет таким:
В результате работы программы на экран выводится ответ – 237.
Перебор значений
Итак, мы решили два задания, основываясь только на вычислениях по известным нам формулам. Но в 11 заданиях можно пойти и другим путём – перебирать длину сообщения в цикле и выводить на экран ту, которая будет удовлетворять условиям.
Нельзя сказать, что этот подход избавит вас от знаний формул. Но до него все же можно дойти логически, что мы постараемся и показать далее.
Формулировка 11 задания будет такая:
«На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры и символы из 17-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 7 564 230 серийных номеров требуется более 31 Мбайт памяти.
Определите минимально возможную длину серийного номера»
Как обычно, импортируем нужные функции и выписываем данные значения:
Далее пишем цикл, в котором будем перебирать возможную длину серийного номера. Пока возьмем диапазон значений (range()) от 1 до 10. Если среди этих значений не будет нужной длины, то увеличим верхний предел.
Затем в цикле находим вес одного символа в битах (i) и округляем «вверх», назовём эту переменную bits:
Итак, сколько у нас весит серийный номер? Если у нас есть вес одного символа, то чтобы найти вес какого-то количества символов, нужно просто перемножить вес на количество, верно?
Давайте так и сделаем, только вместо известного количества символов подставим нашу переменную serial_num_len из цикла:
Это будет вес одного серийного номера в байтах, так что не забывайте про деление на 8!
Ну а дальше идём по условию: нам сказано, что вес 7 564 230 номеров (переменная nums) должен быть больше или равен 31 Мбайт (переменная memory_size). Так и запишем:
Если условие выполнится, то выводим первую найденную длину серийного номера и завершаем цикл:
Весь код для решения этого задания выглядит так:
В итоге получаем ответ на это задание – 7.
К рассмотренным способам мы еще вернёмся при разборе других типов 11 заданий ЕГЭ по информатике. Следующая же статья посвящена определению объёма памяти, необходимого для хранения заданного числа серийных номеров / идентификаторов.
