编程题：年会抽奖（错排算法）

阳光穿透心脏的1/2处 2023-07-12 03:54 2阅读 0赞

### 文章目录 ###

*   *  问题描述：
     *  解题思路：
     *  解题代码：

链接： [年会抽奖][Link 1]  
来源：牛客网

## 问题描述： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]

## 解题思路： ##

解这个题的时候，我们应该先明白：**什么时候算都不获奖？全部不获奖的概率又该怎么计算？**

全部不获奖的概率=N个人都拿错的情况/所有人的排列情况数
    而所有人的排列情况数=N！（第一个人有N种情况，第二个有N-1种，直到最后一个人）

N个人都拿错的情况和这个题：[发邮件][Link 2] 的情况是一样的。

假设a的名字没有被a拿到，除他之外的N-1个人都有可能拿到，即有N-1种情况。 假设b这个时候拿到了a的名字，那么对于b的名字有两种情况：
      第一种：b的名字是被a拿到了，也就是a和b互相拿到了对方的名字，那么对于其他的N-1个人来说互相拿错又是一个子问题f(n-2) ;
      第二种：b的名字没有被a拿到，则剩下的问题是子问题 f(n-1).
      
    因此：可以得出递推公式：f(n)=(n-1)*(f(n-1)+f(n-2))

## 解题代码： ##

import java.util.Scanner;
    
    public class Main { 
        public static void main(String[] args) { 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                 int n=sc.nextInt();
                 double sum1=factorial(n);
                 double sum2=count(n);
                 double result=(sum2/sum1)*100; //计算成%的形式
                System.out.println(String.format("%.2f",result)+"%");
            }
        }
        //计算所有人都抽不到奖的情况：错排算法
        private static double count(int n) { 
          if(n==1){ 
              return 0;
          }else if(n==2){ 
              return 1;
          }else { 
              return (n-1)*(count(n-1)+count(n-2));
          }
        }
    
        //计算阶乘：迭代写法
        private static double factorial(int n) { 
            double sum=1;
            while(n>1){ 
               sum=sum*n;
               n--;
            }
            return sum;
        }
        //计算阶乘：递归写法
        private  static double factorical2(int n){ 
           if(n==0||n==1){ 
               return 1;
           }
           return n*factorical2(n-1);
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/610e6c0387a0401fb96675f58cda8559?toCommentId=25418
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306224548754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4,size_16,color_FFFFFF,t_70
[Link 2]: https://blog.csdn.net/qq_44840148/article/details/104723196