Задача на Python. Как найти число?

Question

[nihi1ist]

Решаю задачу. Надо написать код, с помощью которого можно вычислить число (от 1 до 100) отвечая на вопросы (1 — равно, 2 — больше, 3 — меньше.). При этом число надо угадать в пределах 7 попыток. Логически я представляю как это сделать, но как реализовать в коде до меня не доходит.
Начальная цифра 50, шаг допустим 24. Как отследить, что если сначала было больше, число уменьшилось на 24 и стало меньше. То надо сократить шаг в половину?

Comments

[Saboteur]

А почему шаг 24?
Вам шаг рассчитывать не нужно. Вам нужно чтобы пользователь вводил число, а вы сравнивали его с вашим загаданным и выводили равно, больше или меньше.

[nihi1ist]

Saboteur, здесь обратная ситуация. Угадать должна программа. Загадывает человек, он же отвечает в стиле холодно-горячо.

Answer 1

[antares4045]

Ваша задача называется бинарный поиск

def binsearch(min, max, check):
    support = (min + max) // 2
    result = check(support)
    if result == 'меньше':
        return binsearch(support+1, max, check)
    if result == 'больше':
        return binsearch(min, support-1, check)
    return support

def guess(num):
    print('загадано', num)
    def check(req):
        result = 'равно' if req == num else 'меньше' if req < num else 'больше'
        print(f'это {req}?', '-', 'Да' if result=='равно' else f'Нет, твоё число {result}')
        return result
    return check


binsearch(0, 100, guess(10))
print('='*30)
binsearch(0, 100, guess(27))
print('='*30)
binsearch(0, 100, guess(50))
print('='*30)
binsearch(0, 100, guess(100))

загадано 10
это 50? - Нет, твоё число больше
это 24? - Нет, твоё число больше
это 11? - Нет, твоё число больше
это 5? - Нет, твоё число меньше
это 8? - Нет, твоё число меньше
это 9? - Нет, твоё число меньше
это 10? - Да
==============================
загадано 27
это 50? - Нет, твоё число больше
это 24? - Нет, твоё число меньше
это 37? - Нет, твоё число больше
это 30? - Нет, твоё число больше
это 27? - Да
==============================
загадано 50
это 50? - Да
==============================
загадано 100
это 50? - Нет, твоё число меньше
это 75? - Нет, твоё число меньше
это 88? - Нет, твоё число меньше
это 94? - Нет, твоё число меньше
это 97? - Нет, твоё число меньше
это 99? - Нет, твоё число меньше
это 100? - Да

Comments

[Михаил]

Ну вот зачем? Как человек будет учиться, если вы ему готовое решение даёте =_=

[antares4045]

Михаил, честно говоря -- просто залип на моменте, когда начал писать о опорном элементе и смещающемся окне без использования кода и просто написал решение -- не выспался наверное

К тому же, учитывая как был сформулирован вопрос, превратить этот код в нужный автроу вопрса... неоторая техническая задача

[nihi1ist]

Возможно ли в def() использовать input()?
Если возможно, то с примером пожалуйста. А то гугл не помог в этом вопросе.

[antares4045]

nihi1ist, конечно

[nihi1ist]

Михаил, решение не готовое. Мне его надо теперь переделать без использования def и с вводом ответов пользователем. В коде по любому успею разобраться, а значит запомнить.

[nihi1ist]

antares4045, ещё вот этот участок не пойму:

if req == num else 'меньше' if req < num else 'больше'

Пытался оформить построчно, но не сходится пасьянс. Нет двоеточий, нет текста между предполагаемым двоеточием и else. Можете объяснить или ссылку на материал какую нибудь?

[antares4045]

import math

def binsearch(min, max, check, depth=1, maxdepth=None):
    if maxdepth is None:
        maxdepth = math.ceil(math.log(max-min + 1, 2))

    if depth > maxdepth:
        print('Ваши ответы противоречивы. прощайте.')
        return None

    print(f'число находится в диапазоне [{min}, {max}].')    
    print(f'попытка {depth} / {maxdepth}')

    support = (min + max) // 2
    result = check(support)
    if result == 'меньше':
        return binsearch(support+1, max, check, depth=depth+1, maxdepth=maxdepth)
    if result == 'больше':
        return binsearch(min, support-1, check, depth=depth+1, maxdepth=maxdepth)
    return support

def guess():
    print('возможные ответы: 1 - равно, 2 - загаданое число больше, 3 - загаданое число меньше ')
    answers = {
        '1' : 'равно',
        '2' : 'меньше',
        '3' : 'больше'
    }
    def check(req):
        answer = ''
        while answer not in answers.keys():
            answer = input(f'это {req}? :')
            if answer not in answers.keys():
                print('ответ не распознан. попробуем ещё раз')
        return answers[answer]
    return check


result = binsearch(1, 100, guess())
if result is not None:
    print('результат -', result)

а вот утверждение, что вы собираетесь переписать решение рекурсивное без функций... интересно. не помню, чтобы нам даже на первом курсе давали такие задачи (хотя заучке вроде меня всё было очевидно ещё в классе восьмом)

[antares4045]

nihi1ist,
конструкция
if req == num else 'меньше' if req < num else 'больше'
это два тернарных оператора
https://pythonim.ru/osnovy/ternarnyy-operator-python

[antares4045]

nihi1ist, хотя, справедливости ради, без рекурсии получилось чище

import math

min = 1
max = 100
maxdepth = math.ceil(math.log(max-min + 1, 2))

print('возможные ответы: 1 - равно, 2 - загаданое число больше, 3 - загаданое число меньше ')

result = None
round  = 1

while result is None and round <= maxdepth:
    print(f'число находится в диапазоне [{min}, {max}].')    
    print(f'попытка {round} / {maxdepth}')

    round += 1
    support = (min + max) // 2

    answer = ''
    while answer not in { '1', '2', '3' }:
        answer = input(f'это {support}? :')
        if answer not in { '1', '2', '3' }:
            print('ответ не распознан. попробуем ещё раз')

    if answer == '2':
        min = support + 1
    if answer == '3':
        max = support - 1
    if answer == '1':
        result = support


if result is not None:
    print('результат -', result)

надо заняться чем-нибудь полезным ;(

Answer 2

[lirostin]

nihi1ist советую для закрепления материала порешать легкие задачки на leetcode. Вот раздел с задачами на бинарный поиск: https://leetcode.com/tag/binary-search/ ; )
Вы же поняли из примера решения как его реализовывать? Сможете написать решение задачи:
Дан массив arr и число K. Необходимо вывести True если число есть в массиве или вывести False если его нет.
Примеры:
Input:
K = 6
arr = [1,2,3,4,6]
Output: True

Input:
K = 2
arr = [1,3,4,5,6]
Output: False