这道题的数学公式是错排公式，也称为derangement formula。 错排公式给出了将 n 个元素全部错排的方案数。记为 D(n) 或 !n。 数学公式为： 其中，n! 表示 n 的阶乘，而 (-1)^n 表示取 n 的符号。 例如，D(3) = 3! * (1/0! - 1/1! + 1/2! - 1/3!) = 3 * (1 - 1 + 1/2 - 1/6) = 3 对于本题来说，如果题目要求求解 n 个人全装错信的方案数，即为 D(n)。 完整代码：

【算法分析】 aia_iai 表示 iii 封信封都装错的方案数，初始化： 初始条件：1封信都装错的方案数为0 a1a_1a1 = 0 2封信都装错的方案数为1 a2a_2a2 = 1 当 iii 大于等于 333，递推式为:a[i]=(i−1)∗(a[i−2]+a[i−1])a[i] = (i - 1) * (a[i - 2] + a[i - 1])a[i]=(i−1)∗(a[i−2]+a[i−1]) 【参考代码】 【时间复杂度】 O(n)O(n)O(n) 【预计得分】 100pts100pts100pts

这是老师上课讲的例题之一，也是一道特典型的递推。 在放代码之前，我们先求出公式： 一封信时结果为000种可能性，两封信时结果为111种，三封信时222种……你可以再多推算几步，得知如果索引从111开始，在减少一封信后，将得出i−1i-1i−1封完全错排的信及最后一封位置正确的信，交换前面的任意一封信和最后一封即可。去掉两封信后同理，最终可得a[i]=(a[i−1]+a[i−2])∗(i−1)a[i]=(a[i-1]+a[i-2])*(i-1)a[i]=(a[i−1]+a[i−2])∗(i−1)，注意接下来我的代码中索引从0开始，因此略有改动。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 不想听的话，注释里也有思路的大致解析，当然肯定没有自己想来的效果。