Я загадал случайное число от 1 до 10. Как быстро вы сможете отгадать его? Кому-то повезёт с первой попытки. Кто угодно уж точно отгадает с десятой. В среднем у людей будет получаться за 5 попыток. А как можно точно сделать это быстрее всего? Чтобы это было проще, после неправильного ответа я буду говорить вам, большее или меньшее число я загадал.

Кстати, я загадал число 8

Правильный ответ — за 4 попытки. Не очень впечатляет: лишь на 1 меньше 50%. Но что если я скажу вам, что отгадаю 1 число из 100 всего за 7 попыток? И одно из тысячи всего за 10.

Знание о том, больше или меньше загаданное число нашей попытки очень сильно облегчает задачу. Например, мы можем предположить число 9. Вероятность попасть в любое число одинакова, поэтому девятка ничем не хуже других. Если она и была ответом, мы победили, а если нет, услышав «меньше» мы будем знать, что и 10 не является загаданным числом! Так можно пройти в 2 раза меньше чисел, и мы уже улучшим средний результат.

Но есть ещё более эффективный способ. Мы можем взять число из середины последовательности. Если не угадаем, у нас тогда останется ещё половина вариантов, это верно. Но мы избавимся и от целой другой половины! Если в случае 10 это не так важно, то если нам загадали число от 1 до 100, мы даже неправильным предположением убираем 50 вариантов!

С оставшейся половиной можно проделать то же самое. Давайте посмотрим, как это работает на примере. 8, которую я загадал в начале отгадывается всего за 2 шага — это неинтересно. Давайте разберём на примере от 1 до 100. На этот раз я сразу скажу ответ, чтобы вы следили за его поиском: это число 43.

–Это число 50? –Меньше –Это число 25? –Больше –Это число 37? –Больше –Это число 43? –Верно!

Мы управились всего за 4 шага! При случайном угадывании нам потребовалось бы 50. Попробуйте сами так «отгадать» любое число из 1000 — вам скорее всего понадобится даже меньше 10 шагов.

4, 7, 10 — почему именно эти числа? Вы могли бы подумать, что я просто прибавляю 3, но это неверно: 1 из 10000 точно отгадывается уже за 14 шагов.

В нашем алгоритме мы каждый раз делим оставшийся интервал на 2. Давайте попробуем решить обратную задачу: через сколько умножений на 2 мы достигнем определённой длины? 222 = 8 — это всё ещё не равно 10. Но, умножив 2 на себя 4 раза, другими словами, возведя 2 в 4 степень, мы получим 16, что явно больше 10. Значит, можно гарантированно угадать число за 4 шага! Математическая операция, которая позволит это посчитать, — обратная к возведению в степень: логарифм по основанию 2.

Этот график растёт очень медленно

Степень двойки растёт очень быстро. С этим связаны известные факты: почти невозможно сложить лист бумаги пополам больше 7 раз, что неудивительно — в нём будет уже 128 слоёв! Рвать листы бумаги пополам также с определённого момента становится очень сложно

Слишком много слоёв

По легенде древнеиндийский математик создал шахматы и показал их правителю страны. Тому игра настолько понравилась, что он позволил изобретателю самому выбрать себе награду. Математик попросил одно зёрнышко пшеницы за первую клетку, 2 за вторую и так далее до конца доски. Правитель обиделся, что мудрец просит так мало, но повелел выплатить награду. Однако, оказалось, что сделать это невозможно: количество зерна превышает урожай пшеницы за всю историю человечества, а его масса бы составила 1200 миллиардов тонн!

Даже не пытайтесь дойти до конца

Если пронумеровать каждый атом на нашей планете и попросить найти один определённый, это можно сделать всего лишь за 167 раз! У числа атомов на нашей планете, к слову, 50 нулей.

Такой алгоритм поиска широко используется в программировании — там, где количество шагов и время критически важно. Его также можно несколько улучшить. Наша последовательность расположена по возрастанию, и в центре находится число 5 (если округлять середину вниз). Но если число загадывает человек, он с большей вероятностью загадает число 7. Если расположить его в середине, часто мы будем попадать с первого раза! Если также удобно расположить другие числа, можно ещё больше улучшить алгоритм.

Спасибо за чтение!