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

Задача

Правила игры «Угадай букву» очень похожи на правила игры «Угадай число». В игре «Угадай букву» Водящий загадывает букву русского алфавита. Определи, за сколько вопросов можно наверняка отгадать букву в игре «Угадай букву». Чтобы ответить на вопрос, построй дерево сортировки «Половинным разделителем». Пользуясь построенным деревом, сыграй с соседом две партии в игру «Угадай букву» и проверь свои ответы. Дерево построй способом из предыдущего, 214 номера. У тебя получится на строчку больше.

Подробный ответ

В русском алфавите 33 буквы. Если каждый раз делить оставшиеся буквы на две примерно равные части, то за один вопрос можно сузить выбор в 2 раза.

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

$$2^5 = 32 < 33,$$

$$2^6 = 64 \ge 33.$$

Значит, пяти вопросов недостаточно, а шести вопросов уже хватает.

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