Подтема 3 из 6
Наибольшее значение: «не более»
Как найти наибольшие длину пароля, алфавит и число записей, когда памяти «не более» заданной.
Длина по байтам
Пароль из алфавита задачи темы занимает 12 байт. Какой он длины?
По числу байт длину точно не восстановить: округление вверх прячет пустой хвост. 12 байт — это больше 88 бит (иначе хватило бы 11 байт) и не больше 96. Подходят 6 · 15 = 90 и 6 · 16 = 96 бит, то есть K = 15 или K = 16; 6 · 14 = 84 бита уместились бы в 11 байт.
Поэтому в обратных задачах спрашивают наибольшее или наименьшее значение. Они зависят от слов условия: «не более» — в этой подтеме, «более» и «не менее» — в подтеме 4.
Наибольшая длина
Для 40 пользователей выделено не более 1200 байт, сведения — 18 байт. Какой наибольшей длины может быть пароль?
«Не более» сначала переводят в наибольший размер одной записи, потом — в наибольшее число битов пароля. Запись не больше 1200 / 40 = 30 байт, пароль не больше 30 − 18 = 12 байт = 96 бит. Значит, 6 · K ≤ 96, K ≤ 16.
Проверь найденную длину и следующую. K = 16: 96 бит = 12 байт, 40 · (12 + 18) = 1200 — подходит. K = 17: 102 бита → 13 байт, 40 · 31 = 1240 — больше 1200. Ответ 16.
Программа перебирает длины (), для каждой считает объём прямо, как в подтемах 1–2, и запоминает последнюю подходящую ():
from math import ceilbest = 0for k in range(1, 100): password = ceil(k * 6 / 8) if 40 * (password + 18) <= 1200: best = kprint(best)Условие <= 1200 — дословно «не более 1200»: перебору не нужно думать об округлениях.
Тонкости:память не делится нацело
Пусть выделено не более 1210 байт. 1210 / 40 = 30,25, но запись — целое число байт, поэтому она по-прежнему не больше 30: при 31 байте 40 записей займут 1240. При «не более» дробь отбрасывают.
Наибольший алфавит
Длина пароля — 15, ограничение то же: не более 1200 байт на 40 пользователей. Какова наибольшая мощность алфавита?
Сначала находят, сколько битов на символ можно себе позволить, а потом — сколько символов закодирует столько битов: N = 2ⁱ. Пароль не больше 96 бит: 15 · i ≤ 96, i ≤ 6,4, то есть i = 6. Шесть битов кодируют до 2⁶ = 64 символов.
Проверка соседа: N = 64 — 6 бит, 90 бит, 12 байт, всего 1200 — подходит; N = 65 — 7 бит, 105 бит, 14 байт, всего 1280 — нет. Ответ 64, а не 62: алфавит задачи можно расширить ещё на 2 символа.
from math import ceilbest = 0for n in range(1, 1000): password = ceil(15 * bits(n) / 8) if 40 * (password + 18) <= 1200: best = nprint(best)Если спрашивают, сколько специальных знаков можно добавить к цифрам и буквам, из наибольшего алфавита вычитают известные символы: 64 − 62 = 2.
Наибольшее число записей
О каком наибольшем числе пользователей можно хранить сведения в 1 Кбайт?
Наибольшее число записей — целая часть от деления памяти на размер записи. 1024 / 30 = 34,13…: 34 записи займут 1020 байт, 35-я уже не поместится. Неполную запись хранить нельзя, поэтому дробь отбрасывают.
Сначала округляют вверх размер одной записи, потом делят память и округляют вниз. В Python это деление нацело .
На экзамене числа крупные: номер детали из 200 символов, 300 000 номеров, не более 64 Мбайт. Какова наибольшая мощность алфавита? Тот же перебор, только по числу битов:
from math import ceilbest = 0for i in range(1, 30): if 300000 * ceil(200 * i / 8) <= 64 * 2 ** 20: best = iprint(best, 2 ** best)Восемь битов на символ — наибольший алфавит 2⁸ = 256. Вручную: на номер не больше 64 · 2²⁰ / 300 000 = 223,6… → 223 байта = 1784 бита, 1784 / 200 = 8,92 → 8 бит.
Итого
- По байтамдлина — диапазон, а не одно число
- Не болеезапись — целая часть памяти / число записей
- ДлинаK · i ≤ биты пароля, проверить K + 1
- Алфавитнаибольшее i, ответ 2ⁱ
- Записипамять // запись
- Pythonперебор кандидатов, условие дословно: <=
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Наибольшая длина по 9 байтам
Пароль использует алфавит мощностью 40 и занимает минимально возможные 9 байтов. Какой наибольшей длины может быть пароль?
Введите число.
Подсказка
9 байтов вмещают 72 бита: раздели на биты одного символа.
Решение
40 символам нужно 6 бит. 9 байтов — больше 64 бит (иначе хватило бы 8 байтов) и не больше 72. Длина 12 даёт 72 бита — ещё 9 байтов, длина 13 — 78 бит, уже 10 байтов. Наибольшая длина 12.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i ok = [k for k in range(1, 30) if ceil(k * bits(40) / 8) == 9]print(max(ok))Ответ: 12
Наименьший алфавит по 9 байтам
Пароль содержит 12 символов и занимает минимально возможные 9 байтов. Какова наименьшая возможная мощность алфавита?
Введите число.
Подсказка
Сначала найди число битов на символ, потом наименьший алфавит для него.
Решение
9 байтов — больше 64 бит и не больше 72: 64 < 12i ≤ 72, значит, i = 6. Шесть битов нужны алфавитам от 33 до 64 символов, наименьший из них — 33.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i ok = [n for n in range(2, 300) if ceil(12 * bits(n) / 8) == 9]print(min(ok))Ответ: 33
Наибольшая длина пароля
Алфавит содержит 33 символа. Дополнительные сведения занимают 3 байта на пользователя. Для 100 пользователей доступно не более 2 Кбайт. Найди максимальную длину пароля.
Введите число.
Подсказка
От наибольшего размера записи — к наибольшему числу битов пароля.
Решение
33 символам нужно 6 бит. Запись не больше 2048 / 100 = 20,48 → 20 байтов, пароль не больше 20 − 3 = 17 байтов = 136 бит, 136 / 6 = 22,6 → 22 символа. Проверка: 23 символа — 138 бит → 18 байтов, 100 · 21 = 2100 > 2048.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i record = 2048 // 100ok = [n for n in range(1, 60) if ceil(n * bits(33) / 8) + 3 <= record]print(max(ok))Ответ: 22
Длина серийного номера
Серийный номер содержит десятичные цифры, заглавные и строчные латинские буквы и символы из специального алфавита в 700 символов. Каждому номеру отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Для хранения 3000 номеров отведено не более 500 Кбайт. Определи максимально возможную длину номера.
Введите число.
Подсказка
Алфавит — цифры, буквы обоих регистров и специальные знаки.
Решение
Алфавит — 10 цифр, 52 буквы и 700 знаков, N = 762, на символ 10 бит. Номер не больше 500 · 1024 / 3000 = 170,67 → 170 байтов = 1360 бит, 10 · K ≤ 1360, K = 136.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i per = 500 * 1024 // 3000print(per * 8 // bits(10 + 52 + 700))Ответ: 136
Наибольшая мощность алфавита
Длина пароля — 15 символов. Для 40 паролей выделено не более 480 байтов, каждому паролю — минимальное целое число байтов. Найди наибольшую мощность алфавита.
Введите число.
Подсказка
Найди наибольшее число битов на символ — ответ 2ⁱ.
Решение
Пароль не больше 480 / 40 = 12 байтов = 96 бит. 15 · i ≤ 96, i ≤ 6,4, то есть i = 6. Наибольший алфавит для 6 бит — 2⁶ = 64.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i ok = [a for a in range(2, 1000) if ceil(15 * bits(a) / 8) <= 480 // 40]print(max(ok))Ответ: 64
Специальные символы
Код из 24 символов может содержать заглавные латинские буквы, десятичные цифры и символы специального набора. Каждому коду — одинаковое минимальное целое число байтов, кодирование посимвольное. Для 1000 кодов выделено не более 30 Кбайт. Какое наибольшее количество символов может быть в специальном наборе?
Введите число.
Подсказка
Сначала наибольший весь алфавит, потом вычти известные символы.
Решение
Код не больше 30 · 1024 / 1000 = 30,72 → 30 байтов = 240 бит, 24 · i ≤ 240, i = 10. Наибольший алфавит 2¹⁰ = 1024, из них 26 букв и 10 цифр известны: специальных знаков 1024 − 36 = 988.
Решение программой
most = (30 * 1024 // 1000) * 8 // 24print(2 ** most - 36)Ответ: 988
Пользователи в 3 Мбайт
Пароль содержит 16 символов алфавита мощностью 40, на дополнительные сведения выделено 19 байтов на пользователя, паролю — минимальное целое число байтов. О каком наибольшем количестве пользователей можно хранить сведения в 3 Мбайт?
Введите число.
Подсказка
Целая часть деления памяти на размер записи.
Решение
40 символам нужно 6 бит, пароль 16 · 6 = 96 бит = 12 байтов, запись 12 + 19 = 31 байт. 3 Мбайт = 3 · 2²⁰ байтов, 3 · 2²⁰ / 31 = 101 475,09… — целых записей 101 475.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i record = ceil(16 * bits(40) / 8) + 19print(3 * 2 ** 20 // record)Ответ: 101475
Мощность алфавита серийного номера
На предприятии каждой детали присваивают серийный номер из 310 символов. Каждому номеру отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Для хранения 700 000 номеров отведено не более 200 Мбайт. Определи максимально возможную мощность алфавита.
Введите число.
Подсказка
Байты на номер — целая часть, затем биты на символ.
Решение
Номер не больше 200 · 2²⁰ / 700 000 = 299,59… → 299 байтов = 2392 бита. 310 · i ≤ 2392, i ≤ 7,7, i = 7. Наибольший алфавит 2⁷ = 128.
Решение программой
most = 200 * 2 ** 20 // 700_000 * 8 // 310print(2 ** most)Ответ: 128