481. Chef Showdown https://projecteuler.net/problem=481 一群廚師（編號#1、#2、……）參加了一場回合制的策略型廚藝競賽。在每個廚師的回合 中，他會端出符合其廚藝的最佳料理並將其給評審試吃。令S(k)表示第k個廚師的廚藝值 （此一數值分布為所有人皆知），而廚藝值也代表此廚師做的料理被評審所接受的機率 （此一機率在所有回合均不變）。若一道料理被接受，則其廚師將選擇淘汰一位其他廚師 直到剩下一人為止，此人即為贏家。 此競賽永遠從廚師#1開始，並依序輪流。輪完一輪則再從號碼最小者開始下一輪。所有 廚師都以最佳策略進行競賽以求獲勝，並且也預期其他廚師策略相同。假使對一個廚師 而言有兩個以上的淘汰選項有相同的獲勝機率，則會選擇接著自己之後最先被輪到的。 令W_n(k)為總共n位廚師時第k位的獲勝機率。如果我們假設S(1) = 0.25、S(2) = 0.5及 S(3) = 1，則W_3(1) = 0.29375。 由此開始，對所有1≦k≦n，我們令S(k) = F_k / F_(n+1)，其中F_k為費波那契數列的 第k項，定義為：F_k = F_(k-1) + F_(k-2)以及F_1 = F_2 = 1。舉例而言，假設共有 n = 7位廚師，則W_7(1) = 0.08965042、W_7(2) = 0.20775702、W_7(3) = 0.15291406、 W_7(4) = 0.14554098、W_7(5) = 0.15905291、W_7(6) = 0.10261412以及 W_7(7) = 0.14247050（四捨五入至小數後8位）。 令E(n)表示由n位廚師參與的一場競賽中端出的料理總數的期望值。例如， E(7) = 42.28176050。 請求出E(14)並四捨五入至小數後8位。 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.2.129.153 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/puzzle/M.1411653124.A.604.html