作者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