Python 3.x Угадывание коротких номеров памяти (Программирование / Математика)

Question

(Это может быть как проблема программирования, так и математическая проблема, но публиковать здесь сначала.)

Я создал простую программу, которая играет в угадайку между компьютером и самим собой.Он генерирует число от 0 до 100 включительно, а затем получает догадки от другой функции.Программа работает, но очень неточна, потому что функция угадывания знает только последнее предположение, и должно ли оно угадываться выше или ниже.(Прямо сейчас он просто рандомизирует int между последним предположением и самой низкой / самой высокой границей.)

Самое простое решение было бы с if-else, но я бы предпочел решение с как можно меньшим количеством условных выражений.

Интересно, есть ли способ заставить функцию угадывания постепенно сужать ширину своего угадывания, когда он знает только свое последнее предположение, должен ли он угадывать выше или ниже и максимальные и минимальные границы предположения?

Текущий код:

import random as rnd
def guess_me_computer(number = None, guess = 50, turns = 0, memory = []): 
    """Guessing game between two computers.

    Args:
        number: Number to be guessed
        guess: Guess made by computer
        turns: How many guesses made so far
        memory: List storing how many turns each run takes
    """
    turns += 1

    if number == None:
        number = rnd.randint(0, 100)

    if guess == number:
        print("Correct! My number: {number} was guessed in {turns} tries!".format(number = number, turns = turns))
        memory.append(turns) #Memory used in another testing function
        return None
    elif guess < number:
        print("Wrong! Guess Higher!")
        guess_me_computer(number = number, guess = guesser_computer(last_guess = guess, higher = True), turns = turns, memory = memory)
    else:
        print("Wrong! Guess Lower!")
        guess_me_computer(number = number, guess = guesser_computer(last_guess = guess, higher = False), turns = turns, memory = memory)


def guesser_computer(last_guess = None, higher = None):
    if higher:
        return rnd.randint(last_guess, 100)
    else:
        return rnd.randint(0, last_guess)

Любые вопросы о самом вопросе и / или критике в отношении написания приветствуются.

Answer 1

Хотя это не большая проблема для изучения рекурсии, это может быть интересной проблемой для изучения генераторов, особенно их метода .send().Приведенный ниже генератор все еще знает только последнее сделанное предположение, но также получает подсказку от программы, вызывающей его, было ли это предположение слишком высоким или слишком низким:

from random import randint

def guess_me_computer(guesser):
    number = randint(1, 100)
    tries = 1
    too_low = None
    guess = next(guesser)

    while True:
        if guess == number:
            print("Number: {} guessed in {} tr{}!".format(number, tries, ["ies", "y"][tries == 1]))
            return

        if guess < number:
            print("Wrong! {} is too low! Guess Higher!".format(guess))
            too_low = True
        else:
            print("Wrong! {} is too high! Guess Lower!".format(guess))
            too_low = False

        tries += 1
        guess = guesser.send(too_low)

def guesser_computer(minimum=1, maximum=100):
    while True:
        guess = randint(minimum, maximum)
        higher = yield guess

        if higher:
            minimum = guess + 1
        else:
            maximum = guess - 1

generator = guesser_computer()
guess_me_computer(generator)

Answer 2

Я думаю, что это хорошее упражнение для меня, поэтому я попробовал бинарный поиск.Это интересно.(Встроенные комментарии используются в качестве объяснения кода.)

import random
import numpy as np

max_iters = 10000  #maximum iterations to calculate mean and standard variation of trials
min_num = 0  # a game to guess a random number ranging [0, 100]
max_num = 100
memory = []  # to store the number of turns for each game
numbers_for_guess = [random.randint(min_num, max_num) for i in range(max_iters)]
n_iters = 0  # counter for number of iterations
turns = 0  # counter for number of turns for each game
while n_iters < max_iters:
    # Use binary search
    guess_min = 0  # lower bound for the next guess
    guess_max =  max_num  # upper bound for the next guess
    guess = random.randint(min_num, max_num)  # start from a random number
    while True:
        turns += 1
        if guess == numbers_for_guess[n_iters]:
            memory.append(turns)
            turns = 0
            break
        else:
            if guess > numbers_for_guess[n_iters]:
                guess_max = guess  # narrow down the range for making the next guess
                guess = round((guess + guess_min) / 2, 0)
            else:
                guess_min = guess  # narrow down the range for making the next guess
                guess = round((guess + guess_max) / 2, 0)
    n_iters += 1

print(f'The computer needs {np.mean(memory):.2f} +/- {np.std(memory):.2f} turns to guess the correct number.')

Это выводит:

The computer needs 6.09 +/- 1.48 turns to guess the correct number.