Подтема 4 из 6
Наименьшее значение: «более» и «не менее»
Как найти наименьшие длину и алфавит, когда памяти нужно «более» или «не менее» заданной.
Наименьшая запись
40 пользователям требуется более 1200 байт, сведения — 18 байт. Какой наименьший размер записи?
«Не менее» и «более» дают нижнюю границу одной записи — её округляют вверх до целых байт. «Более 1200»: 30 байт дают ровно 1200 — не больше, значит, запись хотя бы 31 байт. «Не менее 1200» допускает ровно 30 байт.
| Условие на 40 записей | Одна запись |
|---|---|
| не более 1200 байт | не больше 30 байт |
| менее 1200 байт | не больше 29 байт |
| не менее 1200 байт | не меньше 30 байт |
| более 1200 байт | не меньше 31 байта |
На пароль при «более 1200» остаётся хотя бы 31 − 18 = 13 байт.
Наименьшая длина
Пароль должен занимать хотя бы 13 байт. Какой наименьшей длины он может быть?
Пароль занимает хотя бы 13 байт, если его код не помещается в 12 байт: 6 · K > 96. K > 16, наименьшая длина — 17. Заполнять все 13 байт код не обязан: 102 бита уже требуют 13 байт.
Проверь найденную длину и предыдущую. K = 16: 12 байт, всего 1200 — не больше 1200, не подходит. K = 17: 13 байт, 40 · 31 = 1240 — подходит. Запись 6 · K ≥ 104 дала бы K = 18 — ошибка: тринадцатый байт не обязан быть полным.
Перебор идёт от малых длин, первая подходящая — ответ; останавливает цикл:
from math import ceilfor k in range(1, 100): password = ceil(k * 6 / 8) if 40 * (password + 18) > 1200: print(k) breakУсловие — снова дословно: «более 1200» — это > 1200, «не менее» — >= 1200.
Наименьший алфавит
Длина пароля — 15, на 40 пользователей требуется более 1200 байт. Какова наименьшая мощность алфавита?
Сначала находят, сколько битов на символ понадобится, а потом — самый маленький алфавит, которому их нужно столько: N = 2ⁱ⁻¹ + 1. Пароль не помещается в 12 байт: 15 · i > 96, i > 6,4, i = 7. Шести битов хватает на 64 символа, седьмой нужен с 65-го: N = 65.
Проверка соседа: N = 64 — 6 бит, 12 байт, всего 1200 — не больше 1200; N = 65 — 7 бит, 105 бит → 14 байт, всего 1280 — подходит. Наименьший специальный набор к 62 буквам и цифрам: 65 − 62 = 3 знака.
Цикл увеличивает i, пока объём ещё не больше 1200, — условие цикла обратно условию задачи. Запусти по шагам:
from math import ceil i = 1while 40 * (ceil(15 * i / 8) + 18) <= 1200: i += 1print(i, 2 ** (i - 1) + 1)Шесть или семь битов меняют объём скачком: 64 символа — 1200 байт, 65 — сразу 1280. Число битов растёт целыми шагами, а байты пароля ещё и округляются.
Тонкости:крупные числа
Серийный номер — из цифр, строчных латинских букв и 900 знаков, 150 000 номеров занимают более 20 Мбайт. Наименьшая длина номера — тот же перебор:
from math import ceili = bits(10 + 26 + 900)for k in range(1, 1000): if 150000 * ceil(k * i / 8) > 20 * 2 ** 20: print(i, k) breakИтого
- Не менеезапись — память / число, вверх
- Болееровно граница не подходит: + 1 байт
- Длинакод не помещается в байт меньше: K · i > …
- Алфавитнаименьшее i, ответ 2ⁱ⁻¹ + 1
- Проверкапредыдущее значение не подходит
- Pythonперебор от малых, первое подходящее, break
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Запись при «более»
40 одинаковых записей занимают целое число байтов каждая. Все записи вместе занимают более 1000 байтов. Какое наименьшее число байтов может занимать одна запись?
Введите число.
Подсказка
При «более» сама граница не подходит.
Решение
При 25 байтах 40 записей занимают ровно 1000 — это не «более 1000». Значит, запись хотя бы 26 байтов: 40 · 26 = 1040.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(r for r in range(1, 100) if 40 * r > 1000))Ответ: 26
Наименьший заголовок
Отправлено 3 сообщения по 40 символов и 5 сообщений по 25 символов алфавита из 100 символов. Каждое сообщение кодируется минимальным целым числом байтов, к каждому добавляется заголовок одинакового целого размера. Всего передано более 300 байтов. Какое наименьшее число байтов может содержать заголовок?
Введите число.
Подсказка
Заголовок добавляется к каждому из 8 сообщений.
Решение
100 символам нужно 7 бит. Сообщение из 40 символов — 280 бит = 35 байтов, из 25 — 175 бит → 22 байта. Без заголовков 3 · 35 + 5 · 22 = 215 байтов; 215 + 8 · h > 300, h > 10,6, наименьший заголовок 11 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i long = ceil(40 * bits(100) / 8)short = ceil(25 * bits(100) / 8)data = 3 * long + 5 * shortprint(min(h for h in range(100) if data + 8 * h > 300))Ответ: 11
Наименьшая длина при «более»
Алфавит содержит 17 символов. Каждый пароль занимает минимальное целое число байтов. 100 паролей требуют более 1000 байтов. Найди наименьшую длину пароля.
Введите число.
Подсказка
Код должен не помещаться в меньшее число байтов.
Решение
17 символам нужно 5 бит. «Более 1000» на 100 паролей — пароль хотя бы 11 байтов, то есть его код не помещается в 10 байтов: 5 · K > 80, K > 16. Наименьшая длина 17: 85 бит → 11 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(k for k in range(1, 60) if 100 * ceil(k * bits(17) / 8) > 1000))Ответ: 17
Более 450 байтов
Пароли используют алфавит из 30 символов, каждый пароль занимает минимальное целое число байтов. 50 паролей занимают более 450 байтов. Найди минимальную длину пароля.
Введите число.
Подсказка
Пароль хотя бы на байт больше, чем 450 / 50.
Решение
30 символам нужно 5 бит. При 9 байтах 50 паролей заняли бы ровно 450, поэтому пароль хотя бы 10 байтов: код не помещается в 9 байтов, 5 · K > 72, K > 14,4. Наименьшая длина 15.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(n for n in range(1, 60) if 50 * ceil(n * bits(30) / 8) > 450))Ответ: 15
Минимальная длина номера
Серийный номер содержит десятичные цифры, заглавные латинские буквы и символы из специального алфавита в 5000 символов. Каждому номеру отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Известно, что 200 000 номеров занимают более 30 Мбайт. Определи минимально возможную длину номера.
Введите число.
Подсказка
Алфавит — 10 + 26 + 5000 символов.
Решение
N = 10 + 26 + 5000 = 5036, на символ 13 бит. 30 · 2²⁰ / 200 000 = 157,29…, поэтому номер хотя бы 158 байтов: код не помещается в 157 байтов, 13 · K > 1256, K > 96,6. Наименьшая длина 97.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(n for n in range(1, 500) if 200_000 * ceil(n * bits(5036) / 8) > 30 * 2 ** 20))Ответ: 97
Минимальная мощность алфавита
Пароль содержит 13 символов. Для хранения 200 паролей требуется не менее 2001 байта. Каждый пароль занимает минимальное целое число байтов. Найди минимальную мощность алфавита.
Введите число.
Подсказка
Найди наименьшее число битов, затем наименьший алфавит для него.
Решение
2001 / 200 = 10,005, поэтому пароль хотя бы 11 байтов: код не помещается в 10 байтов, 13 · i > 80, i > 6,15, i = 7. Семь битов нужны начиная с 2⁶ + 1 = 65 символов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(a for a in range(2, 5000) if 200 * ceil(13 * bits(a) / 8) >= 2001))Ответ: 65
Наименьший специальный набор
Код из 20 символов использует заглавные латинские буквы, десятичные цифры и символы специального набора; каждому коду — минимальное целое число байтов, кодирование посимвольное. Для 400 кодов требуется не менее 6800 байтов. Какое наименьшее количество символов может быть в специальном наборе?
Введите число.
Подсказка
Сначала наименьший весь алфавит, затем вычти известные символы.
Решение
6800 / 400 = 17 байтов на код — код не помещается в 16 байтов: 20 · i > 128, i = 7. Наименьший алфавит для 7 бит — 65 символов, из них 26 букв и 10 цифр известны: специальных хотя бы 65 − 36 = 29.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(s for s in range(0, 5000) if 400 * ceil(20 * bits(36 + s) / 8) >= 6800))Ответ: 29
Минимальная мощность алфавита номера
Серийный номер состоит из 40 символов. Каждый номер занимает одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Для хранения 2 000 000 номеров требуется не менее 95 Мбайт. Определи минимально возможную мощность алфавита.
Введите число.
Подсказка
Наименьшее число битов, при котором номер не помещается в меньшее число байтов.
Решение
95 · 2²⁰ / 2 000 000 = 49,8…, поэтому номер хотя бы 50 байтов: код не помещается в 49 байтов, 40 · i > 392, i > 9,8, i = 10. Десять битов нужны начиная с 2⁹ + 1 = 513 символов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(a for a in range(2, 5000) if 2_000_000 * ceil(40 * bits(a) / 8) >= 95 * 2 ** 20))Ответ: 513