← 完整题目索引

PROJECT EULER · #0595

增量随机排序

Incremental Random Sort

仅题目 · 待解原题 ↗

一副编号从 1n 的牌被随机洗牌,以便每个排列的可能性相同。

将使用以下技术将卡片按升序排序:

  1. 查看卡片的初始序列。 如果已经排序,则无需执行进一步操作。 否则,如果卡片的任何子序列恰好位于相对于彼此的正确位置(无间隙地升序),则通过将卡片连接在一起来固定这些子序列。 例如,对于最初顺序为 4123756 的 7 卡,标记为 1、2 和 3 的卡将连接在一起,标记为 5 和 6 的卡也将连接在一起。
  1. 通过将卡片扔到空中,卡片会被"洗牌",但请注意,任何顺序正确的卡片仍会保持连接状态,因此它们的顺序会保持不变。 然后随机拾取卡片(或附加卡片束)。 您应该假设这种随机化是无偏见的,尽管事实上有些卡片是单一的,而其他卡片则分组在一起。
  1. 重复步骤 1 和 2,直到卡片排序完毕。

S(n) 为对纸牌进行排序所需的预期洗牌次数。由于在第一次洗牌之前检查顺序,S(1)=0。您将获得 S(2)=1S(5)=4213/871

找到 S(52),并将答案四舍五入到 8 小数位。

题解待补充

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