数字炸弹（Number Bomb）是派对聚会中的经典猜数游戏：主持人在某个区间内秘密设定一个目标数字，参与者轮流猜测，主持人告知”偏大”或”偏小”，猜中者受罚。本文用Java实现智能猜数策略，核心在于二分搜索的信息论最优性与区间博弈的排除策略分析。
游戏规则与信息论建模
游戏设定：
– 区间范围 [L, R]，初始通常为 [1, 100]
– 秘密数字 target，由主持人随机生成
– 猜测反馈：猜数后告知”太大”、”太小”或”命中”
– 淘汰规则：猜中炸弹数字者出局
信息论视角：每次猜测将搜索空间划分为”偏大区”、”偏小区”和”命中点”。最优策略应使每次猜测后剩余候选数的期望数量最小化，即选择使max(偏大区间大小, 偏小区间大小)最小的猜测点——这正是二分搜索的核心思想。
二分搜索的最优性证明
对于长度为n的有序区间，二分搜索每次将搜索范围减半。最坏情况下需要⌈log₂(n+1)⌉次猜测即可确定目标。
证明：设T(n)为长度为n时的最坏猜测次数。每次猜测后剩余区间最多为⌊n/2⌋，故T(n) = 1 + T(⌊n/2⌋)，解得T(n) = ⌈log₂(n+1)⌉。
对于1-100的范围，理论上最多需要⌈log₂(101)⌉ = 7次猜测即可命中。
Java完整实现
import java.util.*;
/**
* 数字炸弹游戏 - 二分搜索与区间博弈最优排除
* 核心问题：在区间[L,R]中最快定位秘密数字
*/
public class NumberBomb {
// ==================== 核心算法：二分搜索家族 ====================
/**
* 标准二分搜索：每次猜中间值，保证最坏情况最优
* @param target 秘密数字
* @param low 区间下界
* @param high 区间上界
* @return 猜测历史记录
*/
public static List<Integer> binarySearch(int target, int low, int high) {
List<Integer> history = new ArrayList<>();
int steps = 0;
int l = low, r = high;
while (l <= r) {
steps++;
// 防溢出中间值计算
int mid = l + (r - l) / 2;
history.add(mid);
if (mid == target) {
System.out.println("二分搜索命中! 目标=" + target + ", 步数=" + steps);
return history;
} else if (mid < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return history;
}
/**
* 三分搜索变体：当分布不均匀时，可按概率加权选择分割点
* 若目标服从均匀分布，三分搜索无优势；若已知分布则适用
*/
public static List<Integer> weightedBinarySearch(int target, int low, int high,
Map<Integer, Double> probMap) {
List<Integer> history = new ArrayList<>();
int l = low, r = high;
while (l <= r) {
// 选择使左右两侧概率和尽可能相等的分割点
int bestGuess = l;
double minDiff = Double.MAX_VALUE;
for (int g = l; g <= r; g++) {
double leftProb = 0, rightProb = 0;
for (int i = l; i < g; i++) leftProb += probMap.getOrDefault(i, 0.0);
for (int i = g + 1; i <= r; i++) rightProb += probMap.getOrDefault(i, 0.0);
double diff = Math.abs(leftProb - rightProb);
if (diff < minDiff) {
minDiff = diff;
bestGuess = g;
}
}
history.add(bestGuess);
if (bestGuess == target) {
System.out.println("加权二分命中! 目标=" + target + ", 步数=" + history.size());
return history;
} else if (bestGuess < target) {
l = bestGuess + 1;
} else {
r = bestGuess - 1;
}
}
return history;
}
// ==================== 区间博弈：多玩家版本 ====================
/**
* 多玩家轮流猜数，猜中者淘汰，最后存活者胜
* 每位玩家采用不同策略，模拟博弈过程
*/
static class GameEngine {
int secret; // 秘密数字
int low, high; // 当前有效区间
int initialRange; // 初始范围
List<Player> players; // 玩家列表
int currentPlayer; // 当前轮到的玩家
Random rand;
GameEngine(int secret, int low, int high, List<Player> players, Random rand) {
this.secret = secret;
this.low = low;
this.high = high;
this.initialRange = high - low + 1;
this.players = new ArrayList<>(players);
this.currentPlayer = 0;
this.rand = rand;
}
/**
* 运行完整游戏，返回最终存活玩家列表
*/
List<Player> run() {
int round = 1;
while (players.size() > 1) {
Player p = players.get(currentPlayer);
int guess = p.makeGuess(low, high, initialRange, secret, rand);
System.out.printf("轮%d [%s] 猜: %d (区间[%d,%d])%n",
round, p.name, guess, low, high);
if (guess == secret) {
System.out.println(" -> 命中炸弹! " + p.name + " 淘汰!");
p.alive = false;
// 重新生成秘密数字继续游戏
secret = rand.nextInt(initialRange) + low;
low = 1;
high = initialRange;
} else if (guess < secret) {
System.out.println(" -> 太小了");
low = Math.max(low, guess + 1);
} else {
System.out.println(" -> 太大了");
high = Math.min(high, guess - 1);
}
players.removeIf(pl -> !pl.alive);
if (players.size() <= 1) break;
currentPlayer = (currentPlayer + 1) % players.size();
round++;
if (round > 500) break; // 安全退出
}
return players;
}
}
/**
* 玩家策略接口与多种实现
*/
static abstract class Player {
String name;
boolean alive;
int totalGuesses;
Player(String name) {
this.name = name;
this.alive = true;
this.totalGuesses = 0;
}
abstract int makeGuess(int low, int high, int initialRange, int secret, Random rand);
}
/** 纯二分搜索策略：始终猜中间值 */
static class BinaryPlayer extends Player {
BinaryPlayer() { super("二分侠"); }
int makeGuess(int low, int high, int initialRange, int secret, Random rand) {
totalGuesses++;
return low + (high - low) / 2;
}
}
/** 随机策略：在有效区间内均匀随机猜测 */
static class RandomPlayer extends Player {
RandomPlayer() { super("随机君"); }
int makeGuess(int low, int high, int initialRange, int secret, Random rand) {
totalGuesses++;
return low + rand.nextInt(high - low + 1);
}
}
/** 赌徒策略：倾向于猜边界值，认为"数字在中间太明显" */
static class GamblerPlayer extends Player {
GamblerPlayer() { super("赌徒"); }
int makeGuess(int low, int high, int initialRange, int secret, Random rand) {
totalGuesses++;
// 70%概率猜靠近边界的值
if (rand.nextDouble() < 0.7) {
return rand.nextBoolean() ? low + rand.nextInt(3) : high - rand.nextInt(3);
}
return low + (high - low) / 2;
}
}
/** 学习策略：根据历史记录调整，避免重复区间 */
static class SmartPlayer extends Player {
Set<Integer> guessed = new HashSet<>();
SmartPlayer() { super("学霸"); }
int makeGuess(int low, int high, int initialRange, int secret, Random rand) {
totalGuesses++;
int guess = low + (high - low) / 2;
// 若中间值已猜过，向未探索方向偏移
while (guessed.contains(guess) && guess <= high) {
guess++;
}
if (guess > high) guess = low + (high - low) / 2;
guessed.add(guess);
return guess;
}
}
/** 对抗策略：故意猜让下家陷入小范围的值 */
static class AdversarialPlayer extends Player {
AdversarialPlayer() { super("老狐狸"); }
int makeGuess(int low, int high, int initialRange, int secret, Random rand) {
totalGuesses++;
// 将区间分割为极端不均匀的两段，让下家承担风险
int range = high - low + 1;
if (range <= 3) return low + (high - low) / 2;
// 故意偏离中点，制造一侧大区间
return low + range / 4 + rand.nextInt(range / 2);
}
}
// ==================== 策略胜率统计 ====================
/**
* 大规模模拟统计各策略胜率
*/
static Map<String, Integer> simulateTournament(int simulations, int low, int high) {
Map<String, Integer> wins = new HashMap<>();
String[] names = {"二分侠", "随机君", "赌徒", "学霸", "老狐狸"};
for (String n : names) wins.put(n, 0);
for (int sim = 0; sim < simulations; sim++) {
Random rand = new Random(sim);
int secret = rand.nextInt(high - low + 1) + low;
List<Player> players = new ArrayList<>();
players.add(new BinaryPlayer());
players.add(new RandomPlayer());
players.add(new GamblerPlayer());
players.add(new SmartPlayer());
players.add(new AdversarialPlayer());
GameEngine engine = new GameEngine(secret, low, high, players, rand);
List<Player> survivors = engine.run();
// 统计谁存活最久(简化：最后存活的赢)
// 由于多轮重置secret，采用积分制
for (Player p : players) {
if (p.alive) {
wins.merge(p.name, 1, Integer::sum);
}
}
}
return wins;
}
// ==================== 信息论分析 ====================
/**
* 计算不同策略的期望猜测次数
*/
static void analyzeExpectedGuesses(int low, int high) {
System.out.println("\n========== 信息论分析 ==========");
int range = high - low + 1;
System.out.println("搜索范围: [" + low + ", " + high + "]，共" + range + "个数");
System.out.println("二分搜索最坏情况: " + (int)Math.ceil(Math.log(range + 1) / Math.log(2)) + "次");
// 统计所有可能目标的猜测次数
int totalSteps = 0;
for (int target = low; target <= high; target++) {
List<Integer> hist = binarySearchSilent(target, low, high);
totalSteps += hist.size();
}
System.out.printf("二分搜索平均猜测次数: %.2f次%n", (double)totalSteps / range);
// 随机策略模拟期望
int randomTotal = 0;
Random rand = new Random(42);
int samples = 10000;
for (int s = 0; s < samples; s++) {
int target = rand.nextInt(range) + low;
randomTotal += randomSearchSteps(target, low, high, rand);
}
System.out.printf("随机策略平均猜测次数: %.2f次%n", (double)randomTotal / samples);
}
static List<Integer> binarySearchSilent(int target, int low, int high) {
List<Integer> history = new ArrayList<>();
int l = low, r = high;
while (l <= r) {
int mid = l + (r - l) / 2;
history.add(mid);
if (mid == target) break;
else if (mid < target) l = mid + 1;
else r = mid - 1;
}
return history;
}
static int randomSearchSteps(int target, int low, int high, Random rand) {
int steps = 0;
int l = low, r = high;
while (true) {
steps++;
int guess = l + rand.nextInt(r - l + 1);
if (guess == target) return steps;
else if (guess < target) l = guess + 1;
else r = guess - 1;
}
}
// ==================== 主程序与演示 ====================
public static void main(String[] args) {
System.out.println("========== 数字炸弹 - 二分搜索最优排除 ==========\n");
int low = 1, high = 100;
// 1. 演示二分搜索找特定数字
System.out.println("=== 二分搜索演示 (范围1-100) ===");
int[] targets = {1, 50, 77, 100};
for (int t : targets) {
System.out.print("目标=" + t + ": ");
List<Integer> hist = binarySearch(t, low, high);
System.out.println("猜测序列: " + hist);
}
// 2. 信息论分析
analyzeExpectedGuesses(low, high);
// 3. 多玩家博弈演示
System.out.println("\n=== 五人对战演示 ===");
Random rand = new Random(2024);
int secret = rand.nextInt(100) + 1;
System.out.println("(演示用秘密数字: " + secret + ")");
List<Player> players = new ArrayList<>();
players.add(new BinaryPlayer());
players.add(new RandomPlayer());
players.add(new GamblerPlayer());
players.add(new SmartPlayer());
players.add(new AdversarialPlayer());
GameEngine engine = new GameEngine(secret, low, high, players, rand);
List<Player> survivors = engine.run();
System.out.println("\n最终存活: " + survivors);
// 4. 策略胜率统计
System.out.println("\n=== 策略胜率统计 (1000场) ===");
Map<String, Integer> wins = simulateTournament(1000, low, high);
for (Map.Entry<String, Integer> e : wins.entrySet()) {
System.out.printf("%s: %d 胜 (%.1f%%)%n", e.getKey(), e.getValue(), e.getValue() / 10.0);
}
}
}
算法复杂度分析
| 策略 | 最坏时间 | 平均时间 | 空间 | 最优性 |
|---|---|---|---|---|
| 二分搜索 | O(log n) | O(log n) | O(1) | 最坏最优 |
| 加权二分 | O(log n) | O(log n) | O(1) | 分布最优 |
| 随机搜索 | O(n) | O(log n) | O(1) | 无保证 |
| 线性搜索 | O(n) | O(n) | O(1) | 非最优 |
二分搜索的最优性体现在：对于”仅知偏大/偏小”的反馈模型，没有任何确定性算法能在最坏情况下优于⌈log₂(n+1)⌉次猜测。这是信息论下界决定的——每次猜测最多产生1比特有效信息，而确定n个数需要log₂(n)比特。
扩展思考
- 噪声信道：若主持人有概率
ε给出错误反馈，需引入容错二分搜索（如重复询问确认），期望查询次数增长为O(log n / (1-H(ε)))，其中H为二元熵函数。 - 多秘密数字：区间内有k个炸弹数字，猜中任意一个即淘汰。最优策略改为将区间分为k+1段，使每段候选数尽可能相等，推广为k叉搜索。
- 连续区间：目标为实数而非整数时，二分搜索不再适用，需改用黄金分割搜索或三分搜索寻找单峰函数的极值点。
数字炸弹将二分搜索的信息论最优性融入趣味博弈，是理解”分治策略”与”信息熵”最直观的教学场景之一。
