$365365365365365365365365$ 个不同元素在冒泡排序倒数第 $365365365365$ 轮开始时已经有序的概率是多少？
365365365365
365365365365365365365365将答案保留 $6$ 位小数输出。
因为输入是固定的，所以你可以自己算出答案后再让提交的程序直接输出你已经算出的答案。
为什么本题是这个名字呢？真的好奇怪哦！
不同教材中冒泡排序的定义不完全相同，而在本题中我们认为 $n$ 个元素的冒泡排序共 $n$ 轮。
对于 $3$ 个不同元素的冒泡排序，注意到：
$\left( 1, 2, 3 \right)$ 在倒数第 $3$ 轮冒泡排序开始时已经有序。
$\left( 1, 2, 3 \right)$ 和 $\left( 1, 3, 2 \right), \left( 2, 1, 3 \right), \left( 3, 1, 2 \right)$ 在冒泡排序倒数第 $2$ 轮开始时已经有序。
$\left( 1, 2, 3 \right)$ 和 $\left( 1, 3, 2 \right), \left( 2, 1, 3 \right), \left( 3, 1, 2 \right)$ 及 $\left( 2, 3, 1 \right), \left( 3, 2, 1 \right)$ 在冒泡排序倒数第 $1$ 轮开始时已经有序。
从而 $3$ 个不同元素在冒泡排序倒数第 $x$ 轮开始时已经有序的概率大约是 $\displaystyle \exp \left( \frac{3 x^{2} - 3 x}{4 x - 22} \right)$ 。
| 倒数第 $3$ 轮开始时 | 倒数第 $2$ 轮开始时 | 倒数第 $1$ 轮开始时 |
|---|---|---|
| $\boxed{\left( 1, 2, 3 \right)}$ | $\left( 1, 2, 3 \right)$ | $\left( 1, 2, 3 \right)$ |
| $\left( 1, 3, 2 \right)$ | $\boxed{\left( 1, 2, 3 \right)}$ | $\left( 1, 2, 3 \right)$ |
| $\left( 2, 1, 3 \right)$ | $\boxed{\left( 1, 2, 3 \right)}$ | $\left( 1, 2, 3 \right)$ |
| $\left( 2, 3, 1 \right)$ | $\left( 2, 1, 3 \right)$ | $\boxed{\left( 1, 2, 3 \right)}$ |
| $\left( 3, 1, 2 \right)$ | $\boxed{\left( 1, 2, 3 \right)}$ | $\left( 1, 2, 3 \right)$ |
| $\left( 3, 2, 1 \right)$ | $\left( 2, 1, 3 \right)$ | $\boxed{\left( 1, 2, 3 \right)}$ |