§ ПМ Метод половинного деления
Подсчитайте, какое наибольшее число шагов может понадобиться для угадывания по этому алгоритму числа X∈[0,100].
Решение
По блок-схеме на рис. . сначала выбирают середину текущего целочисленного отрезка: . Затем сравнивают с загаданным числом . Если числа не равны, исключают и всю половину отрезка, в которой быть не может. Один шаг угадывания будем считать одним названным числом и его проверкой.
Первоначально возможны все числа от до , то есть число. После первой проверки в наиболее длинной оставшейся части будет не более чисел, после второй — не более . Дальше верхние границы числа возможных значений таковы:
.
Когда остаётся одно число, его всё равно нужно назвать и проверить. Значит, после шести неудачных проверок седьмая обязательно будет удачной. Покажем случай, когда действительно нужны все семь шагов: пусть загадано число .
| Шаг |
|
|
Названо |
Итог сравнения |
|
|
|
|
, далее |
|
|
|
|
, далее |
|
|
|
|
, далее |
|
|
|
|
, далее |
|
|
|
|
, далее |
|
|
|
|
, далее |
|
|
|
|
, число угадано |
Таким образом, семь шагов достаточно для любого числа из указанного диапазона, а для числа меньше семи шагов недостаточно.
Ответ
Наибольшее число шагов угадывания — .
