每日算法 — 使用java实现称球问题：三分搜索与信息论下界分析

引言

有12个外观完全相同的小球，其中有一个是假球（重量与其他不同，但不知道更重还是更轻）。用一台天平，最少需要称几次才能确定哪个是假球，以及它是更重还是更轻？

这个经典的智力题背后蕴含着深刻的信息论原理。每一次天平称量有3种可能结果（左重、平衡、右重），因此n次称量最多可以区分3ⁿ种情况。12个小球每种都可能是重或轻，共24种情况，而3³=27 > 24，所以理论上3次就够。本文将用Java实现这一经典问题的通用解法，并深入分析其信息论原理。

问题建模与信息论分析

信息论下界

对于N个小球，假球可能更重或更轻，共有2N种可能性。每次称量提供log₂(3) ≈ 1.585 bits的信息。

因此最少称量次数k满足：

[3^k \geq 2N \Rightarrow k \geq \lceil \log_3(2N) \rceil]

三分搜索策略

每次称量的核心目标是将当前的所有可能性尽可能均匀地分成3组：
– 左盘重的情况组
– 平衡的情况组
– 右盘重的情况组

理想情况下每组大小 ≈ 总可能性 / 3。

Java完整实现

import java.util.*;

/**
 * 称球问题通用求解器
 * 使用三分搜索与信息论最优策略
 */
public class WeighingBallSolver {

    // 小球状态枚举
    enum State {
        NORMAL,    // 正常球
        HEAVY,     // 假球且更重
        LIGHT      // 假球且更轻
    }

    // 称量结果枚举
    enum Result {
        LEFT_HEAVY,   // 左盘重
        BALANCED,     // 平衡
        RIGHT_HEAVY   // 右盘重
    }

    // 表示一次称量操作
    static class Weighing {
        List<Integer> left;   // 左盘小球
        List<Integer> right;  // 右盘小球

        Weighing(List<Integer> left, List<Integer> right) {
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "称量: 左盘" + left + " vs 右盘" + right;
        }
    }

    // 表示一个小球的可能性
    static class Possibility {
        int ball;      // 小球编号
        State state;   // 可能的状态（重或轻）

        Possibility(int ball, State state) {
            this.ball = ball;
            this.state = state;
        }

        @Override
        public String toString() {
            return "球" + ball + (state == State.HEAVY ? "(重)" : "(轻)");
        }
    }

    private final int n;           // 小球总数
    private final int maxWeighings; // 最大称量次数
    private List<Weighing> solution; // 找到的解

    public WeighingBallSolver(int n, int maxWeighings) {
        this.n = n;
        this.maxWeighings = maxWeighings;
    }

    /**
     * 主求解方法
     * @return 称量步骤列表，如果无法解决返回null
     */
    public List<Weighing> solve() {
        // 初始化所有可能性
        List<Possibility> possibilities = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            possibilities.add(new Possibility(i, State.HEAVY));
            possibilities.add(new Possibility(i, State.LIGHT));
        }

        solution = new ArrayList<>();
        if (dfs(possibilities, maxWeighings)) {
            return solution;
        }
        return null;
    }

    /**
     * 深度优先搜索寻找最优称量策略
     */
    private boolean dfs(List<Possibility> possibilities, int remaining) {
        // 只剩一种可能性，问题解决
        if (possibilities.size() == 1) {
            return true;
        }

        // 没有剩余称量次数
        if (remaining == 0) {
            return false;
        }

        // 剪枝：如果可能性数量 > 3^remaining，不可能解决
        if (possibilities.size() > Math.pow(3, remaining)) {
            return false;
        }

        // 枚举所有可能的称量方案
        // 对每个小球，有三种选择：放左盘、放右盘、不放
        int[] assignment = new int[n];  // -1:左盘, 0:不放, 1:右盘
        return enumerateAssignments(possibilities, remaining, assignment, 0);
    }

    /**
     * 枚举称量方案（将小球分配到左盘/右盘/不放）
     */
    private boolean enumerateAssignments(List<Possibility> possibilities, 
                                          int remaining, int[] assignment, int idx) {
        if (idx == n) {
            // 检查这种分配是否有效（左右盘数量相等）
            int leftCount = 0, rightCount = 0;
            for (int a : assignment) {
                if (a == -1) leftCount++;
                else if (a == 1) rightCount++;
            }
            if (leftCount != rightCount || leftCount == 0) {
                return false;
            }

            // 模拟称量，看能否将可能性均匀分割
            return tryWeighing(possibilities, remaining, assignment);
        }

        // 尝试三种分配
        for (int val = -1; val <= 1; val++) {
            assignment[idx] = val;
            if (enumerateAssignments(possibilities, remaining, assignment, idx + 1)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 尝试一次称量，检查是否能有效分割可能性
     */
    private boolean tryWeighing(List<Possibility> possibilities, int remaining, int[] assignment) {
        // 根据当前称量方案，将可能性分类
        List<Possibility> leftHeavy = new ArrayList<>();
        List<Possibility> balanced = new ArrayList<>();
        List<Possibility> rightHeavy = new ArrayList<>();

        for (Possibility p : possibilities) {
            Result result = simulateWeighing(p, assignment);
            switch (result) {
                case LEFT_HEAVY -> leftHeavy.add(p);
                case BALANCED -> balanced.add(p);
                case RIGHT_HEAVY -> rightHeavy.add(p);
            }
        }

        // 信息论最优：三组的大小尽量接近
        int maxGroup = Math.max(leftHeavy.size(), Math.max(balanced.size(), rightHeavy.size()));
        int minGroup = Math.min(leftHeavy.size(), Math.min(balanced.size(), rightHeavy.size()));

        // 如果某组过大，不可能在剩余次数内解决
        if (maxGroup > Math.pow(3, remaining - 1)) {
            return false;
        }

        // 尝试这种称量，递归求解子问题
        List<Integer> leftBalls = new ArrayList<>();
        List<Integer> rightBalls = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (assignment[i] == -1) leftBalls.add(i);
            else if (assignment[i] == 1) rightBalls.add(i);
        }

        Weighing w = new Weighing(leftBalls, rightBalls);
        solution.add(w);

        // 按最坏的子问题优先的顺序尝试（剪枝优化）
        List<List<Possibility>> groups = Arrays.asList(leftHeavy, balanced, rightHeavy);
        groups.sort((a, b) -> b.size() - a.size());  // 从大到小

        for (List<Possibility> group : groups) {
            if (dfs(group, remaining - 1)) {
                return true;
            }
        }

        // 回溯
        solution.remove(solution.size() - 1);
        return false;
    }

    /**
     * 模拟一次称量结果
     * @param p 假设的可能性（哪个球是假球，重还是轻）
     * @param assignment 小球分配方案
     * @return 称量结果
     */
    private Result simulateWeighing(Possibility p, int[] assignment) {
        int leftWeight = 0, rightWeight = 0;

        for (int i = 0; i < n; i++) {
            int weight = 1;  // 正常球重量为1
            if (i == p.ball) {
                weight = (p.state == State.HEAVY) ? 2 : 0;  // 假球重为2，轻为0
            }

            if (assignment[i] == -1) leftWeight += weight;
            else if (assignment[i] == 1) rightWeight += weight;
        }

        if (leftWeight > rightWeight) return Result.LEFT_HEAVY;
        else if (leftWeight < rightWeight) return Result.RIGHT_HEAVY;
        else return Result.BALANCED;
    }

    // ==================== 12球经典问题的特化解法 ====================

    /**
     * 12球问题的经典三步解法
     * 这是经过验证的最优策略
     */
    public static void solveClassic12Balls() {
        System.out.println("=== 12球经典问题解法 ===");
        System.out.println("问题：12个球中有一个假球（不知轻重），用天平最少3次找出。\n");

        System.out.println("第一次称量：左盘(0,1,2,3) vs 右盘(4,5,6,7)");
        System.out.println("  - 如果平衡：假球在(8,9,10,11)中");
        System.out.println("  - 如果左重：假球在(0,1,2,3)重 或 (4,5,6,7)轻");
        System.out.println("  - 如果右重：假球在(4,5,6,7)重 或 (0,1,2,3)轻\n");

        System.out.println("第二次称量（以左重为例）：左盘(0,1,4) vs 右盘(2,5,8)");
        System.out.println("  - 平衡：假球在(3)重 或 (6,7)轻 → 第三次称量可确定");
        System.out.println("  - 左重：假球在(0,1)重 或 (5)轻 → 第三次称量可确定");
        System.out.println("  - 右重：假球在(2)重 或 (4)轻 → 第三次称量可确定\n");

        System.out.println("通用策略：每次将当前候选集尽可能均分为3组。\n");
    }

    /**
     * 信息论验证：计算最少称量次数
     */
    public static void informationTheoryAnalysis(int n) {
        int possibilities = 2 * n;  // n个球，每个可能重或轻
        double minWeighings = Math.ceil(Math.log(possibilities) / Math.log(3));

        System.out.println("=== 信息论分析 ===");
        System.out.println("小球数量: " + n);
        System.out.println("总可能性: " + possibilities + " (每个球可能重或轻)");
        System.out.println("每次称量信息量: log₂(3) ≈ 1.585 bits");
        System.out.println("理论最少称量次数: ⌈log₃(" + possibilities + ")⌉ = " + (int)minWeighings);
        System.out.println("3^" + (int)minWeighings + " = " + (int)Math.pow(3, minWeighings));
        System.out.println("是否可行: " + (Math.pow(3, minWeighings) >= possibilities ? "是" : "否"));
        System.out.println();
    }

    /**
     * 交互式称球模拟器
     */
    static class BallSimulator {
        private final int n;
        private final int fakeBall;      // 假球编号
        private final boolean isHeavy;   // 是否更重
        private int weighingsUsed = 0;

        BallSimulator(int n, int fakeBall, boolean isHeavy) {
            this.n = n;
            this.fakeBall = fakeBall;
            this.isHeavy = isHeavy;
        }

        Result weigh(List<Integer> left, List<Integer> right) {
            weighingsUsed++;
            int leftWeight = 0, rightWeight = 0;

            for (int b : left) {
                leftWeight += (b == fakeBall) ? (isHeavy ? 2 : 0) : 1;
            }
            for (int b : right) {
                rightWeight += (b == fakeBall) ? (isHeavy ? 2 : 0) : 1;
            }

            if (leftWeight > rightWeight) return Result.LEFT_HEAVY;
            if (leftWeight < rightWeight) return Result.RIGHT_HEAVY;
            return Result.BALANCED;
        }

        int getWeighingsUsed() { return weighingsUsed; }
    }

    /**
     * 使用策略自动求解并验证
     */
    public static void interactiveSolve(int n, int fakeBall, boolean isHeavy) {
        System.out.println("=== 交互式求解 ===");
        System.out.println("设置：球" + fakeBall + "是假球，" + (isHeavy ? "更重" : "更轻"));

        BallSimulator sim = new BallSimulator(n, fakeBall, isHeavy);

        // 候选集：每个球可能是重或轻
        Set<String> candidates = new HashSet<>();
        for (int i = 0; i < n; i++) {
            candidates.add(i + "H");
            candidates.add(i + "L");
        }

        // 预定义的12球最优策略（简化版）
        // 这里展示策略框架，实际实现需要完整的决策树

        // 对于12球3次的问题，使用已验证的经典策略
        if (n == 12) {
            // 第一次称量
            Result r1 = sim.weigh(Arrays.asList(0,1,2,3), Arrays.asList(4,5,6,7));
            System.out.println("第1次称量: (0,1,2,3) vs (4,5,6,7) → " + r1);

            Result r2, r3;
            String answer = "";

            switch (r1) {
                case BALANCED:
                    // 假球在8,9,10,11
                    r2 = sim.weigh(Arrays.asList(8,9), Arrays.asList(10,0));
                    System.out.println("第2次称量: (8,9) vs (10,0) → " + r2);
                    if (r2 == Result.BALANCED) {
                        r3 = sim.weigh(Arrays.asList(11), Arrays.asList(0));
                        System.out.println("第3次称量: (11) vs (0) → " + r3);
                        answer = "11" + (r3 == Result.LEFT_HEAVY ? "H" : "L");
                    } else if (r2 == Result.LEFT_HEAVY) {
                        r3 = sim.weigh(Arrays.asList(8), Arrays.asList(9));
                        System.out.println("第3次称量: (8) vs (9) → " + r3);
                        if (r3 == Result.BALANCED) answer = "10L";
                        else if (r3 == Result.LEFT_HEAVY) answer = "8H";
                        else answer = "9H";
                    } else {
                        r3 = sim.weigh(Arrays.asList(8), Arrays.asList(9));
                        System.out.println("第3次称量: (8) vs (9) → " + r3);
                        if (r3 == Result.BALANCED) answer = "10H";
                        else if (r3 == Result.LEFT_HEAVY) answer = "9L";
                        else answer = "8L";
                    }
                    break;

                case LEFT_HEAVY:
                    // 假球在0,1,2,3重 或 4,5,6,7轻
                    r2 = sim.weigh(Arrays.asList(0,1,4), Arrays.asList(2,5,8));
                    System.out.println("第2次称量: (0,1,4) vs (2,5,8) → " + r2);
                    if (r2 == Result.BALANCED) {
                        r3 = sim.weigh(Arrays.asList(6), Arrays.asList(7));
                        System.out.println("第3次称量: (6) vs (7) → " + r3);
                        if (r3 == Result.BALANCED) answer = "3H";
                        else if (r3 == Result.LEFT_HEAVY) answer = "7L";
                        else answer = "6L";
                    } else if (r2 == Result.LEFT_HEAVY) {
                        r3 = sim.weigh(Arrays.asList(0), Arrays.asList(1));
                        System.out.println("第3次称量: (0) vs (1) → " + r3);
                        if (r3 == Result.BALANCED) answer = "5L";
                        else if (r3 == Result.LEFT_HEAVY) answer = "0H";
                        else answer = "1H";
                    } else {
                        r3 = sim.weigh(Arrays.asList(2), Arrays.asList(0));
                        System.out.println("第3次称量: (2) vs (0) → " + r3);
                        if (r3 == Result.BALANCED) answer = "4L";
                        else answer = "2H";
                    }
                    break;

                case RIGHT_HEAVY:
                    // 假球在4,5,6,7重 或 0,1,2,3轻
                    r2 = sim.weigh(Arrays.asList(4,5,0), Arrays.asList(6,1,8));
                    System.out.println("第2次称量: (4,5,0) vs (6,1,8) → " + r2);
                    if (r2 == Result.BALANCED) {
                        r3 = sim.weigh(Arrays.asList(2), Arrays.asList(3));
                        System.out.println("第3次称量: (2) vs (3) → " + r3);
                        if (r3 == Result.BALANCED) answer = "7H";
                        else if (r3 == Result.LEFT_HEAVY) answer = "3L";
                        else answer = "2L";
                    } else if (r2 == Result.LEFT_HEAVY) {
                        r3 = sim.weigh(Arrays.asList(4), Arrays.asList(5));
                        System.out.println("第3次称量: (4) vs (5) → " + r3);
                        if (r3 == Result.BALANCED) answer = "1L";
                        else if (r3 == Result.LEFT_HEAVY) answer = "4H";
                        else answer = "5H";
                    } else {
                        r3 = sim.weigh(Arrays.asList(6), Arrays.asList(0));
                        System.out.println("第3次称量: (6) vs (0) → " + r3);
                        if (r3 == Result.BALANCED) answer = "0L";
                        else answer = "6H";
                    }
                    break;
            }

            System.out.println("\n结论: 球" + answer.charAt(0) + "是假球，" + 
                             (answer.charAt(1) == 'H' ? "更重" : "更轻"));
            System.out.println("实际答案: 球" + fakeBall + (isHeavy ? "H" : "L"));
            System.out.println("共使用 " + sim.getWeighingsUsed() + " 次称量");
            System.out.println("判断正确: " + answer.equals(fakeBall + (isHeavy ? "H" : "L")));
        }
    }

    public static void main(String[] args) {
        // 信息论分析
        informationTheoryAnalysis(12);
        informationTheoryAnalysis(13);
        informationTheoryAnalysis(39);

        // 经典解法说明
        solveClassic12Balls();

        // 交互式求解示例
        interactiveSolve(12, 3, true);   // 球3更重
        System.out.println();
        interactiveSolve(12, 7, false);  // 球7更轻
        System.out.println();
        interactiveSolve(12, 10, true);  // 球10更重

        // 通用求解器测试（小规模）
        System.out.println("\n=== 通用求解器测试 ===");
        WeighingBallSolver solver = new WeighingBallSolver(3, 2);
        List<Weighing> sol = solver.solve();
        if (sol != null) {
            System.out.println("3球2次称量解法:");
            for (Weighing w : sol) {
                System.out.println("  " + w);
            }
        }
    }
}

复杂度分析

重要结论：13个球虽然满足信息论条件27≥26，但存在奇偶性约束，实际上无法在3次内解决。这说明了信息论下界是必要条件而非充分条件。

应用场景

1. 质量检测：生产线上的产品重量检测与异常定位。
2. 故障诊断：通过分批测试定位故障组件。
3. 信息编码：三分决策树的编码与压缩。
4. 算法教学：理解信息论与决策树的经典案例。

总结

称球问题是信息论与算法设计完美结合的典范。通过将每次称量建模为三分决策，我们不仅找到了最优策略，更深刻理解了”信息量”这一核心概念。从12球问题推广到N球问题，信息论给出了不可逾越的下界，而巧妙的分配策略则让我们触及这一下界。这种从具体到抽象、从实践到理论的思维方式，正是算法设计的精髓所在。