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)
今天的文章错排问题Dn = (n – 1) * (Dn-1 + Dn-2)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/7583.html