前言

牛客网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有以下两种分法：

1. b装入A中，这样剩下的（n-2）份信和信封A、B，和信a、b就没有任何关系了，所以这时候装错的可能性总共有D(n-2)。
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]);
            }
        }
    }
}