[数据结构与算法]第四站鲁南煤城--------发邮件（错排问题）

错排问题
牢记公式

大佬讲解错排问题

一、题目描述
题目链接

二、题目分析

1. 全错排问题
   

2. 设D(n) 表示 n个邮件全错排，（即 A—>a、B ---->b、C---->c…均不会出现），一共有D(n)种可能
   列举其中一种情况
   

3. A —> b、c、e、d…有 (n - 1) 种情况
   所以得到 n个邮件全错排的所有情况的总数是 D(n) = (n-1)*(D(n-1) + D(n-2))

三、解决方法
注意此处因为数据过大，用 long替换 int

import java.util.*;
public class Main{
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            System.out.println(D(n));
        }
    }
    public static long D(int n){
        if(n == 0 || n == 1){
            return 0;
        }
        if(n == 2){
            return 1;
        }
        return (n - 1) * (D(n - 1) + D(n - 2));
    }

}

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 因为 2 <= n <= 20，此处 1下标就是1封邮件  2下标就是2封邮件 3下标就是3封邮件
        long[] D = new long[21];
        D[2] = 1;

        for (int i = 3; i < 21; i++) {
            D[i] = (i - 1) * (D[i-1] + D[i-2]);
        }
        while(scanner.hasNext()){
            int n = scanner.nextInt();
            System.out.println(D[n]);
        }
    }

生态山水名城，运河文化之都，铁道英雄故乡。

山东枣庄

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖