作者copa ()
看板CYSH91Y322
标题Re: [问题] 等电梯该等多久呢?
时间Wed Nov 26 23:02:23 2008
※ 引述《copa ()》之铭言：
: 嗨，all
: 昨天听到个题目，请高手解答啊!!!
: 如果你从1f-10f搭电梯要15秒，走楼梯要45秒，你最多等电梯多久就该走楼梯啦???
感谢我同学啦，昨天看到原文了，这题是on-line algorithm中的问题，有修过演算法的
同学会知道，我是不知道啦orz
解法的想法是看待:所花的时间(cost)和最佳解(opt)的比值(competitive ratio)，如果
这个比值愈小愈好罗，不会小於1啦xd
假设两种方法所花的值较小是r(rent)和较大是p(purchase)(因为这题原题是rent or buy)
，这题中搭电梯是r，走楼梯是p，最小的值会是(2-r/p)，这题是5/3，发生在等电梯30秒
电梯没来，就走楼梯啦
证明方法是 competitive ratio = (k*r+p)/min((k+1)*r,p)
if (k+1)*r>=p，ration = ((k+1)*r+p-r)/p >= (p+p-r)/p = 2-r/p
else ratio = ((k+1)*r+p-r)/((k+1)*r) = 1+(p-r)/((k+1)*r) >= 2-r/p
现在题目是先假设等的时间是(30+t)+走楼梯时间45
((30+t)+45)/45>=75/45;
等的时间是(30-t)+走楼梯时间
((30-t)+45)/((30-t)+15)>=75/45
所以啦，不是只看所花的时间哦，是看比值xd
真是高手!
p.s.解法有问题，请痛鞭~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 71.199.96.201
1F：推 kendoo:喔!!原来是这样啊!!(恍然大悟貌) 11/27 00:44
2F：推 Helilo:说实在我不太理解这题怎麽类比到那个式子的 可进一步解释吗 11/27 02:15
※ 编辑: copa 来自: 71.199.96.201 (11/27 02:41)