Bogosort优化，概率相关
我正在编写一个关于在线法官的问题以供练习。问题是关于优化 Bogosort 的，并且涉及不要每次都对整个数字范围进行洗牌。如果在最后一次洗牌之后，几个第一个元素最终出现在正确的位置，我们将修复它们并且不再洗牌这些元素。如果最后的元素位于正确的位置，我们将对它们执行相同的操作。例如，如果初始序列是 (3, 5, 1, 6, 4, 2)，经过一次洗牌后 Johnny 得到 (1, 2, 5, 4, 3, 6)，他将修复 1, 2 和 6 并继续使用相同的算法进行排序 (5, 4, 3)。 对于每个测试用例，输出改进算法所需的预期洗牌量，以不可约分数的形式对前 n 个自然数的序列进行排序。
示例输入/输出表明，对于 n=6，答案是 1826/189。
我不太明白答案是如何得出的。
I'm coding a question on an online judge for practice . The question is regarding optimizing Bogosort and involves not shuffling the entire number range every time. If after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle Johnny gets (1, 2, 5, 4, 3, 6) he will fix 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm.
For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions.
A sample input/output says that for n=6, the answer is 1826/189.
I don't quite understand how the answer was arrived at.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这看起来类似于 2011 Google Code Jam，预赛，第 4 题，但答案是 n，我不知道你是如何得到 1826/189 的。
This looks similar to 2011 Google Code Jam, Preliminary Round, Problem 4, however the answer is n, I don't know how you get 1826/189.