Это вторая часть статьи, в которой мы разбираем алгоритм решения задания 11 ЕГЭ по информатике.
Остальные статьи доступны по ссылкам:
В прошлой статье мы познакомились с формулами для определения объёма текстового сообщения и научились решать 11 задания, в которых необходимо найти длину серийного номера или идентификатора.
Эта же статья посвящена второму типу 11 заданий, в котором условие содержат такую фразу: «Определите объём памяти, необходимый для хранения заданного числа серийных номеров / идентификаторов».
Ранее мы говорили, что 11 задания предполагают три возможных варианта решения:
- Полностью ручное решение
- Решение по формулам, но в среде разработки
- Перебор значений в цикле for
Однако в случае с рассматриваемым в этой статье типом, третий вариант – перебор значений – будет недоступен. Здесь от нас требуется буквально вычислить точный объём памяти, а не подобрать минимальный/максимальный. Так что решать все задания будем только по формулам.
Полностью ручное решение распишем для одного примера, а два других будем решать уже в среде разработки. Больше заданий с подробными решениями вы всегда можете найти у нас на сайте.
Навигация по странице
Ручное решение
Первой рассмотрим задание с такой формулировкой:
Задание 1101
«При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов.
В ответе запишите только целое число – количество Мбайт»
Начнём решение с определения мощности алфавита (N): 10 цифр + 4090 спецсимволов, итого мощность алфавита равна 4100 символов.
Сразу же найдём вес одного символа. Вспоминаем степени двойки: ближайшее число к 4100 – это 2 в 12-ой степени или же 4096. Но в 12 бит у нас не влезут все 4100 символов, так что придётся брать на один побольше – 13 бит на символ.
Из условия мы знаем длину идентификатора (L), равную 317 символов, и только что вычислили вес одного символа (i) в битах, следовательно, можем найти вес одного идентификатора в байтах:
Чтобы все символы точно уместились, округлим вес одного идентификатора в большую сторону, до значения в 516 байт.
Теперь осталось вычислить объём памяти, необходимый для хранения всех 262 144 идентификаторов. Для этого просто умножим вес одного идентификатора на их количество и переведём полученное значение в мегабайты:
В ответе запишем число 129.
Решение кодом. Пример 1
Далее уже не будем так подробно расписывать каждое действие. Алгоритм решения будет аналогичным, только все операции мы будем проводить в среде разработки.
Формулировка второй задачи следующая:
Задание 1110
«При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов и содержащий только символы 26-символьного набора строчных латинских букв и десяти арабских цифр. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 9 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 30 пользователях. В ответе запишите только целое число – количество байт»
Что мы имеем из условия:
- Длина пароля: 7 символов
- Алфавит: 10 цифр и 26 строчных букв латинского алфавита
- Дополнительные данные в размере 9 байт на каждого пользователя
- Всего пользователей в системе: 30
Давайте все эти данные и запишем в переменные:
from math import ceil, log2
L = 7
N = 26 + 10
other_data = 9
users = 30
Вычисляем вес одного символа:
i = ceil(log2(N))
Далее вычисляем вес одного пароля:
I = ceil(L * i / 8)
Осталось лишь сложить полученный вес одного пароля с 9 байтами дополнительных данных и умножить эту сумму на количество пользователей:
I_30 = (I + other_data) * users
В итоге получаем такой код для решения этого задания:
from math import ceil, log2
L = 7
N = 26 + 10
other_data = 9
users = 30
i = ceil(log2(N))
I = ceil(L * i / 8)
I_30 = (I + other_data) * users
print(I_30)
После выполнения этой программы, видим на экране значение 450, которое и пишем в ответ.
Решение кодом. Пример 2
Рассмотрим еще один пример на решение в среде разработки. В этот раз будет такая формулировка 11 задания:
Задание 1115
«При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 5 символов и содержащий только десятичные цифры и символы из 7084-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 22 528 идентификаторов. В ответе запишите только целое число – количество Кбайт.»
По аналогии с прошлым решением выпишем все имеющиеся у нас на руках данные:
- Длина идентификатора: 5 символов
- Алфавит: 10 цифр и 7084 спецсимволов
- Количество идентификаторов: 22 528 штук
Переносим эти данные в нашу среду разработки:
from math import ceil, log2
L = 5
N = 10 + 7048
ids = 22_528
Вычисляем вес одного символа:
i = ceil(log2(N))
Теперь вычисляем вес одного идентификатора:
I = ceil(L * i / 8)
И, наконец, вычислим требуемый объем памяти и переведём его в килобайты:
I_all = I * ids * 2 ** -10
Вся наша программа выглядит так:
from math import ceil, log2
L = 5
N = 10 + 7048
ids = 22_528
i = ceil(log2(N))
I = ceil(L * i / 8)
I_all = I * ids * 2 ** -10
print(I_all)
А в результате получаем ответ на это задание –198.
В следующей статье мы завершим работу с 11 заданиями и научимся вычислять мощность алфавита.