如何计算n个圆盘k个柱子的汉诺塔最大分支因子？

要找到这个问题的通用解法，我们得先抓住核心：最大分支因子出现在合法移动数量最多的状态下——而这种状态的关键是让尽可能多的小圆盘处于可移动的顶端位置，且每个小圆盘有尽可能多的目标柱子可选。

分情况推导 #

1. 当圆盘数量 ≥ 柱子数-1（n ≥ k-1） #

此时我们可以构造出移动选择最多的状态：

• 把最大的n - (k-1)个圆盘堆在同一个柱子上（作为固定底座，顶端是第k个圆盘）；
• 剩下的k-1个最小圆盘，每个单独放在一个柱子上；
• 此时所有k个柱子都被占用，没有空柱子。

计算这个状态的分支因子：

• 每个小圆盘s（1 ≤ s ≤k-1）可以移动到：堆大圆盘的柱子（顶端圆盘比它大） + 所有放着比s大的小圆盘的柱子，总计(k - s)个目标柱子；
• 堆大圆盘的柱子顶端是第k个圆盘，它无法移动（其他柱子顶端都是更小的圆盘，违反“小圆盘不能放在大圆盘上”的规则）；
• 所有小圆盘的可移动数量之和为：Σ(k - s)（s从1到k-1）= k*(k-1)/2。

这就是当前条件下的最大分支因子——因为我们已经用满了所有柱子，且每个小圆盘的可选移动数达到了上限。

2. 当圆盘数量 < 柱子数-1（n < k-1） #

此时最优状态是：

• n个圆盘每个单独放在一个柱子上；
• 剩下的k -n个柱子是空的。

计算这个状态的分支因子：

• 每个圆盘s（1 ≤s ≤n）可以移动到：所有空柱子（共k-n个） + 所有放着比s大的圆盘的柱子（共n -s个），总计k -s个目标柱子；
• 所有圆盘的可移动数量之和为：Σ(k - s)（s从1到n）= n*(2k -n -1)/2。

任何其他状态（比如把部分小圆盘堆在一起）都会减少可移动的圆盘数量，或者缩小单个圆盘的可选目标范围，导致总分支因子更小。

验证示例 #

• 经典汉诺塔场景：k=3，n=5（n≥k-1=2），最大分支因子是3*2/2=3——和我们熟悉的经典汉诺塔每个状态最多3种移动完全吻合；
• 多柱少盘场景：k=5，n=2（n<k-1=4），最大分支因子是2*(10-2-1)/2=7——实际移动数为圆盘1的4种选择 + 圆盘2的3种选择，总和7，完全正确。

内容的提问来源于stack exchange，提问作者pepito