错排问题Dn = (n - 1) * (Dn-1 + Dn-2)

1.什么是错排问题？

我们知道，n个有序的元素，应当由n!种排列方式，如若一个排列使所有元素都不在原来的位置上，则这个排列就称为错排，也可称为重排。

如：1         2         3

错排有两种：

2 3 1

3 1 2

2.递推关系Dn = (n - 1) * (Dn-1 + Dn-2)

大概推导过程如下：

Dn就表示n个元素错排的方法数

第一步：

考虑第n个元素，把它放在除原位置以外的任意位置k,一共有n-1种选择

第二步：

如果选择放在位置k，则第k个元素需要更改位置，第k个元素整体上有两大类选择：

• 选择放在第n个位置，则剩下的n-2个元素再错排
• 选择放在除n除k外的其他任意位置，则相当于n-1个元素错排

综上，Dn = (n - 1) * (Dn-1 + Dn-2)

3.根据递推关系递归求解

3.1题目——年会抽奖

题目描述：

链接：
来源：牛客网
 

3.2递归解法 

import java.util.Scanner;

/**
 * 年会抽奖——错排问题
 *递推公式——Dn = (n - 1) * (Dn-1 + Dn-2)
 * @author sunny
 * @date 2022/06/03 08:57
 **/
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()){
            int n = scanner.nextInt();
            double res = 0;
//            先计算分母
            double a = calcuA(n);
//            再计算分子
            double b = calcuB(n);
            res = (b/a) * 100;
            System.out.printf("%.2f%%\n",res);
        }
    }
//    计算阶乘求分母
    private static double calcuA(int n){
        double ans = 1;
        while(n != 1){
            ans *= n;
            n --;
        }
        return ans;
    }
//    根据递推公式求分子
    private static double calcuB(int n){
        if(n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        return (n - 1) * (calcuB(n - 1) + calcuB(n - 2));
    }
}

最后，再记一遍，Dn = (n - 1) * (Dn-1 + Dn-2)