Задание 213 ГДЗ Семенов Рудченко 6 класс (Информатика)

213. Используя метод половинного деления, построй дерево из вопросов в игре «Угадай число» от 1 до 16. Построй дерево бинарной сортировки половинным разделителем множества чисел от 1 до 16, соответствующее дереву из вопросов.

При методе половинного деления каждый вопрос делит множество возможных чисел примерно пополам. Для чисел от $$1$$ до $$16$$ достаточно $$4$$ вопросов, потому что

$$2^4 = 16.$$

Поэтому дерево вопросов строится так:

• 1-й вопрос: число больше 8?
• 2-й вопрос: в каждой половине снова делим пополам: больше 4?, больше 12?
• 3-й вопрос: далее получаем группы по 2 числа: больше 2?, больше 6?, больше 10?, больше 14?
• 4-й вопрос: остаётся выбрать одно число из пары.

Соответствующее дерево сортировки половинным разделителем повторяет те же деления множества чисел на половины:

• $$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$$
• $$1,2,3,4,5,6,7,8$$ и $$9,10,11,12,13,14,15,16$$
• $$1,2,3,4$$, $$5,6,7,8$$, $$9,10,11,12$$, $$13,14,15,16$$
• $$1,2$$, $$3,4$$, $$5,6$$, $$7,8$$, $$9,10$$, $$11,12$$, $$13,14$$, $$15,16$$
• отдельные числа $$1,2,3,\dots,16$$.

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

Ответ

Дерево Ш строится последовательным делением множества чисел пополам: $$8$$, затем $$4$$, затем $$2$$, затем $$1$$. Дерево Б имеет те же уровни деления. Отгадать число от $$1$$ до $$16$$ можно за $$4$$ вопроса.