Число кодовых слов
Сколько разных паролей из 4 цифр можно составить?
N = mk
- N
- количество различных слов, штук
- m
- размер алфавита (сколько символов доступно), штук
- k
- длина слова, символов
На каждую позицию — m вариантов, позиций k. Для четырёхзначного PIN это 10⁴ = 10 000 комбинаций: перебрать их вручную нереально, а компьютером — мгновенно.
Формула считает варианты С ПОВТОРЕНИЯМИ: «1111» тоже пароль.
Условие Фано
Как код читается однозначно, если между буквами нет разделителей?
ни одно кодовое слово — не начало другого → сообщение декодируется однозначно
Если ни одно кодовое слово не совпадает с началом другого, сообщение читается слева направо без запятых единственным способом. Код {0, 10, 110, 111} условие выполняет: строка 0110111 разбирается только как 0|110|111. В задании 4 из подходящих вариантов выбирай самое короткое слово, которое не нарушает условие для всего набора.
Достаточно любого из двух условий: прямого Фано (не начало другого) или обратного (не окончание другого) — второе означает однозначное чтение справа налево. Проверять оба сразу не требуется.