牛客刷题---年会抽奖

[编程题]年会抽奖

链接：年会抽奖__牛客网
来源：牛客网

今年公司年会的奖品特别给力，但获奖的规矩却很奇葩：
1. 首先，所有人员都将一张写有自己名字的字条放入抽奖箱中；
2. 待所有字条加入完毕，每人从箱中取一个字条；
3. 如果抽到的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
现在告诉你参加晚会的人数，请你计算有多少概率会出现无人获奖？

 解题思路:

阅读题意我们首先要明白”无人获奖的概率“是怎末算出来的，这也是本题的难点。

第一，我们要先找到这个事件的样本容量，也就是一共会出现多少种情况。

第二，需要找到所有人都没有抽到带有自己字条可能出现的所有情况。

第三，计算无人获奖的概率：

样本容量很好找，N个人去抽N个不同的字条，抽一个盒子里就少一个，所以样本容量就等于 N！

有N个不同名字的字条，N个人抽，其中若A没抽中也就是说：A抽到了另外N-1个带有别人名字的字条。那么这个时候就有可能两个情况:

①A抽之后，第二个人B恰好抽到了带有A名字的字条，A也刚好抽到了带有B名字的字条。

这种情况下，相当于A、B后面的N-2个人都没有抽到带有自己字条可能出现的所有情况这一事件是一个新的独立的系统，与前面A和B没有关系。

②A抽之后，第二个人B没有抽到了带有A名字的字条。

这种情况下，相当于A后面的N-1个人都没有抽到带有自己字条可能出现的所有情况这一事件是一个新的独立的系统，与前面A没有关系。

那这样题目的思路就梳理的比较明了了， 相对独立的系统我们可以使用递归的方式来处理

设计一个函数：

getNoOne(int n) 计算都没有抽到带有自己字条可能出现的所用情况，其中遇到的可能的两种情况使用递归解决: return (n - 1) * (getNoOne(n - 1) + getNoOne(n - 2));d代码展示

 代码展示：

 
 
import java.util.Scanner;
 
/**
 * @Author qiqichongya
 * @Date 2022/8/4 19:43
 * @PackageName:Day35_8_4
 * @ClassName: AnnualMeetingLottery
 * @Description: 年会抽奖
 * 
 * 1.首先，所有人员都将一 张写有自己名字的字条放入抽奖箱中;
 * 2.待所有字条加入完毕，每人从箱中取一个字条;
 * 3.如果抽到的字条上写的就是自己的名字，那么“恭喜你，中奖了!”
 * 现在告诉你参加晚会的人数，请你计算有多少概率会出现无人获奖?
 */
public class AnnualMeetingLottery {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 人数
            int n = scanner.nextInt();
            // 计算所有人拿到字条可能出现的全部情况
            double allSituation = getAll(n);
            // 计算没有一个人获奖可能出现的所有情况
            double noOneWins = getNoOne(n);
            // 计算无人获奖的概率
            double probability = (noOneWins / allSituation) * 100;
            System.out.println(String.format("%.2f", probability) + "%");
        }
    }
 
    /**
     * 计算没有一个人获奖可能出现的所有情况
     *
     * @param n
     * @return
     */
    private static double getNoOne(int n) {
        // 边界值
        if (n == 1) {
            return 0;
        }
        if (n == 2) {
            return 1;
        } else {
            // ①第一个人与第二个人互相拿到了带有对方名字的字条
            // ---也就是说没抽中的概率在 n-2 字条中产生,
            // 接下来抽奖无人中奖的概率样本基数减少2
            // ②第一个人与第二个人没有互相拿到了带有对方名字的字条
            // ---也就是说没抽中的概率在 n-1 字条中产生
            // 接下来抽奖无人中奖的概率样本基数减少1
            return (n - 1) * (getNoOne(n - 1) + getNoOne(n - 2));
        }
    }
 
    /**
     * 计算所有人拿到字条可能出现的全部情况
     *
     * @param n
     * @return
     */
    private static double getAll(int n) {
        double sum = 1;
        while (n > 0) {
            sum *= n;
            n--;
        }
        return sum;
    }
}