ProjectEuler 481 Chef Showdown - 拼圖

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位。

--