Небольшая головоломка, которую можно сыграть с друзьями, коллегами или даже с компьютером. Один человек загадал целое число в диапазоне от 1 до 100, а другой задаёт вопросы, на которые ответчик может отвечать только «да» или «нет». Цель — узнать загаданное число за минимальное количество вопросов.
Правила игры
- Загадчик выбирает число от 1 до 100 и держит его в уме.
- Угадывающий может задавать любые вопросы, но ответы могут быть только «да» или «нет».
- Вопросы могут быть как простыми («Число > 50?»), так и более сложными («Число 27?»).
- Игра заканчивается, когда угадывающий получает число, либо когда исчерпывается заданное число вопросов.
Вопрос «Число 27?» звучит длиннее, но он тоже допустим. В реальности наиболее эффективным оказывается стратегия, основанная на разбиении диапазона пополам — бинарном поиске.
Почему 7 вопросов?
В диапазоне от 1 до 100 существует 100 возможных чисел. Каждый вопрос, на который ответ можно дать «да» или «нет», в лучшем случае может разделить множество вдвое. Число разбиений, нужное чтобы получить 1 элемент, равно ⌈log₂ 100⌉ = 7. Поэтому 7 вопросов — это абсолютный минимум, при условии, что ответы честны.
Алгоритм бинарного поиска (классическая стратегия)
Основная идея: каждый вопрос сокращает диапазон кандидатов вдвое. Ниже – пошаговый алгоритм для угадывающего.
- Установить границы:
левый = 1,правый = 100. - Пока
левый ≤ правый:- Подсчитать середину:
среднее = (левый + правый) // 2. - Спросить: «Число больше
среднее?» - Если ответ «да» – число находится в правой половине, поэтому
левый = среднее + 1. - Если ответ «нет» – число находится в левой половине (или равно
среднее), поэтомуправый = среднее. - Если
левый == правый, то число найдено.
- Подсчитать середину:
Псевдокод
левый = 1 правый = 100 пока левый <= правый: среднее = (левый + правый) // 2 если (загадчик отвечает "да" на "Число > среднее?"): левый = среднее + 1 иначе: правый = среднее если левый == правый: вывести "Ваше число: " + левый остановить
Практическая реализация на Python
Ниже пример простейшей консольной программы, реализующей описанный алгоритм:
def guess_number:
left, right = 1, 100
attempts = 0
while left <= right:
mid = (left + right) // 2
attempts += 1
print(f"Попытка {attempts}: Я думаю, ваше число больше {mid}? (да/нет)")
answer = input.strip.lower
if answer == "да":
left = mid + 1
else:
right = mid
if left == right:
print(f"Ваше число: {left}. Задачка решена за {attempts} вопросов!")
break
guess_number
Ещё один вариант: задавать вопрос «Число равно mid?», а если ответ «нет», то уточнять «больше» или «меньше». Такой подход тоже гарантирует победу за 7 вопросов.
Вариации и интересные детали
- Ответы «нет» и «меньше» – в некоторых вариантах правил можно уточнять, что «нет» означает «меньше» (если вопрос был «Число > X?»). Это упрощает логику.
- Нечестные ответы – если ответчик может давать ложные ответы, то число вопросов резко возрастает. В таком случае применяются более сложные алгоритмы (например, ориентированные на ошибки).
- Проверка честности – можно добавить «тестовые» вопросы, чтобы убедиться, что ответы согласованы.
- Бинарный поиск в другом диапазоне – алгоритм легко масштабируется: для 1–1000 понадобится 10 вопросов, для 1–1 000 000 – 20 вопросов.
Почему бинарный поиск так эффективен?
Бинарный поиск — это фундаментальный алгоритм из области информатики и математики. Он использует свойство, что каждый «да/нет» ответ может исключить примерно половину оставшихся вариантов. Это минимизирует количество вопросов, потому что:
- В каждом шаге количество возможных чисел сокращается вдвое.
- После 7 шагов остаётся ровно одно число.
- Ни один другой алгоритм не может гарантировать меньшее число вопросов при полностью честном ответчике.
Если вы хотите сыграть в эту игру, следуйте простому правилу: задавайте вопросы «Число > X?» и постепенно сужайте диапазон. За 7 вопросов вы точно угадаете любое число от 1 до 100. Это классический пример того, как математика и алгоритмы помогают решать задачи с минимальными ресурсами.
Попробуйте саму программу, измените диапазон, посмотрите, как меняется количество вопросов. Удачной отгадывания!