Боб и его старший брат Альберт часто играют в игру "Угадай число". Сначала Боб загадывает число K в диапазоне от 1 до N. Потом Альберт называет числа, а Боб говорит, является названное число больше или меньше загаданного или Альберт назвал правильное число. Альберт для угадывания всегда использует следующую стратегию.
1 шаг. Альберт задает A=1 и B=N
2 шаг. Альберт вычисляет M – целую часть среднего арифметического чисел A и B
3 шаг. Альберт называет число M
4 шаг. Если Боб говорит "Меньше", то Альберт полагает A=M+1 и переходит к шагу 2
5 шаг. Если Боб говорит "Больше", то Альберт полагает B=M−1 и переходит к шагу 2
6 шаг. Если Боб говорит "Угадал", то игра заканчивается
Например, пусть N=9, а задуманное Бобом число K равно 6. Сначала A=1, B=9. Альберт называет число 5 и получает ответ "Меньше". Теперь A=6, B=9. Следующее число-попытка 7. Боб отвечает "Больше". Теперь A=6, B=6. Альберт называет 6 и получает ответ "Угадал".
Напишите программу, которая определяет, сколько чисел придется назвать Альберту, прежде чем он получит ответ "Угадал" от Боба.
Скачать
Комментариев нет:
Отправить комментарий