一、题目描述
今年公司年会的奖品特别给力，但获奖的规矩却很奇葩：
首先，所有人员都将一张写有自己名字的字条放入抽奖箱中；待所有字条加入完毕，每人从箱中取一个字条；如果抽到的字条上写的就是自己的名字，那么“恭喜你，中奖了！” 现在告诉你参加晚会的人数，请你计算有多少概率会出现无人获奖？二、思路分析
对于什么时候才算做都不获奖，当然是所有人都拿到了别人的名字，没有拿到自己的名字。全部都不获奖的概率必定是由 n个人都拿错的情况种数 除 n个人拿出的所有排列情况数。n个人拿出的所有排列情况数显然是n的阶乘。
假设a的名字没有被a拿到，其他n - 1个人都有可能拿到，即有n - 1种情况。假设b拿到了a的名字，那么对于b的名字有两种情况， 第一种是b的名字被a拿到了，也就是a、b互相拿到了对方的名字，那么对于其他n - 2个人互相拿错又是一个子问题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 ret = count(n)/fac(n); System.out.printf("%.2f", 100 * ret); System.out.println("%"); } } //计算无人获奖组的个数，得到分母 public static double count(int n) { if(n==1){ //n=1的时候返回0 return 0; } if(n==2) { //n=2的时候返回1 return 1; } //递归。 return (n-1)*(count(n-1)+count(n-2)); } //下面的函数用来求阶乘，得到分母 public static double fac(int n){ if(n==0){ //0的阶乘等于1，不用多说吧 return 1; }else{ //阶乘表示，进行递归 return n*fac(n-1); } } }