Банки(#1019) 2^n(#1021)
#1020

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

Наверх