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

错排问题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)

错排问题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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注