9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. 48Обработка информации § 411. Для передачи закодированных сообщений используется таблица кодовых слов из четырех букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трех одинаковых букв, идущих подряд?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 включительно. Сколько дверей ему пришлось открыть?Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?

Question 1

Задача Задача №3765868

А

Аноним

5 дней назад · публичный вопрос

А

Аноним 5 дней назад

9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. 48Обработка информации § 411. Для передачи закодированных сообщений используется таблица кодовых слов из четырех букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трех одинаковых букв, идущих подряд?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 включительно. Сколько дверей ему пришлось открыть?Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?

Answer

Кратко

\(Д = 1111\).
Да, можно: только для буквы Б, заменив код \(11\) на \(1\).
\(66\) различных кодовых слов.
\(590\) стоит на 15-м месте. При выборе левого среднего поиск идёт так: \(345 \to 478 \to 567 \to 590\).
Плотник открыл 5 дверей; использован двоичный поиск — метод половинного деления.

Разбор

9. Код для буквы Д

Уже есть коды:

Б — 0
В — 10
Г — 110
А — 1110

Удобно строить кодовое дерево. Все занятые коды находятся на ветвях:

После кода 1110 ближайшее свободное продолжение — 1111. Оно не является началом другого кода, и другие коды не являются его началом.

Почему нельзя короче? Например, если взять 111, то:

1110 = А
1110 = Д + Б = 111 + 0

Получается два разных прочтения. Аналогично более короткие варианты конфликтуют с уже имеющимися кодами.

Ответ: \(Д = 1111\).

10. Можно ли сократить троичный код

Исходный код:

А — 0
Б — 11
В — 20
Г — 21
Д — 22

Можно заменить:

Б: 11 → 1

Получим код:

А — 0
Б — 1
В — 20
Г — 21
Д — 22

Теперь ни одно кодовое слово не является началом другого, значит декодирование остаётся однозначным.

Другие сокращения не подходят. Например:

если дать какой-то букве код 1, кроме Б, то 11 можно будет прочитать как Б или как две такие буквы;
если дать код 2, то 2 станет началом слов 20, 21, 22, и возникнет неоднозначность. Например, при В = 2 слово 22 читается и как Д, и как ВВ.

Ответ: да, можно: только \(Б: 11 \to 1\).

11. Число кодовых слов длины 4

Каждое слово состоит из 4 букв, алфавит: А, Р, У — всего 3 буквы.

Всего слов:

\[ 3^4 = 81 \]

Теперь вычтем «плохие» слова, где есть три одинаковые буквы подряд.

Такие три буквы могут стоять:

на местах 1–3: \(3 \cdot 3 = 9\) слов;
на местах 2–4: \(3 \cdot 3 = 9\) слов.

Но слова из четырёх одинаковых букв посчитаны дважды: таких слов \(3\).

Значит, плохих слов:

\[ 9 + 9 - 3 = 15 \]

Хороших слов:

\[ 81 - 15 = 66 \]

Ответ: \(66\).

12. Поиск числа 590 методом половинного деления

Пронумеруем элементы:

1   2   3    4    5    6    7    8
061 087 154 180 208 230 290 345

9    10   11   12   13   14   15   16
367  389  456  478  523  567  590  612

Будем брать средний элемент, округляя номер вниз.

Весь массив, середина — №8, число \(345\).
\(590 > 345\), значит ищем в правой части: №9–16.
Середина №12 — \(478\).
\(590 > 478\), остаётся №13–16.
Середина №14 — \(567\).
\(590 > 567\), остаётся №15–16.
Середина №15 — \(590\).
Число найдено.

Ответ: \(590\) найдено за 4 проверки:
\[ 345 \to 478 \to 567 \to 590. \]

Если при чётном числе элементов брать правую середину, шаги будут:
\[ 367 \to 523 \to 590, \] но принцип остаётся тем же — каждый раз отбрасывается примерно половина оставшихся чисел.

13. Задача «Склад»

Известно, что заполнены склады №1–15, а №16 пуст.

Плотник действует так:

Открывает №16 — пусто.
Значит, первый незаполненный склад находится среди №1–15.
Открывает №8 — заполнен.
Значит, искать нужно в №9–15.
Открывает №12 — заполнен.
Остаётся №13–15.
Открывает №14 — заполнен.
Остаётся №15.
Открывает №15 — заполнен.
Значит, все склады до №15 заполнены, а первый незаполненный — №16.

Всего открытий:

\[ 16,\ 8,\ 12,\ 14,\ 15 = 5 \]

Ответ: 5 дверей.
Использован метод половинного деления, или двоичный поиск.

Question 2

9. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. При этом используются следующие коды: А — 1110, Б — 0, В — 10, Г — 110. Каким кодовым словом может быть закодирована буква Д? Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.10. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный троичный код, позволяющий однозначно декодировать полученную троичную последовательность. Вот этот код: А — 0, Б — 11, В — 20, Г — 21, Д — 22. Можно ли сократить для одной из букв длину кодового слова так, чтобы закодированную последовательность по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. 48Обработка информации § 411. Для передачи закодированных сообщений используется таблица кодовых слов из четырех букв. Причем используются только буквы А, Р и У. Сколько различных кодовых слов может быть в такой таблице, если ни в одном слове нет трех одинаковых букв, идущих подряд?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 включительно. Сколько дверей ему пришлось открыть?Решите эту задачу. Какой из рассмотренных нами методов поиска был использован героем этой задачи?

Answer

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