丢手绢是经典的儿童围圈游戏：众人围坐成环，一人持手绢绕圈奔跑，伺机丢在某人身后，被丢者发现后起身追逐，持绢者需在被抓住前跑到对方空位坐下。本文用Java建模这一游戏的追及过程，通过环形队列与概率分析，求解最优丢绢位置与追逐策略。
游戏机制与数学建模
将n名玩家均匀排列在圆周上，相邻两人间距为1单位。持绢者跑动速度为v1，被丢者反应时间为t后起身追赶，速度为v2。持绢者需要选择丢绢位置，使得自己能在被抓住前跑回该位置的正对面空位坐下。
核心决策变量：
– 丢绢距离d：持绢者相对于目标需要跑过的弧长
– 临界条件：持绢者跑完半圈(n/2)的时间 ≤ 被丢者反应时间 + 追赶所需时间
环形追及的临界分析
持绢者沿圆周跑向空位，最短路径为半圈n/2。被丢者发现后沿相反方向追赶，双方构成环形追及问题。设圆周总长为n，则持绢者成功的充要条件为：
(n/2) / v1 < t + (n/2) / v2
整理得临界速度比：v1/v2 > n / (n + 2*v1*t)。当持绢者速度优势足够大时，任意位置均可成功；否则需要选择靠近目标的位置丢绢以缩短跑程。
Java完整实现
import java.util.*;
/**
* 丢手绢游戏 - 环形追及与概率最优策略
* 建模围圈奔跑的追及问题，分析最优丢绢位置
*/
public class DropTheHandkerchief {
// ==================== 核心模型：环形玩家队列 ====================
static class Player {
int id;
String name;
double speed; // 奔跑速度
double reaction; // 反应时间(秒)
boolean hasHandkerchief; // 是否持绢
int position; // 在环上的位置索引
Player(int id, String name, double speed, double reaction) {
this.id = id;
this.name = name;
this.speed = speed;
this.reaction = reaction;
this.hasHandkerchief = false;
}
}
/**
* 环形玩家队列：用数组模拟围坐成圈的玩家
*/
static class CircleQueue {
Player[] players;
int size;
CircleQueue(int n) {
players = new Player[n];
size = n;
}
void setPlayer(int pos, Player p) {
players[pos] = p;
p.position = pos;
}
/**
* 计算两点之间的最短弧长距离
* 环形结构：顺时针和逆时针取较小值
*/
int shortestDistance(int from, int to) {
int clockwise = (to - from + size) % size;
int counterClockwise = (from - to + size) % size;
return Math.min(clockwise, counterClockwise);
}
/**
* 从from出发沿指定方向走到to的步数
* @param direction 1为顺时针, -1为逆时针
*/
int distanceWithDirection(int from, int to, int direction) {
if (direction == 1) {
return (to - from + size) % size;
} else {
return (from - to + size) % size;
}
}
}
// ==================== 核心算法：追及判定与最优位置 ====================
/**
* 判定持绢者从target位置丢绢后能否成功逃脱
* @param circle 环形队列
* @param runnerId 持绢者ID
* @param targetId 被丢绢者ID
* @param dropDistance 在target身后多远丢绢(步数)
* @return 逃脱成功返回true
*/
static boolean canEscape(CircleQueue circle, int runnerId, int targetId, int dropDistance) {
Player runner = circle.players[runnerId];
Player target = circle.players[targetId];
int n = circle.size;
// 持绢者需要跑到target对面的空位，即target + n/2的位置
int emptySeat = (target.position + n / 2) % n;
int runDistance = circle.shortestDistance(runner.position, emptySeat);
double runnerTime = (double) runDistance / runner.speed;
// 被丢者反应时间 + 追赶时间
// 被丢者沿与runner相反方向跑向emptySeat(因为runner要去那)
int chaseDistance = circle.shortestDistance(target.position, emptySeat);
double targetTime = target.reaction + (double) chaseDistance / target.speed;
return runnerTime < targetTime; // 严格小于表示成功
}
/**
* 为持绢者寻找最优丢绢目标：能成功逃脱且跑程最短
* @return 最优目标ID列表(可能多个同样优)
*/
static List<Integer> findBestTargets(CircleQueue circle, int runnerId) {
Player runner = circle.players[runnerId];
List<Integer> bestTargets = new ArrayList<>();
int minRunDistance = Integer.MAX_VALUE;
for (int i = 0; i < circle.size; i++) {
if (i == runnerId) continue; // 不能丢给自己
if (canEscape(circle, runnerId, i, 1)) {
int emptySeat = (circle.players[i].position + circle.size / 2) % circle.size;
int runDist = circle.shortestDistance(runner.position, emptySeat);
if (runDist < minRunDistance) {
minRunDistance = runDist;
bestTargets.clear();
bestTargets.add(i);
} else if (runDist == minRunDistance) {
bestTargets.add(i);
}
}
}
return bestTargets;
}
/**
* 计算每个位置作为丢绢目标的成功概率
* 假设目标反应时间在[minReact, maxReact]均匀分布
*/
static Map<Integer, Double> computeSuccessProbability(
CircleQueue circle, int runnerId, double minReact, double maxReact) {
Map<Integer, Double> probMap = new HashMap<>();
Player runner = circle.players[runnerId];
int n = circle.size;
for (int i = 0; i < n; i++) {
if (i == runnerId) continue;
Player target = circle.players[i];
int emptySeat = (target.position + n / 2) % n;
int runDist = circle.shortestDistance(runner.position, emptySeat);
int chaseDist = circle.shortestDistance(target.position, emptySeat);
double runnerTime = (double) runDist / runner.speed;
// 目标成功追赶需要: reaction + chaseDist/speed < runnerTime
// 即 reaction < runnerTime - chaseDist/speed
double criticalReaction = runnerTime - (double) chaseDist / target.speed;
if (criticalReaction <= minReact) {
probMap.put(i, 1.0); // 反应再快也追不上
} else if (criticalReaction >= maxReact) {
probMap.put(i, 0.0); // 反应再慢也能追上
} else {
double prob = (criticalReaction - minReact) / (maxReact - minReact);
probMap.put(i, Math.max(0, Math.min(1, prob)));
}
}
return probMap;
}
// ==================== 扩展：多轮博弈模拟 ====================
/**
* 模拟多轮丢手绢游戏，统计各玩家被抓住概率
*/
static Map<Integer, Integer> simulateGames(CircleQueue circle, int rounds) {
Random rand = new Random(42);
Map<Integer, Integer> caughtCount = new HashMap<>();
int n = circle.size;
int runner = 0; // 初始持绢者
for (int r = 0; r < rounds; r++) {
// 贪心策略：选择成功概率最高的目标
Map<Integer, Double> probs = computeSuccessProbability(
circle, runner, 0.5, 2.0);
int bestTarget = -1;
double bestProb = -1;
for (Map.Entry<Integer, Double> e : probs.entrySet()) {
if (e.getValue() > bestProb) {
bestProb = e.getValue();
bestTarget = e.getKey();
}
}
// 模拟实际结果
if (bestTarget != -1) {
double actualReact = 0.5 + rand.nextDouble() * 1.5;
Player runnerP = circle.players[runner];
Player targetP = circle.players[bestTarget];
int emptySeat = (targetP.position + n / 2) % n;
int runDist = circle.shortestDistance(runnerP.position, emptySeat);
int chaseDist = circle.shortestDistance(targetP.position, emptySeat);
double rTime = (double) runDist / runnerP.speed;
double tTime = actualReact + (double) chaseDist / targetP.speed;
if (rTime >= tTime) {
// 被抓住，持绢者失败
caughtCount.merge(runner, 1, Integer::sum);
runner = bestTarget; // 被丢者成为新的持绢者
} else {
// 逃脱成功
runner = bestTarget; // 被丢者成为新的持绢者(传统规则)
}
}
}
return caughtCount;
}
// ==================== 主程序与演示 ====================
public static void main(String[] args) {
int n = 12; // 12人围圈
CircleQueue circle = new CircleQueue(n);
// 初始化玩家：速度越快、反应越快越强
circle.setPlayer(0, new Player(0, "小明", 3.0, 0.8));
circle.setPlayer(1, new Player(1, "小红", 2.5, 1.0));
circle.setPlayer(2, new Player(2, "小刚", 3.2, 0.9));
circle.setPlayer(3, new Player(3, "小丽", 2.8, 1.2));
circle.setPlayer(4, new Player(4, "小强", 3.5, 0.7));
circle.setPlayer(5, new Player(5, "小芳", 2.6, 1.1));
circle.setPlayer(6, new Player(6, "小军", 3.1, 0.9));
circle.setPlayer(7, new Player(7, "小敏", 2.9, 1.0));
circle.setPlayer(8, new Player(8, "小伟", 3.3, 0.8));
circle.setPlayer(9, new Player(9, "小静", 2.7, 1.3));
circle.setPlayer(10, new Player(10, "小波", 3.0, 1.0));
circle.setPlayer(11, new Player(11, "小艳", 2.8, 1.1));
System.out.println("========== 丢手绢游戏 - 环形追及分析 ==========");
System.out.println("玩家人数: " + n);
System.out.println();
int runner = 4; // 假设小强持绢
System.out.println("持绢者: " + circle.players[runner].name);
// 分析对每个目标的成功概率
Map<Integer, Double> probs = computeSuccessProbability(circle, runner, 0.5, 2.0);
System.out.println("\n对各目标的逃脱成功概率:");
for (int i = 0; i < n; i++) {
if (i == runner) continue;
System.out.printf(" %s: %.2f%%%n", circle.players[i].name, probs.getOrDefault(i, 0.0) * 100);
}
// 寻找最优目标
List<Integer> best = findBestTargets(circle, runner);
System.out.println("\n最优丢绢目标: ");
for (int id : best) {
System.out.println(" " + circle.players[id].name);
}
// 多轮模拟
System.out.println("\n========== 1000轮博弈模拟 ==========");
Map<Integer, Integer> caught = simulateGames(circle, 1000);
System.out.println("被抓住次数统计:");
for (int i = 0; i < n; i++) {
int count = caught.getOrDefault(i, 0);
System.out.printf(" %s: %d 次 (%.1f%%)%n", circle.players[i].name, count, count / 10.0);
}
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 单目标追及判定 | O(1) | 常数计算 |
| 最优目标搜索 | O(n) | 遍历所有玩家 |
| 成功概率计算 | O(n) | 每个目标一次计算 |
| 多轮模拟 | O(rounds × n) | 每轮需比较所有目标概率 |
环形结构使距离计算具有对称性，shortestDistance通过取模运算在O(1)内完成，是高效处理环形问题的关键技巧。
扩展思考
- 非均匀分布：若玩家围圈间距不等，需将位置建模为带权图，最短路径改用Dijkstra算法。
- 联盟策略：多名玩家可临时结盟围堵持绢者，引入多人博弈的纳什均衡分析。
- 信息不完全：被丢者不知谁被丢绢，直到邻座提示，可建模为部分可观察马尔可夫决策过程（POMDP）。
丢手绢将环形队列、追及问题与概率决策融为一体，是理解离散环形结构动态规划的绝佳案例。
