欧拉298项目 - 必须有正确答案？ （只有pastebinned代码）

Question

Project Euler有一个页面文件问题（尽管它伪装换句话说）。

我根据样本数据测试了my code（为了不伤害任何人），并获得与问题相同的记忆内容+分数。然而，没有一个统一的分数组。它要求在50回合后得分的预期差异。分数的随机抽样：

1.50000000 
1.78000000 
1.64000000 
1.64000000 
1.80000000 
2.02000000 
2.06000000 
1.56000000 
1.66000000 
2.04000000 

我已经尝试了一些那些作为答案，但他们都没有被接受......我知道一些人成功了，所以我真的很困惑 - 我错过了什么？

Answer 1

您的问题可能是您似乎不知道Expected Value的定义。

您将不得不多次运行模拟，并针对每个得分差异，保持该出现的频率，然后采用加权平均值来获得预期值。

当然，鉴于这是欧拉项目问题，可能有一个可以很容易使用的数学公式。

Answer 2

我会运行你的模拟很多次，然后在所有运行中对| L- R |值进行加权平均。这应该让你更接近预期的价值。

只提交一次运行作为答案是不太可能的。想象一下，这是掷骰子的期望值。掷骰子，得分6，提交，如预期的价值。

Answer 3

是的，这是一个正确的答案。说实话，蒙特卡罗在理论上可以接近大数定律的期望值。但是，你不会想在这里尝试。因为实际上每次运行simu时，都会得到一个稍微不同的结果，小数点后8位（我认为这种设置确实剥夺了任何人甚至有想到使用蒙特卡罗的机会）。如果你幸运的话，你将有一个simu在经过大量试验后提供答案，因为你已经提交了所有以前和失败的答案。我认为，captcha是euler项目让你放弃任何暴力方法的第二种方式。

那么，与莫伦一致，你必须先弄清楚“预期值”。这个问题的原理是，你必须找到一种方法，在50轮之后列举每一个可能的“基本”结果。每个结果都有自己的| L-R |，所以总结起来，你会得到答案。不用说，大部分情况下蛮力方法都失败了，特别是在这种情况下。幸运的是，我们有动态编程（dp），这很快！

基本上，dp将每一轮的计算结果保存为状态，并在下一次使用它们。因此它避免了一遍又一遍地重复同样的计算。这个问题的难点在于找到表示状态的方法，也就是说，如何保存临时结果。如果你已经在dp中解决了问题290，那么你可以从中得到一些关于如何理解问题和制定状态的提示。

其实，这不是心灵最困难的部分。最难的思想是，你是否意识到这两名球员的一些记忆状态在数值上是不同的，但基本上是相同的。例如，L：12345 R：12345对L：23456 R：23456或甚至对L：98765 R：98765。这是由于该通话是随机的。这也是我撰写可能的“基本”成果的原因。也就是说，你可以将一些状态归纳为一个状态。只有这样做，你的程序才能在合理的时间内完成。