Какой вопрос разделит неизвестность?
Выбирать различающий вопрос · Строить дерево да/нет
В этом занятии
- Выбирать различающий вопрос
- Строить дерево да/нет
- Доказывать нижнюю границу числа вопросов
Пригодится: Рекомендуем сначала пройти «Одно решение, много решений, ни одного».
Разберёмся перед практикой+
Какой вопрос разделит неизвестность?
Полезный вопрос делит оставшиеся возможности по разным ответам. Если четыре возможных файла лежат в папках, вопрос «файл существует?» ничего не различает: во всех случаях ответ да. Вопрос о папке может отсечь часть кандидатов и направить следующий шаг проверки.
Для гарантии быстрого поиска важен худший ответ, а не самый приятный. Вопрос, который делит восемь равновозможных кандидатов на группы 4 и 4, оставляет не более четырёх. Разделение 1 и 7 может сразу угадать один файл, но при другом ответе оставляет семь вариантов.
Дерево из k последовательных вопросов с двумя ответами имеет не более 2 в степени k листьев. Чтобы различить восемь кандидатов при любом исходе, нужно хотя бы три вопроса. Эта граница предполагает честные точные ответы и действительно два исхода каждого вопроса.
Количество вариантов и их вероятности — разные сведения. Ровное деление количества удобно для худшего случая; если варианты сильно неравновероятны, среднее число вопросов может улучшаться иначе. Сначала выберите цель: гарантия, среднее усилие или цена конкретной проверки.
Среди восьми карточек спрятана одна. Можно спрашивать, принадлежит ли она выбранной группе. Как гарантированно найти её за три вопроса?
- Делим восемь карточек на две группы по четыре.
- По ответу делим оставшиеся четыре на две пары, затем пару на отдельные карточки.
- Три ответа задают одну из восьми ветвей; меньше трёх двоичных ответов недостаточно.
Попробуйте самостоятельно
Запишите рассуждения в черновик или сделайте построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Построй дерево для шести карточек и подпиши максимальную глубину.
- Придумай вопрос, который звучит содержательно, но одинаково отвечает для всех кандидатов.
Читайте и разбирайте пример в своём темпе. К практике можно перейти, когда будете готовы.