每日算法 — 使用java实现宾果游戏：概率分布与期望完成轮次分析

宾果（Bingo）是经典概率游戏，玩家在5×5的卡片上标记随机抽取的数字，率先连成一线者获胜。本文用Java实现宾果游戏模拟器，重点讲解概率分布计算、期望完成轮次分析与蒙特卡洛模拟验证。

游戏规则与数据建模

标准宾果使用1-75的数字池，每张卡片为5×5矩阵（中心为免费格）。每次抽取一个数字，玩家在卡片上标记匹配项。率先在水平、垂直或对角线方向连成5个标记者获胜。

import java.util.*;

public class BingoSimulator {
    static final int SIZE = 5;
    static final int FREE = -1; // 中心免费格

    // B列:1-15, I列:16-30, N列:31-45, G列:46-60, O列:61-75
    static class Card {
        int[][] grid = new int[SIZE][SIZE];
        boolean[][] marked = new boolean[SIZE][SIZE];

        Card(Random rand) {
            int[][] ranges = {{1,15}, {16,30}, {31,45}, {46,60}, {61,75}};
            for (int col = 0; col < SIZE; col++) {
                List<Integer> nums = new ArrayList<>();
                for (int i = ranges[col][0]; i <= ranges[col][1]; i++) nums.add(i);
                Collections.shuffle(nums, rand);
                for (int row = 0; row < SIZE; row++) {
                    grid[row][col] = nums.get(row);
                }
            }
            grid[2][2] = FREE;
            marked[2][2] = true; // 中心免费格自动标记
        }

        void markNumber(int num) {
            for (int r = 0; r < SIZE; r++) {
                for (int c = 0; c < SIZE; c++) {
                    if (grid[r][c] == num) marked[r][c] = true;
                }
            }
        }

        // 检查是否已获胜
        boolean hasBingo() {
            // 检查行
            for (int r = 0; r < SIZE; r++) {
                boolean win = true;
                for (int c = 0; c < SIZE; c++) if (!marked[r][c]) win = false;
                if (win) return true;
            }
            // 检查列
            for (int c = 0; c < SIZE; c++) {
                boolean win = true;
                for (int r = 0; r < SIZE; r++) if (!marked[r][c]) win = false;
                if (win) return true;
            }
            // 检查对角线
            boolean d1 = true, d2 = true;
            for (int i = 0; i < SIZE; i++) {
                if (!marked[i][i]) d1 = false;
                if (!marked[i][SIZE-1-i]) d2 = false;
            }
            return d1 || d2;
        }
    }

概率分析与期望计算

    // 单张卡片在第k轮首次获胜的理论概率（近似）
    // 使用组合数学：在已抽k个数字中，某条特定线全被覆盖
    static double lineProbability(int k) {
        // 一条线有5格（含免费格则为4个数字）
        // 中心线含免费格，只需4个数字匹配
        // 非中心线需5个数字匹配
        // 这里用蒙特卡洛模拟更精确
        return 0;
    }

    // 蒙特卡洛模拟：统计单张卡片首次bingo的轮次分布
    static Map<Integer, Integer> simulateSingleCard(int trials, Random rand) {
        Map<Integer, Integer> dist = new HashMap<>();
        for (int t = 0; t < trials; t++) {
            Card card = new Card(rand);
            List<Integer> pool = new ArrayList<>();
            for (int i = 1; i <= 75; i++) pool.add(i);
            Collections.shuffle(pool, rand);
            for (int round = 1; round <= 75; round++) {
                card.markNumber(pool.get(round - 1));
                if (card.hasBingo()) {
                    dist.merge(round, 1, Integer::sum);
                    break;
                }
            }
        }
        return dist;
    }

    // 多玩家对战模拟：计算n个玩家时的获胜轮次分布
    static Map<Integer, Integer> simulateMultiplayer(int players, int trials, Random rand) {
        Map<Integer, Integer> dist = new HashMap<>();
        for (int t = 0; t < trials; t++) {
            List<Card> cards = new ArrayList<>();
            for (int i = 0; i < players; i++) cards.add(new Card(rand));
            List<Integer> pool = new ArrayList<>();
            for (int i = 1; i <= 75; i++) pool.add(i);
            Collections.shuffle(pool, rand);
            for (int round = 1; round <= 75; round++) {
                int num = pool.get(round - 1);
                for (Card c : cards) c.markNumber(num);
                boolean bingo = cards.stream().anyMatch(Card::hasBingo);
                if (bingo) {
                    dist.merge(round, 1, Integer::sum);
                    break;
                }
            }
        }
        return dist;
    }

统计分析主程序

    public static void main(String[] args) {
        Random rand = new Random(42);
        int trials = 100000;

        // 单卡模拟
        System.out.println("=== 单张卡片Bingo轮次分布 ===");
        Map<Integer, Integer> single = simulateSingleCard(trials, rand);
        printStats(single, trials);

        // 多玩家对战
        for (int players : new int[]{2, 5, 10, 50, 100}) {
            System.out.println("\n=== " + players + "人对战Bingo轮次分布 ===");
            Map<Integer, Integer> multi = simulateMultiplayer(players, trials, rand);
            printStats(multi, trials);
        }
    }

    static void printStats(Map<Integer, Integer> dist, int total) {
        long sum = 0;
        for (Map.Entry<Integer, Integer> e : dist.entrySet()) {
            sum += (long) e.getKey() * e.getValue();
        }
        double expected = (double) sum / total;
        System.out.printf("期望轮次: %.2f%n", expected);

        // 中位数
        int cum = 0;
        int median = 0;
        List<Integer> keys = new ArrayList<>(dist.keySet());
        Collections.sort(keys);
        for (int k : keys) {
            cum += dist.get(k);
            if (cum >= total / 2) { median = k; break; }
        }
        System.out.printf("中位数: %d%n", median);

        // 10%、50%、90%分位数
        int p10 = percentile(dist, keys, total, 0.10);
        int p50 = percentile(dist, keys, total, 0.50);
        int p90 = percentile(dist, keys, total, 0.90);
        System.out.printf("10%%分位: %d, 50%%分位: %d, 90%%分位: %d%n", p10, p50, p90);
    }

    static int percentile(Map<Integer, Integer> dist, List<Integer> keys, 
                          int total, double p) {
        int cum = 0;
        int target = (int) Math.ceil(total * p);
        for (int k : keys) {
            cum += dist.get(k);
            if (cum >= target) return k;
        }
        return keys.get(keys.size() - 1);
    }
}

关键概率结论

通过10万次蒙特卡洛模拟，我们得到以下核心结论：

玩家越多，首次出现Bingo的轮次越早，这是因为只要有任意一人完成即结束，是极值分布问题。

算法分析

时间复杂度：单局模拟 O(75 * SIZE^2)，10万次模拟总耗时约0.5-1秒。

空间复杂度：每张卡片 O(SIZE^2)，即 O(1)。