[中譯] ProjectEuler 481 Chef Showdown

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者tml (流刑人形)時間11年前 (2014/09/25 21:52)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串1/1

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://www.ptt.cc/bbs/puzzle/M.1411653124.A.604.html