Как угадать число от 0 до 100 за 7 попыток?

Как угадать число от 0 до 100 за 7 попыток?

Простой математический трюк, который раскрывает мощь алгоритмов

Программист развлекает сына: 

— Загадай любое целое число от 0 до 100!

— Загадал. 

— Спорим, я угадаю его за 7 попыток или быстрее? Я буду называть числа, а ты — отвечать, оно больше, меньше или равно загаданному.

— Ахахах, ты не сможешь угадать за 7 попыток! 

— Спорим, угадаю!

— Ну давай, покажи своё кунфу…

6 попыток спустя отец угадал число, а ребёнок сидит в шоке. Они попробовали снова, и во второй раз отец угадал число за семь попыток. В третий — за четыре. Сколько бы они ни играли, число всегда угадывалось за 7 попыток или менее.

Вопрос: как?

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

👉 каждый раз называть число, которое делит пополам диапазон возможных чисел.

Этот приём каждый раз в 2 раза сокращает область поиска, и в конце нам становится легко угадать даже простым перебором. 

Допустим, сын загадал число 63. Тогда делаем так:

  1. Находим середину диапазона от 0 до 100 — это 50. Называем это число. Сын говорит «Больше».
  2. Значит, его число лежит в диапазоне от 50 до 100. Находим его середину — 75. Называем это число. Сын говорит «Меньше».
  3. Ага, значит, его число находится в диапазоне от 50 до 75. Находим середину — 62. Называем это число. Сын говорит «Больше».
  4. Поиск снова сузился: от 62 до 75. Середина — 67. Называем это число. Сын говорит «Меньше».
  5. У нас осталось 3 попытки и 4 числа. Найдём ещё одну середину — 64. Называем это число. Сын говорит «Меньше».
  6. Раз у нас число, которое больше, чем 62, и меньше, чем 64, то это число 63. Даже седьмая попытка не понадобилась.

Этим способом можно угадать любое число от 0 до 100 за 7 попыток или меньше. Главное — быстро и правильно считать в уме середину и помнить, как выглядит сейчас твой рабочий диапазон.

А если число будет больше? 

На самом деле за 7 шагов можно угадать любое число от 0 до 127 или от 1 до 128. Всё потому, что два в седьмой степени — это как раз 128. Каждый раз, когда мы делим рабочий диапазон на 2, мы как будто убираем одну степень у двойки, постепенно уменьшая наш диапазон угадывания до двух чисел. Для верности лучше добавить ещё попытку. 

Если бы у нас было 8 попыток, можно было бы угадывать числа до 256. 9 попыток — 512 и так далее. 

А где это используется в народном хозяйстве? 

На этом принципе построена модель данных «Бинарное дерево» — это одна из важнейших технологий для составления словарей и поиска данных. Прочитайте об этом в статье про бинарные деревья.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Олег Вешкурцев

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства и компенсация, если вы пойдёте работать в «Яндекс».
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Как стать руководителем ИТ-команды за 5 лет
Как стать руководителем ИТ-команды за 5 лет

Александр Штыков: путь от контент-менеджера до тимлида.

Как отправить JSON-данные на сервер
Как отправить JSON-данные на сервер

Первый шаг на пути к облачному хранению данных.

Кто такой инженер по тестированию и стоит ли на него учиться

Раскладываем по полочкам новую профессию.

Задача про полторы белки

Не спрашивайте, просто попробуйте решить.

Задача с подвохом
Сложная задача про бабушку и домашние помидоры
Головоломка про альпиниста и короткую верёвку

Разбежавшись, слезет со скалы.

Задача про новую должность и выбор зарплаты

Когда вы решили все логические задачи на собеседовании, вам предложат последнюю — самую важную.

Задача про безумного рекрутера и большой офис
Задача про безумного рекрутера и большой офис

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

Задача про математику и секс
Задача про математику и гендерное равенство

Как логика, математика и статистика приводят к созданию новой крепкой семьи.

Загадка 1 000 пробирок
Загадка о тысяче пробирок
Решаем кодом задачу про безумного рекрутера

Пусть рассудит машина.

Задача про охрану периметра

Решаем тремя способами: как математик, инженер и программист.

Находчивый инженер в кафе

Как логика побеждает разгильдяйство.

easy