Так как я думаю об этом есть у вас есть переменная х = 50, если это слишком высока, то вы разделите на 2 и х изменяется на 25, если 25 является слишком низким, то вы бы умножить на 1,5
Это будет работать нормально для начальной итерации, поскольку, если 50 слишком мало, умножение на 1,5 даст вам 75. Если оно слишком велико, то разделение на 2 даст вам 25. В обоих случаях вы переходите к средней точке нового диапазона.
Однако предположим, что ваш номер равен 99. После этого первого вопроса ваша новая средняя точка будет 75, и вы снова зададите вопрос. Так как 75 все еще слишком низко, вы умножаете его на 1,5 и заканчиваете примерно 112, что значительно превышает допустимый диапазон значений.
Что вам нужно сделать, это, а не простым умножением средней точки значения, выработать новую среднюю точку на основе размера текущего диапазона. Вы можете сохранить другую переменную с дельта-значением (которое добавляется или вычитается из текущей средней точки, чтобы получить новую среднюю точку), которая начинается с 25 и половин для каждой итерации.
Проще говоря, это приложение двоичного поиска (или измельчения). Но есть гораздо более простой способ, используя только высокие и низкие границы (с расчетной серединой) и отрегулируйте один этих границ на основе ответа пользователя.
В псевдо-коде, это было бы что-то вроде (немного изменен, чтобы получить ответы yes
, more
и less
:
set low to 1 # starting range
set high to 100
set answer to 'more' # force entry to loop
until answer is 'yes':
if high is low: # only one possibility left
say 'Aaah, it must be ', high
exit
mid = (high + low)/2 # choose midpoint and ask about it
say 'Is it ', mid
get answer
if answer is 'yes': # if match, claim victory and exit
say "I got it."
exit
if answer is 'more': # otherwise adjust range depending on answer
low = mid + 1 # - must be greater than mid
else:
high = mid - 1 # - must be less that mid
Это гораздо более простое решение, тот, который также предотвращает проблемы большинство начинающих найти при первом их бинарном поиске, который попадает в бесконечный цикл в конце, потому что (например) (28 + 29)/2
снова дает вам 28
, что означает, что вы никогда не сможете изучить номер элемента 29
. В приведенном выше псевдокоде факт о том, что новый диапазон исключает старую середину означает, что этого не может быть.
В качестве дополнения, вот в Python (2.7, Python 3, возможно, придется использовать input
вместо raw_input
) код, который реализует выше (достаточно близки, чтобы показать, почему я считаю Python конечной псевдокод языка):
import sys
low = 1
high = 100
answer = "more"
while answer != "yes":
if high == low:
print 'Aaah, it must be', high
sys.exit()
mid = (high + low)/2
print 'Is it', mid
answer = raw_input()
if answer == "yes":
print "I got it."
sys.exit()
if answer == "more":
low = mid + 1
else:
high = mid - 1
Я не предоставлю то же самое в Java, так как (1) Я подозреваю, что это может быть классную и (2) вы будете стать лучшим разработчиком, если вы делаете это самостоятельно, классную или нет.
C#, Java, псевдокод? ... –
Честно говоря, это выглядит как домашнее задание. –
мы могли бы сделать это за вас - и вы узнаете, что? –