Re: [問題] 一個很像binary search的演算法， …
看板Prob_Solve (計算數學 Problem Solving)作者Hatred (yo)時間14年前 (2010/05/28 21:42)推噓3(3推 0噓 7→)留言10則, 4人參與討論串2/3 (看更多)
※ 引述《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
推
05/29 05:19, , 1F
05/29 05:19, 1F
→
05/29 05:19, , 2F
05/29 05:19, 2F
→
05/29 05:19, , 3F
05/29 05:19, 3F
推
05/29 06:49, , 4F
05/29 06:49, 4F
→
05/29 10:01, , 5F
05/29 10:01, 5F
→
05/29 10:03, , 6F
05/29 10:03, 6F
推
05/31 00:18, , 7F
05/31 00:18, 7F
→
05/31 00:20, , 8F
05/31 00:20, 8F
→
05/31 00:20, , 9F
05/31 00:20, 9F
→
05/31 00:21, , 10F
05/31 00:21, 10F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12