Задача 15: A to B
Я загадаю целое число из интервала [A,B]. Напишите программу,
которая за минимальное число вопросов отгадает это число. Играть
будем так. Я сообщаю программе числа A и B, программа выводит свою
версию ответа. Если это меньше задуманного мною, я сообщу программе
об этом числом -1, если больше - числом 1, а если угадано -
числом 0. Так будет продолжаться, пока программа не угадает число
(естественно, я буду играть честно!). Постарайтесь, чтобы ваша
программа угадала число за минимальное число ходов.
Ввод-вывод: В первой строке вводите с клавиатуры два целых
числа через пробел - границы диапазона. Программа на экран выводит
свою версию в новой строке. С новой строки вы вводите "-1", "1" или
"0" ( без кавычек). Так продолжается до того момента, пока число не
будет угадано (т.е. ваш ответ "0" должен завершить работу
программы).
Пример:
( я задумал число 2)
Ввод: 1 6
Вывод: 3
Ввод: 1
Вывод: 2
Ввод: 0
Ограничения : -100000<=A<=B<=100000
Решение:
У нас есть два начальных числа, причем X > A и X < B. Выберем X1 =
((A + B) / 2) и будет выполнен один из трех вариантов:
1) Число совпало, вываливаемся, ура!
2) Число меньше, чем X1. Тогда присваиваем B значение X.
3) Число больше, чем X1. Тогда присваиваем A значение X.
Повторяем вышеприведенные строки, до тех пор, пока не получим
загаданное число.
В этом решении количество действий порядка log2(B-A) (логарифм по
основанию 2), т.е. каждый раз мы уменьшаем область поиска вдвое.
Далее
ð
