一、游戏规则背后的两个数学问题
叠积木（Block Stacking）的玩法极简：屏幕上若干长度相同的木块，玩家把它们一块一块往上叠，越往上越容易倒。它之所以值得用算法拆解，是因为里面藏着两个完全不同类型的问题：
- 判稳问题（静态）：给定当前已叠好的
n块，满足什么条件它不会倒？这是重心计算问题。 - 最优悬挑问题（组合优化）：如果允许任意调整每块的水平偏移，最多能让顶层木块探出桌子边缘多远？答案不是线性的，而是调和级数。
这两点合起来，就是”看起来像物理、实际是数学”的典型样本：玩家凭手感做的每一块微调，本质上都在逼近一个调和级数的渐进值。
二、判稳：重心必须落在支撑区间上
把每块木块看成均匀矩形，宽度 w、高度 h。叠放稳定性判据只有一条：
第
k块及其以上所有木块的合成重心，必须落在第k块与第k-1块的接触区间内。
之所以只看”上方整体的重心”，是因为刚体静力学的等价性：上方 n-k+1 块的所有重力可以合成一个作用于其合重心的单力，只要这个力的作用线落在支撑面内，就不会产生倾覆力矩。
合成重心的递推是 O(1) 的：
M_k = M_{k+1} + m_k
X_k = (M_{k+1}·X_{k+1} + m_k·x_k) / M_k
其中 m_k 是第 k 块的质量（均匀矩形时 m = w·h·ρ），x_k 是其中心横坐标。接触区间则是两块的重叠部分 [max(L_k, L_{k-1}), min(R_k, R_{k-1})]——注意这里取的是两块的重叠区，不是单块的范围，因为支撑力只能通过实际接触面传递。
public final class Stability {
/** 单块木块：中心横坐标 cx，宽度 w，高度 h，密度 rho */
public record Block(double cx, double w, double h, double rho) {
public double mass() { return w * h * rho; }
public double left() { return cx - w / 2; }
public double right() { return cx + w / 2; }
}
public record Verdict(boolean stable, int failIndex, double needShift) { }
/**
* 自顶向下逐层累积重心，检查每一层的支撑条件。
* blocks 按从下到上顺序传入（index 0 是最底层）。
*/
public static Verdict check(java.util.List<Block> blocks) {
int n = blocks.size();
if (n == 0) return new Verdict(true, -1, 0);
double mass = 0; // 上方整体质量
double moment = 0; // 上方整体力矩（质量 × 横坐标）
for (int k = n - 1; k >= 0; k--) {
Block b = blocks.get(k);
double m = b.mass();
// 先把第 k 块自身并入"上方整体"
mass += m;
moment += m * b.cx;
double com = moment / mass; // 上方整体的合成重心
// 最高一块没有"上方支撑"的概念，直接跳过
if (k == n - 1) continue;
Block below = blocks.get(k - 1);
double sL = Math.max(b.left(), below.left());
double sR = Math.min(b.right(), below.right());
// 无接触 → 直接失稳；重心跑出接触区间 → 倾覆
if (sL >= sR || com < sL || com > sR) {
// 需左移量：合成重心到本块中心的偏移（决策只需向左修正时为正）
return new Verdict(false, k, com - b.cx);
}
}
return new Verdict(true, -1, 0);
}
}
这里的 needShift 返回值是很有用的诊断量：它等于”上方整体重心相对该块中心的偏移”，可以直供给自动纠偏逻辑做单步修正，而不必整堆重排。
三、最优悬挑：从 1/2 到 ln n
假设 n 块等长等重的木块，宽度取 1，全部朝右探出。经典结论是：自顶向下第 i 块相对下一块的最大稳定偏移是 1/(2i)，于是总悬挑为
H(n) = (1/2) · (1 + 1/2 + 1/3 + ... + 1/n) = H_n / 2
第 n 个调和数 H_n ≈ ln n + γ（γ ≈ 0.5772，欧拉-马歇罗尼常数）。所以悬挑随块数只呈对数增长：4 块约 1.04 个宽度，31 块才约 2.01 个宽度，要到 12 367 块才能探出 5 个宽度。这解释了为什么”叠积木”永远玩不出无限探出——指数级增加块数才换来线性增加的悬挑。
构造方式很干净：自顶向下，每放一块就把上方整体的重心精确压到下方那块的最右边缘。由于上方 k 块总重 k，把它们整体右移 d 使重心到达下块右缘，恰好给出 d = 1/(2(k+1))，这就是调和级数的来源。
public final class Overhang {
/**
* 返回 n 块等重等长（宽度=1）木块的最优中心坐标，index 0 为底层。
* 顶层中心取 0，越往下越靠左，底层右侧再贴住桌面边缘。
*/
public static double[] optimalCenters(int n) {
double[] pos = new double[n];
pos[n - 1] = 0; // 顶层基准
for (int i = n - 2; i >= 0; i--) {
// 每往下一层，向左移 1/(2·层距顶层数)，使上方重心压在下块右缘
pos[i] = pos[i + 1] - 1.0 / (2.0 * (n - 1 - i));
}
return pos;
}
/** 顶层右边缘相对桌面边缘的悬挑距离 */
public static double overhang(int n) {
double[] pos = optimalCenters(n);
double tableEdge = pos[0] + 0.5 - 1.0 / (2.0 * n);
return (pos[n - 1] + 0.5) - tableEdge;
}
/** 理论值 H_n / 2，用于校验构造 */
public static double theoretical(int n) {
double h = 0;
for (int i = 1; i <= n; i++) h += 1.0 / i;
return h / 2.0;
}
}
四、玩家视角的最优决策：动态规划而非贪心
真实游戏里每块木块不是等重的，还带分值（越往上得分越高）。于是问题变成：给定 n 个木块（每个有质量 m_i、宽度 w_i、分值 v_i），选一个子集并按某个顺序叠放，使总分最大且保持稳定。
贪心（每次选”分值密度最高”的）会失效，因为它可能把重块放在高位，迫使后续偏移收敛、提前失稳。正确做法是区间 DP：以”当前已叠总质量”和”顶层中心偏移”为状态，但这个连续维度无法直接离散。工程上常用的两步近似是可控且足够好的：
- 排序：按质量升序叠（轻的在上）。用交换论证可以证明”若两块相邻且上方更重，交换后上层容错只会变宽”，因此这个排序不会损失可行性。
- DP 选子集：在排序后的序列上做
0/1背包，dp[i][j]表示前i块选j块的最大得分，逐层用O(1)递推维护重心。
public final class Planner {
/** 按质量升序排序（同质量时按宽度升序，宽的放下层更稳） */
public static java.util.List<Stability.Block> order(java.util.List<Stability.Block> raw) {
java.util.List<Stability.Block> list = new java.util.ArrayList<>(raw);
list.sort((a, b) -> {
int c = Double.compare(a.mass(), b.mass());
return c != 0 ? c : Double.compare(a.w(), b.w()); // 同质量时窄的放下层
});
return list;
}
/**
* 在排序结果上做 0/1 背包：重量为质量（取整），价值为分值。
* 返回最大可得总分。
*/
public static double bestScore(java.util.List<Stability.Block> ordered,
double[] value, int capacity) {
int n = ordered.size();
double[] dp = new double[capacity + 1]; // 滚动数组压空间
for (int i = 0; i < n; i++) {
int weight = (int) Math.ceil(ordered.get(i).mass());
double v = value[i];
// 逆序更新保证每块只用一次
for (int cap = capacity; cap >= weight; cap--) {
dp[cap] = Math.max(dp[cap], dp[cap - weight] + v);
}
}
return dp[capacity];
}
}
五、给”手感”建模：临界区间的宽度
玩家在叠积木时感觉”最后一点总能压线”，机理是稳定性判据有一个容差带：只要重心落在接触区间内就稳定，而接触区间本身有宽度 w。因此对第 k 层（自顶向下计数），安全偏移的窗口半宽约等于 1/(2k)。
| 层数（自顶向下） | 理论最大偏移 | 容错半宽（等宽木块） |
|---|---|---|
| 1 | 0.500 | 0.500 |
| 4 | 0.125 | 0.125 |
| 8 | 0.0625 | 0.0625 |
| 16 | 0.0313 | 0.0313 |
1/(2k) 衰减意味着容错率与层数成反比，这就是”越往上越难”的定量解释，也说明游戏难度曲线应当设计成让容差衰减慢于 1/k，否则玩家会在某一层突然崩盘。
六、完整工程结构
stack-blocks/
├── pom.xml
└── src/main/java/com/example/stack/
├── Stability.java // 重心累积与失稳判定
├── Overhang.java // 调和级数最优悬挑
├── Planner.java // 排序 + 背包选子集
└── Demo.java
public final class Demo {
public static void main(String[] args) {
// 场景一：验证最优悬挑 —— 构造值与调和级数应完全一致
for (int n : new int[]{1, 2, 4, 8, 31}) {
System.out.printf("n=%2d 构造悬挑=%.5f 理论值=%.5f%n",
n, Overhang.overhang(n), Overhang.theoretical(n));
}
// 场景二：判稳 —— 每层右移 0.55 的 4 块，第 3 块即失稳
java.util.List<Stability.Block> stack = new java.util.ArrayList<>();
for (int i = 0; i < 4; i++) {
stack.add(new Stability.Block(i * 0.55, 1.0, 0.25, 1.0));
}
Stability.Verdict v = Stability.check(stack);
System.out.printf("稳定=%s 失败层(0起)=%d 偏移=%.4f%n",
v.stable(), v.failIndex(), v.needShift());
}
}
跑出来的输出是：n=1/2/4/8/31 的构造悬挑分别为 0.50000 / 0.75000 / 1.04167 / 1.35893 / 2.01362，与 H_n/2 逐位吻合；第二个场景报 稳定=false 失败层=2 偏移=0.2750，说明每层等距右移 0.55 时，从第 3 块（0 起索引 2）开始整体重心已越出支撑区，需要把这层及以上整体左移约 0.275 才能恢复平衡。
七、复杂度与三条工程结论
check：O(n)时间、O(1)额外空间（滚动累加质量与力矩）。optimalCenters/overhang：O(n)；若要n极大可直接用ln n + γ近似，相对误差O(1/n)。- 背包选子集：
O(n·C)时间，滚动数组下O(C)空间。
第一条结论，判稳必须用”上方整体重心”而不是”相邻两块的重心”。只比较相邻两块的常见错误实现，会让一块轻而极偏的顶块把整个堆叠系统带倒却检测不出来——因为缺陷的根源在更下层，而相邻两块看起来完全正常。
第二条结论，悬挑是单调但非线性的。以为”块数翻倍、悬挑翻倍”的直觉会直接导致关卡数值设计失衡；正确的心智模型是”翻倍块数只增加约 0.35 个宽度”（ln 2 / 2 ≈ 0.347）。
第三条结论，浮点累计误差会否掉合法的临界叠法。临界状态下合成重心恰在接触边界，误差累积到 1e-15 量级就可能让本该通过的判定失败。工程上要给判定加一个 1e-9 的容差，并把坐标改用以毫米为单位的整数来根治。
