Расшифровки с буквой: как решать — ОГЭ по информатике

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

Буквы А, Б, В и Г закодированы двоичным кодом: А — 01, Б — 0, В — 1, Г — 00. Получена цепочка 010000. Сколько… Расшифровки с буквой — ОГЭ по информатике, тема «Коды букв и кодовые слова». Ответ проверяется на странице, разбор — сразу.

Пример 1

Буквы А, Б, В и Г закодированы двоичным кодом: А — 01, Б — 0, В — 1, Г — 00. Получена цепочка 010000. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву Г?

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

Ответ: 8

Условие Фано не выполнено: код А (01) начинается с кода Б (0), код Г (00) начинается с кода Б (0). Поэтому цепочку 010000 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 01 · 0 · 0 · 0 · 0 — АББББ;

2) 01 · 0 · 0 · 00 — АББГ (есть Г);

3) 01 · 0 · 00 · 0 — АБГБ (есть Г);

4) 01 · 00 · 0 · 0 — АГББ (есть Г);

5) 01 · 00 · 00 — АГГ (есть Г);

6) 0 · 1 · 0 · 0 · 0 · 0 — БВББББ;

7) 0 · 1 · 0 · 0 · 00 — БВББГ (есть Г);

8) 0 · 1 · 0 · 00 · 0 — БВБГБ (есть Г);

9) 0 · 1 · 00 · 0 · 0 — БВГББ (есть Г);

10) 0 · 1 · 00 · 00 — БВГГ (есть Г).

Буква Г есть в 8 сообщениях из 10: АББГ, АБГБ, АГББ, АГГ, БВББГ, БВБГБ, БВГББ, БВГГ.

Проверка: всего 10 сообщений, без буквы Г — 2; 10 − 2 = 8. Ответ 10 получился бы, если забыть про букву Г, а 2 — если сосчитать сообщения без неё.

Ответ: 8.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-1kv4c98

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

В стандартном JSON нет отдельного синтаксиса комментариев. Формат задаёт числа, строки, логические значения, null, массивы и объекты. Поэтому файл с привычными программисту пояснениями через две косые черты может оказаться допустимым в расширении формата, но не в самом JSON.

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

Буквы А, Б, В, Г и Д закодированы двоичным кодом: А — 11, Б — 110, В — 000, Г — 01, Д — 1. Получена цепочка 1101111110. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву А?

Решение

Ответ: 9

Условие Фано не выполнено: код Б (110) начинается с кода А (11), код А (11) начинается с кода Д (1), код Б (110) начинается с кода Д (1). Поэтому цепочку 1101111110 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 11 · 01 · 11 · 1 · 110 — АГАДБ (есть А);

2) 11 · 01 · 1 · 11 · 110 — АГДАБ (есть А);

3) 11 · 01 · 1 · 1 · 1 · 110 — АГДДДБ (есть А);

4) 110 · 11 · 11 · 110 — БААБ (есть А);

5) 110 · 11 · 1 · 1 · 110 — БАДДБ (есть А);

6) 110 · 1 · 11 · 1 · 110 — БДАДБ (есть А);

7) 110 · 1 · 1 · 11 · 110 — БДДАБ (есть А);

8) 110 · 1 · 1 · 1 · 1 · 110 — БДДДДБ;

9) 1 · 1 · 01 · 11 · 1 · 110 — ДДГАДБ (есть А);

10) 1 · 1 · 01 · 1 · 11 · 110 — ДДГДАБ (есть А);

11) 1 · 1 · 01 · 1 · 1 · 1 · 110 — ДДГДДДБ.

Буква А есть в 9 сообщениях из 11: АГАДБ, АГДАБ, АГДДДБ, БААБ, БАДДБ, БДАДБ, БДДАБ, ДДГАДБ, ДДГДАБ.

Проверка: всего 11 сообщений, без буквы А — 2; 11 − 2 = 9. Ответ 11 получился бы, если забыть про букву А, а 2 — если сосчитать сообщения без неё.

Ответ: 9.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-ujw460

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

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

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

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

Буквы А, Б, В, Г и Д закодированы двоичным кодом: А — 100, Б — 01, В — 000, Г — 0, Д — 1. Получена цепочка 0000101. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву Д?

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

Ответ: 8

Условие Фано не выполнено: код Б (01) начинается с кода Г (0), код В (000) начинается с кода Г (0), код А (100) начинается с кода Д (1). Поэтому цепочку 0000101 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 000 · 01 · 01 — ВББ;

2) 000 · 01 · 0 · 1 — ВБГД (есть Д);

3) 000 · 0 · 1 · 01 — ВГДБ (есть Д);

4) 000 · 0 · 1 · 0 · 1 — ВГДГД (есть Д);

5) 0 · 000 · 1 · 01 — ГВДБ (есть Д);

6) 0 · 000 · 1 · 0 · 1 — ГВДГД (есть Д);

7) 0 · 0 · 0 · 01 · 01 — ГГГББ;

8) 0 · 0 · 0 · 01 · 0 · 1 — ГГГБГД (есть Д);

9) 0 · 0 · 0 · 0 · 1 · 01 — ГГГГДБ (есть Д);

10) 0 · 0 · 0 · 0 · 1 · 0 · 1 — ГГГГДГД (есть Д).

Буква Д есть в 8 сообщениях из 10: ВБГД, ВГДБ, ВГДГД, ГВДБ, ГВДГД, ГГГБГД, ГГГГДБ, ГГГГДГД.

Проверка: всего 10 сообщений, без буквы Д — 2; 10 − 2 = 8. Ответ 10 получился бы, если забыть про букву Д, а 2 — если сосчитать сообщения без неё.

Ответ: 8.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-1r5vjpd

Пример 3

Буквы А, Б, В, Г и Д закодированы двоичным кодом: А — 001, Б — 10, В — 111, Г — 01, Д — 1. Получена цепочка 0110111111. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву В?

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

Ответ: 8

Условие Фано не выполнено: код Б (10) начинается с кода Д (1), код В (111) начинается с кода Д (1). Поэтому цепочку 0110111111 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 01 · 10 · 111 · 111 — ГБВВ (есть В);

2) 01 · 10 · 111 · 1 · 1 · 1 — ГБВДДД (есть В);

3) 01 · 10 · 1 · 111 · 1 · 1 — ГБДВДД (есть В);

4) 01 · 10 · 1 · 1 · 111 · 1 — ГБДДВД (есть В);

5) 01 · 10 · 1 · 1 · 1 · 111 — ГБДДДВ (есть В);

6) 01 · 10 · 1 · 1 · 1 · 1 · 1 · 1 — ГБДДДДДД;

7) 01 · 1 · 01 · 111 · 1 · 1 — ГДГВДД (есть В);

8) 01 · 1 · 01 · 1 · 111 · 1 — ГДГДВД (есть В);

9) 01 · 1 · 01 · 1 · 1 · 111 — ГДГДДВ (есть В);

10) 01 · 1 · 01 · 1 · 1 · 1 · 1 · 1 — ГДГДДДДД.

Буква В есть в 8 сообщениях из 10: ГБВВ, ГБВДДД, ГБДВДД, ГБДДВД, ГБДДДВ, ГДГВДД, ГДГДВД, ГДГДДВ.

Проверка: всего 10 сообщений, без буквы В — 2; 10 − 2 = 8. Ответ 10 получился бы, если забыть про букву В, а 2 — если сосчитать сообщения без неё.

Ответ: 8.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-1gm3nt

Пример 4

Буквы А, Б, В и Г закодированы двоичным кодом: А — 11, Б — 10, В — 1, Г — 01. Получена цепочка 011101111. Сколько существует различных сообщений из этих букв, которые кодируются этой цепочкой и содержат хотя бы одну букву Б?

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

Ответ: 5

Условие Фано не выполнено: код А (11) начинается с кода В (1), код Б (10) начинается с кода В (1). Поэтому цепочку 011101111 можно разрезать на коды букв по-разному.
Переберём все способы слева направо, как ветви дерева вариантов:

1) 01 · 11 · 01 · 11 · 1 — ГАГАВ;

2) 01 · 11 · 01 · 1 · 11 — ГАГВА;

3) 01 · 11 · 01 · 1 · 1 · 1 — ГАГВВВ;

4) 01 · 1 · 10 · 11 · 11 — ГВБАА (есть Б);

5) 01 · 1 · 10 · 11 · 1 · 1 — ГВБАВВ (есть Б);

6) 01 · 1 · 10 · 1 · 11 · 1 — ГВБВАВ (есть Б);

7) 01 · 1 · 10 · 1 · 1 · 11 — ГВБВВА (есть Б);

8) 01 · 1 · 10 · 1 · 1 · 1 · 1 — ГВБВВВВ (есть Б);

9) 01 · 1 · 1 · 01 · 11 · 1 — ГВВГАВ;

10) 01 · 1 · 1 · 01 · 1 · 11 — ГВВГВА;

11) 01 · 1 · 1 · 01 · 1 · 1 · 1 — ГВВГВВВ.

Буква Б есть в 5 сообщениях из 11: ГВБАА, ГВБАВВ, ГВБВАВ, ГВБВВА, ГВБВВВВ.

Проверка: всего 11 сообщений, без буквы Б — 6; 11 − 6 = 5. Ответ 11 получился бы, если забыть про букву Б, а 6 — если сосчитать сообщения без неё.

Ответ: 5.

Нашли ошибку? Напишите нам, код задания: oge-informatics-rasshifrovki-s-bukvoy-3z8xlz

Рядом

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

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

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

Родителю

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