Как угадать число за 7 попыток: математический трюк

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

Как угадать число за 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 и так далее. 

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

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

Художник:

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

Корректор:

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

Вёрстка:

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

Соцсети:

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

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

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

medium
Тестировщик: кто это такой, что он делает и как им стать
Тестировщик: кто это такой, что он делает и как им стать

Что нужно уметь и сколько можно заработать поиском ошибок

easy
Как стать руководителем ИТ-команды за 5 лет
Как стать руководителем ИТ-команды за 5 лет

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

Сложная задача про дачу, малину и макроэкономику
Сложная задача про дачу, малину и макроэкономику

Продолжение задачи про альтернативные издержки

medium
Вирусная задача про два круга, которую может решить каждый, хотя не знает об этом
Вирусная задача про два круга, которую может решить каждый, хотя не знает об этом

Попробуйте решить и вы

easy
Как вычислить день рождения
Как вычислить день рождения

Простой трюк для знакомств

easy
Новая задача про продуктивность
Новая задача про продуктивность

Простая математическая задачка для восстановления экономики.

easy
Блогеры и колёса
Блогеры и колёса

Эту задачу могут решить только люди с абстрактным мышлением

easy
Крутейшие задачи на комбинаторику
Крутейшие задачи на комбинаторику

Комбинаторика и поиск наилучшего решения для всех.

medium
easy