Как угадать номер от 1 до 100

Представьте: вы загадываете любое число от 1 до 100, а ваш собеседник (или компьютер) угадывает его всего за 7 попыток или меньше. Это не телепатия и не фокус-покус — это фундаментальный алгоритм информатики, известный как бинарный поиск (или поиск методом деления пополам). В этой статье мы подробно разберем, как это работает, почему именно 7 попыток и как применить этот метод на практике.

Суть метода: Стратегия «Разделяй и властвуй»

Главный секрет угадывания числа за минимальное количество шагов, каждый раз называть число, которое делит текущий диапазон возможных вариантов ровно пополам.

Вместо того чтобы перебирать числа по порядку (1, 2, 3…), что заняло бы до 100 попыток, мы используем обратную связь («Больше», «Меньше», «Равно»), чтобы мгновенно отсекать половину оставшихся вариантов.

Пошаговый алгоритм

1. Начальный диапазон: 1 – 100.
2. Находим середину: (1 + 100) / 2 = 50,5 → округляем до 50 (или 51). Называем это число.
3. Анализируем ответ:
   • «Равно» — победа!
   • «Больше» — новый диапазон: 51 – 100.
   • «Меньше» — новый диапазон: 1 – 49.
4. Повторяем: Снова находим середину нового диапазона и называем её.
5. Так продолжаем, пока не угадаем.

Пример игры: Загадано число 63

Давайте проследим за ходом мыслей игрока, использующего бинарный поиск:

Попытка	Текущий диапазон	Называемое число (середина)	Ответ	Новый диапазон
1	1 – 100	50	Больше	51 – 100
2	51 – 100	75	Меньше	51 – 74
3	51 – 74	62	Больше	63 – 74
4	63 – 74	68	Меньше	63 – 67
5	63 – 67	65	Меньше	63 – 64
6	63 – 64	63	Равно!	—

Результат: Число угадано за 6 попыток. Седьмая даже не понадобилась.

Математика успеха: Почему именно 7?

Всё дело в степенях двойки. Каждый шаг бинарного поиска делит множество вариантов на 2.

• После 1 шага остается ≤ 50 вариантов.
• После 2 шагов — ≤ 25.
• После 3 шагов, ≤ 12.
• После 4 шагов — ≤ 6.
• После 5 шагов, ≤ 3.
• После 6 шагов — ≤ 1-2.
• После 7 шагов, гарантированно 1 вариант.

Математически это выражается формулой: 2ⁿ ≥ N, где N — размер диапазона, n — количество попыток.

Для диапазона 1–100: 2⁷ = 128 ≥ 100. Значит, 7 попыток достаточно.

Интересный факт: За 7 попыток можно угадать число не только до 100, а до 128 (или от 0 до 127). Если у вас будет 8 попыток — диапазон расширится до 256, 9 попыток, до 512, 10, до 1024 и т.д..

Практическое применение: Не только игры

Бинарный поиск — это не просто парlor trick (салонный фокус). Это одна из важнейших структур данных и алгоритмов в программировании.

Где это используется:

• Базы данных и индексы: Поиск записи в отсортированной таблице на миллионы строк за доли миллисекунды (B-деревья основаны на этом принципе).
• Словари и справочники: Когда вы ищете слово в бумажном словаре, вы интуитивно используете бинарный поиск: открываете на середине, понимаете, в какой половине искать дальше.
• Отладка кода (Git Bisect): Поиск коммита, в котором появился баг, путем деления истории пополам.
• Численные методы: Нахождение корней уравнений (метод дихотомии).

Как научиться угадывать в уме (Советы)

Чтобы повторить этот фокус у друзей без калькулятора, нужно быстро считать середину диапазона. Вот несколько приемов:

1. Метод «Сумма границ делить на 2»: Складываете минимальное и максимальное число текущего диапазона и делите на 2. Пример: диапазон 63–74. (63+7 -)=137. 137/2=68,5 → 68 или 69.
2. Метод «Половина длины»: Считаете длину диапазона (74-63=11), делите на 2 (5,5 → 5), прибавляете к минимуму (63+5=68).
3. Запоминание «опорных точек»: Для диапазона 1–100 ключевые середины: 50, 25, 75, 12, 37, 62, 87. Зная их, вы быстрее ориентируетесь на первых шагах.

Реализация на коде (Python)

Если вы хотите написать программу, которая угадывает число пользователя, вот простейший пример на Python:

def guess_number:
 low = 1
 high = 100
 attempts = 0
 
 print("Загадайте число от 1 до 100. Я угадаю за 7 попыток!")
 input("Нажмите Enter, когда загадаете...")
 
 while low <= high:
 attempts += 1
 mid = (low + high) // 2 # Целочисленное деление
 
 print(f"
Попытка {attempts}: Это число {mid}?")
 answer = input("Введите: '>' (если больше), '<' (если меньше), '=' (угадал): ").strip
 
 if answer == '=':
 print(f"
Ура! Я угадал ваше число {mid} за {attempts} попыток!")
 break
 elif answer == '>':
 low = mid + 1
 elif answer == '<':
 high = mid ⎼ 1
 else:
 print("Не понял ответ. Введите >, < или =.")
 attempts -= 1 # Не считаем неверный ввод
 
 if low > high:
 print("Что-то пошло не так... Вы, наверное, ошиблись в ответе?")

if __name__ == "__main__":
 guess_number

Расширение игры: Вариации и усложнения

Игра «Угадай число» за компьютером

Вы загадываете число, а компьютер угадывает. Это классическая задача для обучения основам алгоритмов.

Обратная игра: Компьютер загадывает, вы угадываете

Здесь ваша задача — применить бинарный поиск самим. Начинайте с 50. Это отличная тренировка мышления.

Угадывание с обманом (Ulam’s game / Реньи-Улам)

А что, если загадывающий может один раз соврать (сказать «Больше» вместо «Меньше»)? Тогда простого бинарного поиска недостаточно — нужно задавать контрольные вопросы или использовать коды с коррекцией ошибок (коды Хэмминга). Это уже тема для отдельной глубокой статьи.

Частые ошибки новичков

• Случайные числа: Говорить «37», потом «82», потом «12». Это не поиск, это лотерея. Шанс угадать за 7 попыток минимален.
• Нецелое деление: Забывать, что середина диапазона 1–3 — это 2, а не 1,5. Всегда округляйте вниз (floor) или вверх, но последовательно.
• Потеря границ: После ответа «Больше 50» новый минимум — 51, а не 50. Иначе рискуете назвать 50 снова и зациклиться.

Угадывание числа от 1 до 100 за 7 попыток, это идеальная демонстрация силы логарифмической сложности O(log n). Там, где линейный перебор требует 100 операций, бинарный поиск справляется за 7. Этот принцип лежит в основе эффективности современных поисковых систем, баз данных и файловых систем.

Попробуйте прямо сейчас: загадайте число другу и угадайте его, используя стратегию «дели пополам». Вы покажете не фокус, а алгоритмическое мышление!

---

Краткая шпаргалка для запоминания:

1. Старт: 50
2. Если больше → 75; если меньше → 25
3. Дальше — всегда середина текущего диапазона.
4. Помните: 2⁷ = 128 > 100. 7 шагов — гарантия успеха.