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

Информатика · 10 класс Задача №3765873

А

Аноним

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

А

Аноним 4 дня назад

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 находится за 4 сравнения: 345 → 478 → 567 → 590.
Плотник открыл 5 дверей; использован двоичный поиск, он же метод половинного деления.

9. Почему для Д подходит 1111

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

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

Чтобы декодирование оставалось однозначным, удобно строить префиксный код: ни одно кодовое слово не должно быть началом другого.

Проверяем короткие варианты для Д:

1 нельзя: это начало кодов 10, 110, 1110;
11 нельзя: это начало 110 и 1110;
111 нельзя: это начало 1110;
варианты, начинающиеся с 0, нельзя, потому что код Б = 0 уже является началом.

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

Ответ: 1111.

10. Можно ли сократить одно кодовое слово

Дан троичный код:

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

Можно заметить, что код буквы Б можно сократить:

\[ 11 \rightarrow 1 \]

Новый набор:

\[ 0,\ 1,\ 20,\ 21,\ 22 \]

Ни одно из этих слов не является началом другого, значит последовательность по-прежнему декодируется однозначно.

Ответ: да, например Б — 1.

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

Используются 3 буквы: А, Р, У. Всего слов длины 4:

\[ 3^4 = 81 \]

Запрещены слова, где три одинаковые буквы идут подряд.

Слова, где первые три буквы одинаковы: \(3 \cdot 3 = 9\).
Слова, где последние три буквы одинаковы: тоже \(9\).
Пересечение — слова из четырёх одинаковых букв: \(3\).

По формуле включений-исключений:

\[ 81 - 9 - 9 + 3 = 66 \]

Ответ: 66.

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

Дана упорядоченная последовательность из 16 чисел. Ищем 590.

Будем выбирать нижнюю середину:

Шаг	Интервал	Средний элемент	Вывод
1	1–16	8-й элемент: 345	\(590>345\), ищем справа: 9–16
2	9–16	12-й элемент: 478	\(590>478\), ищем справа: 13–16
3	13–16	14-й элемент: 567	\(590>567\), ищем справа: 15–16
4	15–16	15-й элемент: 590	число найдено

Ответ: 590 найден за 4 шага.

13. Склады

Заполнены склады с №1 по №15, начиная с №16 пусто.

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

Открыт склад	Что выяснилось	Новый промежуток поиска
№16	пуст	первый пустой склад где-то среди №1–15
№8	заполнен	ищем №9–15
№12	заполнен	ищем №13–15
№14	заполнен	остаётся проверить №15
№15	заполнен	значит, первый пустой — №16

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

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

То есть 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 находится за 4 сравнения: **345 → 478 → 567 → 590**. 13. Плотник открыл **5 дверей**; использован **двоичный поиск**, он же **метод половинного деления**. --- ### 9. Почему для Д подходит 1111 Исходные коды: - А — 1110 - Б — 0 - В — 10 - Г — 110 Чтобы декодирование оставалось однозначным, удобно строить **префиксный код**: ни одно кодовое слово не должно быть началом другого. Проверяем короткие варианты для Д: - 1 нельзя: это начало кодов 10, 110, 1110; - 11 нельзя: это начало 110 и 1110; - 111 нельзя: это начало 1110; - варианты, начинающиеся с 0, нельзя, потому что код Б = 0 уже является началом. Первое свободное слово — **1111**. Оно не является началом других кодов, и другие коды не являются его началом. **Ответ: 1111.** --- ### 10. Можно ли сократить одно кодовое слово Дан троичный код: - А — 0 - Б — 11 - В — 20 - Г — 21 - Д — 22 Можно заметить, что код буквы **Б** можно сократить: \[ 11 \rightarrow 1 \] Новый набор: \[ 0,\ 1,\ 20,\ 21,\ 22 \] Ни одно из этих слов не является началом другого, значит последовательность по-прежнему декодируется однозначно. **Ответ: да, например Б — 1.** --- ### 11. Сколько кодовых слов длины 4 Используются 3 буквы: А, Р, У. Всего слов длины 4: \[ 3^4 = 81 \] Запрещены слова, где три одинаковые буквы идут подряд. Слова, где первые три буквы одинаковы: \(3 \cdot 3 = 9\). Слова, где последние три буквы одинаковы: тоже \(9\). Пересечение — слова из четырёх одинаковых букв: \(3\). По формуле включений-исключений: \[ 81 - 9 - 9 + 3 = 66 \] **Ответ: 66.** --- ### 12. Поиск числа 590 методом половинного деления Дана упорядоченная последовательность из 16 чисел. Ищем 590. Будем выбирать нижнюю середину: | Шаг | Интервал | Средний элемент | Вывод | |---|---|---|---| | 1 | 1–16 | 8-й элемент: 345 | \(590>345\), ищем справа: 9–16 | | 2 | 9–16 | 12-й элемент: 478 | \(590>478\), ищем справа: 13–16 | | 3 | 13–16 | 14-й элемент: 567 | \(590>567\), ищем справа: 15–16 | | 4 | 15–16 | 15-й элемент: 590 | число найдено | **Ответ: 590 найден за 4 шага.** --- ### 13. Склады Заполнены склады с №1 по №15, начиная с №16 пусто. Плотник действует так: | Открыт склад | Что выяснилось | Новый промежуток поиска | |---|---|---| | №16 | пуст | первый пустой склад где-то среди №1–15 | | №8 | заполнен | ищем №9–15 | | №12 | заполнен | ищем №13–15 | | №14 | заполнен | остаётся проверить №15 | | №15 | заполнен | значит, первый пустой — №16 | Всего открыто: \[ 16,\ 8,\ 12,\ 14,\ 15 \] То есть **5 дверей**. Такой способ — деление области поиска пополам — называется **двоичным поиском** или **методом половинного деления**.