PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 並桌問題

看板Prob_Solve (計算數學 Problem Solving)作者gohomexx (gohomexx)時間8年前 (2016/05/13 18:22)推噓1(1推 0噓 3→)

留言4則, 2人參與討論串3/3 (看更多)

這個問題蠻好玩的。假設平均等待時間以客人組為單位，例如第一組客人來3個，第二組客人來2個，第一組客人等了一組客人，等待組數為 1。第二組客人不用等，等待時間為 0。這種情況下平均等待時間為 (1 + 0) / 2 = 0.5 組客人。我們可以知道極限就是 0.5 ，因為你最快就是兩組人併一桌。如果用一種只容許兩組客人併一桌的演算法呢？客人來就塞著，等到另一組加起來等於 5 的客人來了直接併桌。可以算出設現在來的這組客人為 n 個人，來另一組剛好併桌的機率為 1/4 * 0.5 (平均等待時間為 0.5 組客人) + 3/4 * 1/4 * 1 (一組沒中一組中，沒中的不論，平均等待時間為 2 + 0 = 1) + 3/4 ^ 2 (平方) * 1/4 * 1.5 （二組沒中，第三組中） + 3/4 ^ 3 (立方) * 1/4 * 2　（三組沒中，第四組中） + ... 這個數例我不會算，用 java 跑到 1000 結果收斂在 2。亦即不管現在來幾個人，等到剛好可以併桌需要平均等 2 組，這個值很有趣！理論上的最佳演算法會讓平均等待客人組數落在等 0.5 組 ~ 2 組之間。但實際上不是這樣的，假設你容許塞好塞滿好了。現在併著等開桌的人不管是多少人(小於5人），等到下一組剛好可以併桌的平均等待組數是 2 。但併好桌的人有分先後，所以其實平均待待組數要比 2 大。所以 2 可能也是演算法的最佳解，我時間不夠趕著下班接小孩，只能先分享到這個地方。請大家多多指教。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.51.201.213 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1463134924.A.0E4.html