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