Давайте сымитируем игру «Угадайка» между двумя людьми. Для этого нужно написать программу, которая отгадывает загаданное целое число от 1 до 1000 включительно.
Пользователь (или тестирующая система) загадывает число и не сообщает его вашей программе.
Угадать число нужно не более, чем за 10 попыток.
На каждую попытку пользователь отвечает одной из фраз:
- Больше;
- Меньше;
- Угадал!
Данная задача проверяется интерактивно. Другими словами, пока вы не выведите своё число, система не предоставит вам данных.
Пример
Предположим, что было загадано число 123
Диалог вашей программы с пользователем/системой должен выглядеть так:
500
Меньше
250
Меньше
125
Меньше
63
Больше
94
Больше
109
Больше
117
Больше
121
Больше
123
Угадал!Решение
В этой задаче мы знакомимся с алгоритмом бинарного (двоичного ) поиска.
Кратко суть алгоритма в следующем. Мы предполагаем число из середины интервала, если на говорят больше, мы называем число из середины правого, относительно нашего числа, интервала. Если число оказалось меньше — то из середины правого.
Повторяем этот процесс до тех пор, пока не найдем нужное число. Если алгоритм реализован правильно, то вам потребуется не более 10 попыток.
Приведено два решения задачи:
C использованием «дельты» — числа, отняв или прибавив которое можно получить следующую середину отрезка.
С использованием начала и конца отрезка.
Второе решение более распространено, первое выглядит более лаконично.
Обратите внимание, что во втором решении верхний диапазон сдвинут до 1001. Это нужно потому, что на последнем этапе при загаданном значении 1000 мы никогда не достигнем этого результата с помощью операции //, потому что (999 + 1000) // 2 всегда будет равно 999.
Посмотреть код
Решение
current_guess = 500
step = current_guess // 2
print(current_guess)
while (response := input()) != 'Угадал!':
if response == 'Меньше':
current_guess -= step
elif response == 'Больше':
current_guess += step
if step >= 2:
step = (step + 1) // 2
print(current_guess)
Решение
low, high = 1, 1001
guess = (low + high) // 2
print(guess)
while (response := input()) != "Угадал!":
if response == "Меньше":
high = guess
elif response == "Больше":
low = guess
guess = (low + high) // 2
print(guess)
Очень сильно хотел решить через рекурсию
трудности возникли когда загадывалось число 1000, помог Ваш сайт, спасибо
def recursiv(string, low, hight):
q = (hight — low) // 2 + low
print(q)
s = input()
if s == ‘Угадал!’:
return
elif s == ‘Меньше’:
recursiv(s, low, q)
elif s == ‘Больше’:
if q == 999:
recursiv(s, q, hight + 1)
else:
recursiv(s, q, hight)
string = »
low = 1
hight = 1001
recursiv(string, low, hight)
Первое решение не удовлетворяет требованию 10 попыток, например, для числа 751.
Спасибо, что обратили внимание.
Вы совершенно правы. Кроме того, там оказалась излишняя печать. Поправил.
Большое спасибо за подсказку. А зачем к дельте прибавлять 1 при ее делении на 2? Опытным путем установила, что если не прибавить 1, то 10 попыток не хватит. А теоретическое обоснование есть?
1000(1001) // 2 = 500
500(501) // 2 = 250
250(251) // 2 = 125
125(126) // 2 = 62(63)
62(63) // 2 = 31
31(32) // 2 = 15(16)
15(16) // 2 = 7(8)
7(8) // 2 = 3(4)
3(4) // 2 = 1(2)
1(2) // 2 = 0(1)
как видно, если не прибавлять, то на последнем шаге дельта становится равна нулю и мы никогда не дойдем до финала.
так что, в основном, для того, чтобы при достижении дельтой единицы вы могли сдвинуться дальше. при этом +1 не увеличивает количество шагов (числа в скобочках)
Доброго времени суток!) Первое решение не может найти число 1. Первое решение будет работать только если в переменной number будет число 501, как во втором решении, но в этом случае он не может найти число 1000, будет 1001)
цепочка ответов для первого решения (загадано 1):
1, number=500, delta=250 >1
2, number=250, delta=125 >1
3, number=125, delta=63 >1
4, number=62, delta=32 >1
5, number=30, delta=16 >1
6, number=14, delta=8 >1
7, number=6, delta=4 >1
8, number=2, delta=2 >1
9, number=0, delta=1 <1
10, number=1, delta=1
Цепочка решений для второго (загадано 1000):
1: begin=1, end=1001, ask=501 <1000
2: begin=501, end=1001, ask=751 <1000
3: begin=751, end=1001, ask=876 <1000
4: begin=876, end=1001, ask=938 <1000
5: begin=938, end=1001, ask=969 <1000
6: begin=969, end=1001, ask=985 <1000
7: begin=985, end=1001, ask=993 <1000
8: begin=993, end=1001, ask=997 <1000
9: begin=997, end=1001, ask=999 <1000
10: begin=999, end=1001, ask=1000
По второму решению всё получается как вы и описали)
А по первому решению получается так:
это означает, что вы не обратили внимание, что если у нас изменилось соотношение загаданного и текущего чисел, надо менить знак у дельты (если прибавляли, начинать отнимать и наоборот.)
ps. Хотя нет. почему при загаданной 1 у вас 0 меньше загаданного?
str1 = «Угадал!»
str2 = «Меньше»
str3 = «Больше»
a = 0
b = 1001
c = 500
user_string = «»
print(c)
while user_string != str1:
user_string = str(input())
if user_string == str2:
b = c
c = c — ((b — a) // 2)
print(int(c))
elif user_string == str3:
a = c
c = c + ((b — a) // 2)
print(int(c))
Здравствуйте! Вот такое решение чекер пропустил.
И чем же второе решение отличается от первого, кроме имён переменных? (и замены = на +=)
Если прочитать текст, то можно заметить, что разница должна была быть существенная.
Очевидно, что имела место невнимательность с моей стороны при обновлении страницы. Сейчас все исправлено.