作者Hatred (yo)
看板Prob_Solve
標題Re: [問題] 一個很像binary search的演算法， …
時間Fri May 28 21:42:44 2010
※ 引述《mqazz1 (無法顯示)》之銘言：
: suppose that you are go guess the price of a commodity without knowing its price in advance,
: how fast can you guess its price,
: assuming the real price of the commodity is n.
: use less than O(n) comparisons.
: 如果這是運用到binary search的觀念
: 我記得binary search好像是O(logn)
: 那我先從比n大的數開始開始猜
: 之後每次都取它的中間數猜下去..應該就可以在O(n)內猜到
: 可是題目一開始說 不知道商品的價格
: 那應該就沒辦法一開始就先猜到比n大的數..
: 請問這題可以運用到binary search的觀念嗎?
: 那我的想法應該要怎麼改進呢?
: 謝謝
其實我不是很懂題目的意思 :)
我猜 price 應該是一正整數吧 (否則如果是任意實數, 好像會沒辦法找),
可能可以這樣做:
先猜 price 是 1, 看看是剛好/過高/過低, 假設 (例如) 現在是過低好了, 那就猜 2,
假如還是過低, 我們就猜 4, 假設仍然過低, 我們就猜 8, 接著就是 16, 32, ... 一直
跑下去...
這樣一直猜到過高為止, 只猜了 O(log n) 次; 第一次過高時, 所猜的數字應不大於 2n,
所以之後就在 1 到 2n 之間用 binary search 再猜 O(log n) 次得到答案應該就行了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.90.239
1F：推 LPH66:其實不用 1~2n...最後一次如果是 2^k 則在 2^(k-1) 到 2^k 05/29 05:19
2F：→ LPH66:之間二分搜即可 這一段只有 2^(k-1) 個數所以是 O(k) 05/29 05:19
3F：→ LPH66:當然因為 n < 2^k < 2n 所以也是 O(log n) 啦... 05/29 05:19
4F：推 FRAXIS:原題目也沒說會回答 過高/過低 如果只會回答 對/錯 怎解？ 05/29 06:49
5F：→ Hatred:只回答對錯的話, 就不會有 o(n) 的問法囉 :) 05/29 10:01
6F：→ Hatred:不過我不是很確定題目的意思... 05/29 10:03
7F：推 cibs:從 1 問到 n 不就是 O(n) 嗎？ 05/31 00:18
8F：→ Hatred:是的, 不過原題目看起來又有點像要 o(n) (而非 O(n)) 的方 05/31 00:20
9F：→ Hatred:法 (是嗎, 其實我不是很確定, 另外就是每次是不是可以知道 05/31 00:20
10F：→ Hatred:過高/過低 也不確定... 總之題目我看不太懂) 05/31 00:21