9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них. 10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. 11. Для передачи закодированных сообщений используется таблица кодовых слов из четырех букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трех одинаковых букв, идущих подряд? 12. Методом половинного деления в последовательности чисел 061 087 154 180 208 230 290 345 367 389 456 478 523 567 590 612 требуется найти число 590. Опишите процесс поиска. 13. В Международном конкурсе по информатике «Бобёр» школьникам была предложена задача «Склад», подготовленная специалистами из Японии. Вот её условие.Плотник в Бобровой Деревне использует 31 склад, пронумерованный от 1 до 31. Однажды он забыл, сколько складов уже заполнил, но помнит, что заполнял их в порядке возрастания номеров.Чтобы уменьшить количество открывания дверей, он действует следующим образом:Сначала открывает склад со средним номером — склад № 16.Затем:• если склад № 16 пуст, он решает искать первый незаполненный склад в промежутке от № 1 до № 15, открывает опять средний склад — склад № 8 — и повторяет процедуру;• если склад № 16 заполнен, то нужный склад он ищет между № 17 и № 31, открывает средний склад — склад № 24 — и повторяет процедуру.После всех действий плотник обнаружил, что заполнены были склады от № 1 до № 15 включительно. Сколько дверей ему пришлось открыть?Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?
\(1111\). Короче нельзя: \(0\), \(10\) уже заняты; \(11\) — префикс \(110\), \(110\) занято, \(111\) — префикс \(1110\).
Да: \(Б=1\) вместо \(11\). Код остаётся однозначно декодируемым.
\(3^4-(3\cdot3+3\cdot3-3)=81-15=66\).
\(345<590\) → берём \(9{-}16\);
\(478<590\) → берём \(13{-}16\);
\(567<590\) → берём \(15{-}16\);
\(590\) найден. Всего 4 сравнения.Открыты склады: \(16,\ 8,\ 12,\ 14,\ 15\).
Открыто \(5\) дверей. Использован метод половинного деления — бинарный поиск.
Обсуждение
2 сообщенияРеши все задачи
9.
Коды \(0\), \(10\), \(110\), \(1110\) уже заняты, причём \(1110\) — код буквы А.
Свободное кратчайшее слово, которое не будет началом другого кода и не даст неоднозначности:
\[
Д = 1111.
\]
Ответ: \(1111\).
10.
Да, можно, например для буквы Б:
\[
Б = 11 \to 1.
\]
Новый код:
\[
А=0,\quad Б=1,\quad В=20,\quad Г=21,\quad Д=22.
\]
Ни одно кодовое слово не является началом другого, значит, код остаётся однозначно декодируемым.
Ответ: да, например \(Б=1\).
11.
Всего слов длины 4 из трёх букв:
\[
3^4 = 81.
\]
Запрещены слова, где три одинаковые буквы идут подряд.
Для одной фиксированной буквы таких слов:
\[
3+3-1=5
\]
(три варианта с тройкой на местах 1–3, три — на местах 2–4, слово из четырёх одинаковых букв посчитано дважды).
Для трёх букв: \[ 5\cdot 3 = 15. \] Значит, подходящих слов: \[ 81-15=66. \]
Ответ: \(66\).
12.
Берём левую середину интервала.
Исходный интервал: \(1\)–\(16\).
- Середина — 8-й элемент: \(345\).
\(345<590\), ищем в \(9\)–\(16\). - Середина — 12-й элемент: \(478\).
\(478<590\), ищем в \(13\)–\(16\). - Середина — 14-й элемент: \(567\).
\(567<590\), ищем в \(15\)–\(16\). - Середина — 15-й элемент: \(590\).
Число найдено.
Проверены числа: \[ 345,\quad 478,\quad 567,\quad 590. \]
Ответ: \(590\) найден за 4 сравнения.
13.
Ищем первый незаполненный склад.
- Открываем №16 — пуст, значит, заполнены склады до 15, ищем в \(1\)–\(15\).
- Открываем №8 — заполнен, ищем в \(9\)–\(15\).
- Открываем №12 — заполнен, ищем в \(13\)–\(15\).
- Открываем №14 — заполнен, остаётся проверить №15.
- Открываем №15 — заполнен. Следующий, №16, уже известен как пустой.
Открыты двери складов: \[ 16,\ 8,\ 12,\ 14,\ 15. \] Всего открыто \(5\) дверей.
Ответ: 5 дверей; использован метод половинного деления, то есть двоичный поиск.
