前言
牛客网PAT乙级训练1020
题目描述
NowCoder每天要给很多人发邮件。有一天他发现发错了邮件，把发给A的邮件发给了B，把发给B的邮件发给了A。于是他就思考，要给n个人发邮件，在每个人仅收到1封邮件的情况下，有多少种情况是所有人都收到了错误的邮件？
即没有人收到属于自己的邮件。
输入描述
输入包含多组数据，每组数据包含一个正整数n（2≤n≤20）。
输出描述
对应每一组数据，输出一个正整数，表示无人收到自己邮件的种数。
输入例子
2
3
输出例子
1
2
解析
这道题是一道典型的错排问题，核心在于递归思想的运用。
用A、B、C、D.........表示写着n位友人名字的信封，a、b、c、d.........表示n份相应的信，把n份信装错的总数记为D(n)，那么n-1份信封装错的总数就是D(n-1)。
现在，假设这样一种情况，把a错装进B中，那么对于信b有以下两种分法：
- b装入A中，这样剩下的（n-2）份信和信封A、B，和信a、b就没有任何关系了，所以这时候装错的可能性总共有D(n-2)。
- b不一定装入A中，那么就有可能装入A、C、D等其余除B之外的信封了，这时总共就是(n-1)种装错的可能性了。
所以对于信b来说，总共有D(n-2)+D(n-1)种装错的可能性。所以最后除a之外还有（n-1）封信，所以最终的关系式如下：
D(n)＝(n－1)*[D(n－1)＋D(n－2)]
解决方案
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
long a[] = new long[n + 1];
a[1] = 0;
a[2] = 1;
if (n==2){
System.out.println(1);
}else {
for (int i = 3; i < n + 1; i++) {
a[i] = (i - 1) * (a[i - 1] + a[i - 2]);
}
System.out.println(a[n]);
}
}
}
}
