Вопрос о минимальном количестве «да‑нет» вопросов, один из классических задач из теории информации и комбинаторики. Он часто встречается в школьных олимпиадах, в играх «угадай число» и в задачах по информатике. В этой статье разберём, как вычислять ответ для разных диапазонов чисел, почему именно такая формула работает, и как её применять на практике.
Основная идея: логарифм по основанию 2
Каждый «да‑нет» вопрос разбивает множество возможных ответов на две части. Если у нас есть N возможных чисел, после одного вопроса остаётся максимум ⌊N/2⌋ вариантов. Чтобы сузить диапазон до одного числа, нужно повторять этот процесс, пока количество возможных вариантов не станет 1.
Именно это приводит к формуле:
Минимальное количество вопросов = ⌈log₂ N⌉
где ⌈x⌉ – надграничение (ceil), т.е. ближайшее целое число, не меньшее x, а log₂ N – двоичный логарифм.
Почему именно? Каждый вопрос даёт ровно одну битовую информацию (0 / 1). Для того чтобы однозначно определить число из N вариантов, требуется по крайней мере log₂ N бит. Поскольку вопросы «да‑нет» дают целые биты, мы округляем вверх.
Пример 1: числа от 0 до 15
- Всего вариантов N = 16.
- log₂ 16 = 4.
- Ответ: 4 вопроса.
Это можно проверить: каждый вопрос делит диапазон пополам (0‑7 и 8‑15, затем 0‑3/4‑7 и 8‑11/12‑15 и т.д.). Четвёртый вопрос уже определяет конкретное число.
Пример 2: числа от 0 до 127
- N = 128.
- log₂ 128 = 7.
- Ответ: 7 вопросов.
Пример 3: числа от 1 до 1000
- N = 1000.
- log₂ 1000 ≈ 9,97.
- ⌈9,97⌉ = 10.
- Ответ: 10 вопросов.
Запросив 10 вопросов, можно сузить диапазон до одного числа даже в диапазоне 1‑1000.
Как строить вопросы? – Метод двоичного поиска
Самый простой способ задать «да‑нет» вопросы — использовать двоичный поиск. Вопросы всегда сравнивают загаданное число с некоторым порогом:
«Число больше ли чем X?»
В зависимости от ответа вы ограничиваете диапазон:
- ДА – число находится в диапазоне (X+1 … правый предел).
- НЕТ – число в диапазоне (левый предел … X).
Таким образом, каждый вопрос делит текущее множество ровно пополам (или почти пополам, если нечётное). Повторяя процесс, вы быстро добиваетесь одного числа.
Пошаговый пример: угадываем число от 1 до 1000
- Вопрос 1: «Число > 500?».
• Если «ДА», диапазон 501‑1000.
• Если «НЕТ», диапазон 1‑500. - Вопрос 2: «Число > 750?» (если диапазон 501‑1000)
или «Число > 250?» (если диапазон 1‑500), и т.д. - …
- Вопрос 10: последний порог будет определять конкретное число.
Таким образом, 10 вопросов точно хватает.
Точное счётчение вопросов для любой суммы N
Ниже таблица с результатами для различных диапазонов:
| N | log₂ N | ⌈log₂ N⌉ |
|---|---|---|
| 2 | 1 | 1 |
| 3 | 1,585 | 2 |
| 4 | 2 | 2 |
| 5–8 | 2,32–3 | 3 |
| 9–16 | 3,17–4 | 4 |
| 17–32 | 4,09–5 | 5 |
| 33–64 | 5,04–6 | 6 |
| 65–128 | 6,02–7 | 7 |
| 129–256 | 7,02–8 | 8 |
| 257–512 | 8,02–9 | 9 |
| 513–1024 | 9,02–10 | 10 |
Эта таблица показывает, что при каждом удвоении диапазона требуется ровно на один вопрос больше.
Почему иногда кажется, что нужно больше вопросов
В тексте задачи иногда встречается фраза «половина ответов правильные, а половина нет». Это неправильно; в задаче «да‑нет» всегда есть ровно два возможных ответа, и каждый из них равновероятен, если вопрос задаётся оптимально. Если вы задаёте вопросы не по принципу двоичного поиска, то количество вопросов может вырасти, но это будет неэффективно.
Чтобы избежать «неправильных» вопросов, придерживайтесь следующего правила:
В каждом вопросе делите текущее множество почти пополам.
Если вы будете задавать вопросы, например, «Число больше ли чем 10?», и в ответе «ДА», но число действительно меньше 10, вы потеряете информацию. Поэтому оптимальные вопросы всегда строятся по принципу «половина–половина».
Практическая реализация: онлайн‑генератор «Да‑или‑Нет»
Существуют сервисы, которые помогают быстро реализовать двоичный поиск. Один из них – Uchi.ru/otvety. В нём можно задать диапазон чисел и система автоматически сформирует последовательность вопросов, которые понадобятся для угадывания.
Важно: при копировании материалов с сайта указывайте ссылку uchi.ru/otvety, как это указано в правилах использования ресурса.
- Для любого диапазона из N чисел минимальное количество «да‑нет» вопросов равно ⌈log₂ N⌉.
- Эти вопросы реализуются при помощи двоичного поиска.
- Примеры:
– 0–15: 4 вопроса.
– 0–127: 7 вопросов.
– 1–1000: 10 вопросов. - Если диапазон не является точной степенью двойки, округляем результат вверх.
Таким образом, независимо от того, сколько чисел вы хотите угадать, всегда можно быстро найти оптимальный путь и ограничить количество вопросов до минимально возможного.
Если хотите узнать более подробно, как работает логарифм и почему именно 2‑значный поиск самый эффективный, можно изучить материалы по теории информации или посмотреть видеоруководства по двоичному поиску в интернете.
Ссылки на источники
- Uchi.ru/otvety – онлайн‑инструмент для решения задач с «да‑нет» вопросами.
- Книга «Алгоритмы: построение и анализ» (Кормен и др.) – глава о двоичном поиске.