找到一個隨機數的算法

我試圖找到使用最少步數找到1-100之間的一個隨機數的最佳算法。您可以使用函數guess(n)來猜測數字n，並且您將收到布爾響應true或false。如果答案是錯誤的，答案將總是小於您輸入函數的猜測;如果答案是真的，那麼它需要更大或者猜測本身。找到一個隨機數的算法

2011-05-22 locoboy

你是什麼意思查找？你如何確定哪一半是不相關的？ – Howard 2011-05-22 10:23:14

你的意思是binarysearch？ http://en.wikipedia.org/wiki/Binary_search_algorithm – 2011-05-22 10:26:20

@howard，這樣你就可以知道它是不是在某一點的數字，它總是會是答案將少於猜測的數字。請參閱上面的編輯。 – locoboy 2011-05-22 10:27:41

基本思路：

先猜（50）。根據答案，猜（25）或猜（75）。

2011-05-22 10:39:45

如果你可以判斷你的猜測是大於還是小於隨機數，那麼Binary Search是你的朋友。如果只能告訴數字是否匹配，我會從中間值（50.5）開始交替線性搜索，即從50到1和從51到100（50,51,49,52 ...）。

2011-05-22 10:39:51 maro

爲什麼這會比從1開始並增加1更好？在任何一種方法中，99（或100，取決於）將是最糟糕的「正確」猜測。 – Marvo 2011-05-22 10:42:09

@Marvo，出於某種原因，我假定正常分配值，寫出答案。鑑於大多數隨機發電機產生均勻分佈，你是對的。 – maro 2011-05-22 10:54:34

我不完全確定我理解這個問題，所以誰知道？ =） – Marvo 2011-05-22 11:00:31

回答