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