Решение задачи!

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

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

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

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

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

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

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

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

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

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