如何用Python基于分治算法实现电脑猜测用户所想数字功能

原代码核心问题 #

• 没有动态更新猜测区间的高低边界，每次固定取highest/2作为猜测值，完全没有用到分治缩小范围的核心逻辑
• 定义了first_guess、second_guess等无意义的临时变量，没有复用边界值做计算
• 用普通除法得到浮点数猜测值，和整数目标值对比存在逻辑隐患，应该用整数除法避免浮点数误差

正确实现代码 #

highest = int(input("Enter the highest value you want me to guess: "))
lowest = 0
my_num = 42
game = True

while game:
    # 分治核心：每次取当前猜测区间的中间值作为猜测结果
    computer_guess = (lowest + highest) // 2
    print("My num: ", my_num)
    print("Computer Guess: ", computer_guess)
    
    if computer_guess > my_num:
        print("Computer guess is higher!")
        # 猜高了就把区间上边界调整为当前猜测值减1，缩小后续猜测范围
        highest = computer_guess - 1
    elif computer_guess < my_num:
        print("Computer guess is lower!")
        # 猜低了就把区间下边界调整为当前猜测值加1，缩小后续猜测范围
        lowest = computer_guess + 1
    else:
        print("Computer got it!")
        game = False

实现逻辑说明 #

二分猜数字是分治思想的典型落地，每次猜测后都把猜测范围缩小为原来的一半，最多只需要log2(最大值)次就可以猜对数字，比如最大值设为100时，最多只需要7次就能猜中目标值。

内容的提问来源于stack exchange，提问作者Joy Boy