发邮件：错排问题的分析

提出问题：有一天，有五个人各自收到了一封信，每个人的家门前都有一个自己的信箱，可是送信员在送信的时候恰好把每个人的信都送到了别人家的信箱里，问：满足这样送信方案数共有多少种？

• 分析问题

当n个编号元素放在n个编号位置，错排的方法数记着D(n)～

⒈把第n个元素放在一个位置，比如位置k，一共有（n-1）种方法；

⒉放编号为k的元素，这时有两种情况：
1°把它放到位置n，那么，对于剩下的（n-1）个元素，由于第k个元素放到了位置n，剩下（n-2）个元素就有D(n-2)种方法；
2°第k个元素不把它放到位置n，这时，对于这（n-1）个元素，有D(n-1)种方法；.

于是有：
D(n) = (n-1) [D(n-2) + D(n-1)]

• 解决问题

我们以发邮件这个相同的问题来举例，根据以上分析，我们可得到以下代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            long sum = count(n);
            System.out.println(sum);
        }

    }

    //计算所有人都收不到自己的邮件的情况情况：错排算法
    private static long count(int n) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return (n - 1) * (count(n - 1) + count(n - 2));
        }
    }
}