Число слов из алфавита: как решать — ОГЭ по информатике

ОГЭ Информатика сложность в тренажёре: базовая

Алфавит содержит 5 букв. Сколько различных слов длины 5 можно составить, если буквы могут повторяться? Число слов из алфавита — ОГЭ по информатике, тема «Коды букв и кодовые слова». Ответ проверяется на странице, разбор — сразу.

Пример 1

Алфавит содержит 5 букв. Сколько различных слов длины 5 можно составить, если буквы могут повторяться?

Ответ и разбор

Ответ: 3125

Каждую из 5 позиций можно заполнить 5 способами.
Всего: 5⁵ = 3125.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-nhl2zf

Ещё задания этого вида — ниже. Открыть тренажёр

Первый прототип мыши по замыслу Дугласа Энгельбарта собрал инженер Билл Инглиш в 1964 году. Устройство имело деревянный корпус и одну кнопку. В 1968 году Энгельбарт показал работу мыши в составе системы NLS на знаменитой публичной демонстрации.

Разобранный пример

Алфавит содержит 4 буквы. Сколько различных слов длины 4 можно составить, если буквы могут повторяться?

Решение

Ответ: 256

Каждую из 4 позиций можно заполнить 4 способами.
Всего: 4⁴ = 256.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-rq3kj5

Формулы и приём

Префиксный код: чтение и сокращение

Как декодировать префиксный код и проверить сокращение кодового слова?

p — не начало q

p
непустое двоичное кодовое слово одного символа, последовательность битов
q
любое другое кодовое слово; коды всех символов различны, последовательность битов

Условие Фано здесь означает: ни одно кодовое слово не является началом другого. Такой код можно читать слева направо: как только набран код символа, записывай символ и начинай следующий.
Пример: А = 0, Б = 11, В = 101, Г = 1000, Д = 1001. Это полный список кодов. Декодируем строку 10010101111000: 1001 / 0 / 101 / 11 / 1000 → Д / А / В / Б / Г.
Ответ: ДАВБГ; все биты использованы.
Можно ли сделать код Г короче, сохранив остальные коды и условие Фано? Однобитный 0 уже занят; 1 был бы началом кодов Б, В и Д. Из двухбитных 00 и 01 начинаются с кода А; 10 является началом кодов В = 101 и Д = 1001; 11 занят кодом Б. Из трёхбитных слова на 0 начинаются с кода А, 110 и 111 — с кода Б; 100 является началом кода Д = 1001; 101 занят кодом В. Подходящего слова длины 1, 2 или 3 нет. Значит, нынешняя длина кода Г — 4 бита — минимальна при неизменных кодах А, Б, В и Д.

Ловушка: проверять нужно оба направления — новый код не должен быть началом старого, а старый началом нового. Неполный остаток битов нельзя молча отбросить. Префиксность достаточна, но не необходима для однозначного декодирования вообще; вывод о минимуме здесь относится именно к условию Фано и фиксированным остальным кодам.

Ещё примеры

Пример 2

Алфавит содержит 9 букв. Сколько различных шифров длины 3 можно составить, если буквы могут повторяться?

Ответ и разбор

Ответ: 729

Каждую из 3 позиций можно заполнить 9 способами.
Всего: 9³ = 729.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-j4sj3x

Пример 3

Алфавит содержит 8 букв. Сколько различных кодов длины 5 можно составить, если буквы могут повторяться?

Ответ и разбор

Ответ: 32768

Каждую из 5 позиций можно заполнить 8 способами.
Всего: 8⁵ = 32768.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-no714

Пример 4

Алфавит содержит 4 буквы. Сколько различных паролей длины 2 можно составить, если буквы могут повторяться?

Ответ и разбор

Ответ: 16

Каждую из 2 позиций можно заполнить 4 способами.
Всего: 4² = 16.

Нашли ошибку? Напишите нам, код задания: oge-informatics-word-count-qmbgr7

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.