推 EdisonX: 原題意有提到，一起來的朋友不會拆桌，如果全都是三人或 05/19 21:17
→ EdisonX: 四人一起來，那這飯局就不用開桌了。 05/19 21:17
→ gohomexx: 對啊,同一群人是不會拆桌的.所以來三個人就要再等另一組 06/17 10:48
→ gohomexx: 兩個人的,不然只能一直等下去了. 06/17 10:48
這個問題蠻好玩的。
假設平均等待時間以客人組為單位，例如第一組客人來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