執行二進制搜索猜一個隨機數，但不能匹配

我寫了一個簡單的猜謎遊戲，並猜測它的方法猜測的數...執行二進制搜索猜一個隨機數，但不能匹配

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個，問題是錯誤的。

來源

2013-03-23 user2189524

您應該使用'int（raw_input（...））'而不是'input（...）'。 Python 2.x中的'input（）'函數是不安全的，請避免它。（在Python 3.x中，它是安全的。） – 2013-03-23 11:53:23

@DietrichEpp是的，關於以前由OP做出的評論，輸入不僅僅是整數，它可以用任何python代碼來評估當然是危險的 – jamylak 2013-03-23 12:17:50

讓我們來看看：

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-23 11:43:51 NPE

>>> from math import log, ceil 
>>> ceil(log(1000, 2)) 
10.0

來源

2013-03-23 12:44:39 jamylak

執行二進制搜索猜一個隨機數，但不能匹配

回答

相關問題