← 完整题目索引

PROJECT EULER · #0863

不同的骰子

Different Dice

仅题目 · 待解原题 ↗

仅使用六面公平骰子和五面公平骰子,我们想模拟 n 面公平骰子。

例如,模拟 28 面骰子的一种方法是遵循以下过程:

  1. 掷两个骰子,获得整数 1≤p≤6 和 1≤q≤5。
  2. 使用 r=5(p−1)+q 将它们组合起来以获得整数 1≤r≤30。
  3. 如果 r≤28,则返回值 r 并停止。
  4. 否则(r 为 29 或 30),再次掷骰子,获得整数 1≤s≤6 和 1≤t≤5。
  5. 计算 u=30(r−29)+5(s−1)+t 以获得整数 1≤u≤60。
  6. 如果 u>4,则返回值 ((u−5)mod28)+1 并停止。
  7. 否则(1≤u≤4),掷两次六面骰子,获得整数 1≤v≤6 和 1≤w≤6。
  8. 计算 x=36(u−1)+6(v−1)+w 以获得整数 1≤x≤144。
  9. 如果 x>4,则返回值 ((x−5)mod28)+1 并停止。
  10. 否则(使用 1≤x≤4),分配 u:=x 并返回到步骤 7。

按照此过程,预计掷骰子的次数为 2.142476(四舍五入到小数点后 6 位)。请注意,同时掷两个骰子仍算作两次骰子掷。

还有其他更复杂的程序来模拟 28 面骰子,需要较少的平均骰子掷数。然而,上述过程有一个吸引人的特性,即掷骰子的顺序是预先确定的:无论结果如何,它都遵循(D5,D6,D5,D6,D6,D6,D6,...),在过程停止的地方被截断。事实上,在具有此限制的 n=28 的程序中,就最小化所需的预期卷数而言,此程序是最佳的。

n 的不同值通常将使用不同的预定序列。例如,对于 n=8,序列 (D5,D5,D5,...) 给出最佳过程,平均掷骰子 2.083333... 次。

将 R(n) 定义为仅使用五面和六面骰子模拟 n 面骰子的最佳程序的预期骰子投掷次数,仅考虑骰子投掷顺序预先确定的程序。因此,R(8)≈2.083333 和 R(28)≈2.142476。

设 S(n)=∑k=2nR(k)。已知 S(30)≈56.054622。

查找 S(1000)。将您的答案四舍五入到小数点后 6 位。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。