错排问题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题目——年会抽奖

题目描述：

链接：年会抽奖__牛客网
来源：牛客网
 

今年公司年会的奖品特别给力，但获奖的规矩却很奇葩：
1. 首先，所有人员都将一张写有自己名字的字条放入抽奖箱中；
2. 待所有字条加入完毕，每人从箱中取一个字条；
3. 如果抽到的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
现在告诉你参加晚会的人数，请你计算有多少概率会出现无人获奖？

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)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！