1

我写了一个简单的猜谜游戏和猜猜它的方法......

    from gasp import *

    number = random_between(1, 1000)
    guesses = 0

    while True:
        guess = input("Guess the number between 1 and 1000: ")
        guesses += 1
        if guess > number:
            print "Too high!"
        elif guess < number:
            print "Too low!"
        else:
            print "\n\nCongratulations, you got it in %d guesses!\n\n" % guesses
            break

现在根据问题，如果使用正确的策略，最大猜测数应该等于 11。我使用二进制搜索来获得正确的数字，但猜测的数量永远不会超过 10。为了检查我做了以下它产生了一个非终止循环。

    from gasp import *


    guesses = 0
    big = 1000
    small = 1
    while guesses != 11
        number = random_between(1, 1000)
        while True:
            guess = (big + small) / 2
            guesses += 1
            if guess > number:
                print "Too high!"
                big = guess
            elif guess < number:
                print "Too low!"
                small = guess
            else:
                print "\n\nCongratulations, you got it in %d guesses!\n\n" % guesses
                break

那么谁是对的，我犯了一些错误，或者所需的猜测次数不能超过 10 次，并且问题是错误的。

4

2 回答 2

2 
>>> from math import log, ceil
>>> ceil(log(1000, 2))
10.0
于 2013-03-23T12:44:39.957 回答
1

让我们来看看：

A number between 1 and  1 requires 1 guess
A number between 1 and  3 requires 2 guesses at most
A number between 1 and  7 requires 3 guesses at most
A number between 1 and 15 requires 4 guesses at most
A number between 1 and 31 requires 5 guesses at most
...

换句话说，n猜测足以涵盖从1到的范围(2**n)-1。

因为n=10，这个范围是从1到1023。因为1023 >= 1000，你关于十个猜测的结论是正确的。

也就是说，你用来验证这个结论的代码是错误的，因为它无法重新初始化big，small并且guesses每当你移动到下一个数字时。此外，您可以只测试 1 到 1000 之间的每个数字，并使用有限运行时间的确定性算法，而不是随机生成数字。

于 2013-03-23T11:43:51.890 回答