作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 503 Compromise or persist
时间Tue Mar 3 01:01:20 2015
503. Compromise or persist
https://projecteuler.net/problem=503
Alice用编号1到n的牌进行一个游戏。
这个游戏会反覆进行如下步骤：
(1) Alice随机抽出其中一张牌。
(2) Alice无法看到牌上的数字。取而代之，她的朋友Bob看了牌上的数字後，
会告诉Alice之前看过的所有牌中，比现在的数字还大的张数。
(3) Alice可以选择继续下一轮或结束游戏。如果她选择结束，她最後抽出的牌
即为她的得分。如果她选择继续，则这张牌会从牌堆中被移除，然後她再次
进行步骤(1)。但如果牌堆中已经没牌了，她只能选择结束游戏。
令F(n)为Alice运用让自己得分最小的策略下，得分的期望值。
例如，F(3) = 5/3。在第一回合，她选择继续游戏。在第二回合，如果Bob告诉她
有一张牌比现在的数字大，则她选择结束，否则就继续。
亦能验证F(4) = 15/8以及F(10) ≒ 2.5579365079。
请求出F(10^6)，并将答案四舍五入至小数後10位。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 206.196.186.174
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/puzzle/M.1425315692.A.D5F.html