📑打牌 ： da pai ge的个人主页
🌤️个人专栏 ： da pai ge的博客专栏
☁️宝剑锋从磨砺出，梅花香自苦寒来
目录
☁️题目解析
☁️解题思路
☁️示例代码
☁️题目解析
错排问题举例：
用
A
、
B
、
C……
表示写着ｎ位友人名字的信封，
a
、
b
、
c……
表示ｎ份相应的写好的信纸。把错装的总数为记作
D(n)
。假设把
ａ错装进Ｂ里了
，包含着这个错误的一切错装法分两类：
b
装入Ａ里，这时每种错装的其余部分都与
A
、
B
、
a
、
b
无关，应有
D(n
－
2)
种错装法。
ｂ装入
A
、
B
之外的一个信封，这时的装信工作实际是把（除
a
之外的）
n
－
1
份信纸ｂ、ｃ
……
装入（除
B
以外
的）
n
－
1
个信封
A
、
C……
，显然这时装错的方法有
D(n
－
1)
种。
总之在ａ装入
B
的错误之下，共有错装法
D(n
－
2)
＋
D(n
－
1)
种。
a
装入
C
，装入
D……
的
n
－
2
种错误之下，同样都有
D(n
－
1)
＋
D(n
－
2)
种错装法，因此
D(n)
＝
(n
－
1)[D(n
－
1)
＋
D(n
－
2)]
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，
D(1) = 0, D(2) = 1.
☁️解题思路
错排的递推公式是：
D(n) = (n - 1) [D(n - 2) + D(n - 1)]
，也就是第
n
项为
n - 1
倍的前两项和。通过这个递推公式可以
得到在总数为
n
的时候，错排的可能性一共有多少种。那么要求错排的概率，我们还需要另一个数值，就是当总数
为
n
的时候，所有的排列组合一共有多少种，那么根据排列组合，肯定是使用
的公式来求，也就是
n
的阶乘。所以结果很简单，就是用公式求出第
n
项的错排种类，和
n
的阶乘，然后两者一除，
就是概率了。
☁️示例代码
import java.util.*;
public class Main{
public static void main(String[] args){
long d[] = new long[21]; // 错排数据
d[0] = d[1] = 0;
d[2] = 1;
long f[] = new long[21]; // 阶乘
f[0] = f[1] = 1;
f[2] = 2;
// 算N错排数据和阶乘
for(int i = 3; i <= 20; ++i){
d[i] = (i-1) * (d[i-1] + d[i-2]);
f[i] = i * f[i-1];
}
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
System.out.printf("%.2f%%\n", 100.0*d[n]/f[n]);
}
