← 完整题目索引

PROJECT EULER · #0367

博佐排序

Bozo Sort

仅题目 · 待解原题 ↗

Bozo 排序,不要与效率稍低的 bogo 排序混淆,它包括检查输入序列是否已排序,如果没有则随机交换两个元素。重复此操作,直到最终对序列进行排序。

如果我们将前 4 个自然数的所有排列视为输入,则所有 4! 输入序列的平均交换次数的期望值为 24.75
已经排好序的序列需要 0 步。

在这个问题中,我们考虑以下 bozo 排序的变体。
如果序列不按顺序排列,我们随机选择三个元素并随机打乱这三个元素。
这三个元素的所有 3!=6 排列的可能性相同。
已排序的序列将需要 0 步。
如果我们将前 4 个自然数的所有排列视为输入,则所有 4! 输入序列的平均洗牌次数期望值为 27.5
将前 11 个自然数的排列视为输入序列。
对所有 11! 输入序列进行平均,该排序算法将执行的预期洗牌次数是多少?

请将答案四舍五入到最接近的整数。

题解待补充

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