二进制搜索猜谜游戏

Question

我正在尝试创建一个小程序，该程序使用二进制搜索算法让计算机自己猜测给定一组参数的数字。

函数接受的参数是它必须猜测的数量 'tries' 以及它可以猜测的值（例如，5 尝试猜测 0 到 10 之间的数字）。

当我运行我的代码时，它似乎只运行我的 else: 语句，不管我传入的参数如何。

我在“if”语句中遗漏了一些东西，但我很困惑，无法弄清楚我做错了什么。

非常感谢您的宝贵时间和帮助！

import random

def guess_random_number_binary(tries, start, stop):
    
    rand_number = random.randint(start,stop)
    num_list = range(start,stop)

    lower_bound = start
    upper_bound = len(str(stop)) - 1
    
    while lower_bound <= upper_bound:
        pivot = (lower_bound + upper_bound) // 2
        pivot_value = num_list[pivot]
    
        if pivot_value == rand_number and tries > 0:
            print("Found it! " + str(rand_number))
            return pivot
        if pivot_value > rand_number and tries > 0:
            upper_bound = pivot - 1
            tries -= 1
            print ("incorrect guess" + str(tries) + " Remaining")
        else:
            lower_bound = pivot + 1
            print("Out of tries")
            return


guess_random_number_binary(5, 0 ,10)

更新：

import random

def guess_random_number_binary(tries, start, stop):
    
    rand_number = random.randint(start,stop)    
    num_list = []

    lower_bound = start
    upper_bound = stop
    
    num_list = range(start,stop+1)
     
    while lower_bound <= upper_bound:
                
        pivot = (lower_bound + upper_bound) // 2
        pivot_value = num_list[pivot]

        if tries > 0:
            if pivot_value == rand_number:
                print("Found it! " + str(rand_number))
                return pivot
            elif pivot_value > rand_number:
                upper_bound = pivot - 1
                tries -= 1
                print ("Guessed " + str(pivot) + " incorrectly \n" +  str(tries) + " Tries remaining")
            elif pivot_value < rand_number:
                lower_bound = pivot + 1
                tries -= 1
                print ("Guessed " + str(pivot) + " incorrectly \n" +  str(tries) + " Tries remaining")
        else:
            print ("Ran out of tries!")
            break


guess_random_number_binary(5, 20 ,30)

我一直在尝试调试，即使我的新代码过于简化，我希望它至少朝着正确的方向前进。

我认为主要问题在于我如何创建“num_list”，正如下面的答案所指出的那样。收到 IndexError，这在理论上是有意义的。但是，我似乎找不到创建该列表的替代方法。

再次感谢。

Answer 1

您要在每个循环开始时重置 pivot 的值，因此

您为 stop 传入了值 10。所以在行 upper_bound = len(str(stop)) - 1,

upper_bound = len(str(stop))-1 = len(str(10) = len ('10')-1 = 1.

您的 while 循环永远不会运行，因为 lower_bound 永远不会小于 upper_bound。

你可能在某个时候打算做 upper_bound = len(num_list)-1 而不知何故写了 upper_bound = len(str(stop)) - 1。然而，即使那样也不正确； range(start,stop)的长度是stop-start，不是stop-start+1（range不包括stop）。首先使用 range 会造成不必要的混淆，并且不适用于更大的 start 值。例如，假设 (start, stop) = (20, 30)。那么pivot就是25。但是range对象只有10个元素，所以num_range[pivot]会return出错。

二进制搜索猜谜游戏

Binary Search Guessing Game

python

algorithm

binary-search