神、上帝以及老天爷（62min）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2048

Problem Description

HDU 2006'10 ACM contest的颁奖晚会隆重开始了！
为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：

首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”

大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！

我的神、上帝以及老天爷呀，怎么会这样呢？

不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？

不会算？难道你也想以悲剧结尾？！

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。

Output

对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。

Sample Input

Sample Output

50.00%

题解：

题意：n个人把自己名字写在字条上，放入箱子中，然后每人在从箱子里抽出一个字条，求n个人抽到的字条上面写的名字都不是自己的概率。

方法：全错排方法。

此题全排错推导：D（n）表示n个人都拿错的情况。n个人拿到的名字都不是自己的名字，这里分两种情况：

1.假设第n个人拿到的自己的名字，那么前n-1已经全部错排，此时只需要把第n个人的名字和前面n-1个人的名字交换即是全部错排，这样有n-1种可能，这时 n个人都拿错的情况等于前面n-1个人已经拿错乘以第n个人和前面n-1个人交换的次数，D（n）=D(n-1)*（n-1)。

2.假设第n个人拿的不是自己的名字，那么前面n-1个人肯定有一个人拿着第n个人的名字，那么第n个人可以和除了拿自己名字的那个人，和其他n- 2个人交换纸条即全排错，这时n个人都拿错的情况等于前面n-2个人已经拿错乘以前面n-1个人都有可能拿着第n个人的名字，D（n）=D(n-2)*（n1)。

思路：n个人都拿错名字的概率=每个人都拿错名字的可能性/n个人拿到名字的总可能性。

耗时原因：1.一开始看错题目要求了，以为题目要求求所有人都拿对自己名字的概率，所以浪费了一些时间。

2.自己对全错排使用还不熟练，只是知道了公式，但是用起来还是有些吃力。

3.在最后输出时，保留两位小数，但是java语法和c还是有一点差距，所以上网查了怎么使java最后输出保留两位小数。

看错题代码：

import java.util.Scanner;


public class Main{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner scan=new Scanner(System.in);
            int C=scan.nextInt();
              while(C>0)
              {
                  int n=scan.nextInt();
                  double result;
                  double temp=1.0;
                  for(int i=1;i<=n;i++)
                  {
                     temp*=1.0/i;
                  }      
                  result=temp*100;
               System.out.printf(String.format("%.2f",result));
               System.out.println("%");
              C--; 
       }

    }

}

正确代码：

import java.util.Scanner;


public class test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       Scanner scan=new Scanner(System.in);
            int C=scan.nextInt();
              while(C>0)
              {
                  int n=scan.nextInt();
                  long []result=new long [21];
                  long []quanpai=new long [21];
                  result[0]=0;
                  result[1]=0;
                  result[2]=1;
                  quanpai[0]=1;
                  quanpai[1]=1;
                  quanpai[2]=2;
                  for(int i=3;i<=20;i++)
                  {
                     quanpai[i]=quanpai[i-1]*i;
                     result[i]=(i-1)*(result[i-1]+result[i-2]);
                  }      
                 
               System.out.printf(String.format("%.2f",1.0*result[n]/quanpai[n]*100));
               System.out.println("%");
              C--; 
       }

    }

}

总结：以后再出现这种求错排方法，先写错排公式，然后根据题意对错排公式进行组合。

上一篇：考新郎博客也是使用到了错排公式，博客链接：https://www.cnblogs.com/ping2yingshi/p/12457266.html