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、10 回の推測についてのあなたの結論は正しいです。

とはいえ、この結論を検証するために使用したコードにはバグがあります。再初期化に失敗しbig、small次guessesの番号に進むたびに失敗するからです。また、数値をランダムに生成する代わりに、1 から 1000 までのすべての数値をテストして、実行時間が有限の決定論的アルゴリズムを使用することもできます。

于 2013-03-23T11:43:51.890 に答える