引言
汉诺塔问题是计算机科学中最经典的递归示例之一。传统的递归解法优雅简洁，但在实际工程中，递归可能面临栈溢出和性能问题。本文将用Java实现汉诺塔的完全非递归解法，包括基于栈显式模拟递归过程，以及利用二进制模式直接计算移动序列的高效迭代算法。
问题回顾
汉诺塔规则：有三根柱子A、B、C，A柱上有 $n$ 个大小不一的圆盘，大盘在下小盘在上。目标是将所有圆盘从A移动到C，每次只能移动一个圆盘，且大盘不能压在小盘上。
经典递归解法：
1. 将 $n-1$ 个盘从A经C移到B
2. 将第 $n$ 个盘从A移到C
3. 将 $n-1$ 个盘从B经A移到C
递归深度为 $n$，总移动次数为 $2^n – 1$。
二进制模式迭代法
汉诺塔的移动序列与二进制计数存在深刻联系：
– 第 $k$ 步（从1开始）移动的盘号等于 $k$ 的二进制末尾0的个数加1。
– 盘号的移动方向：奇数盘顺时针（A→B→C→A），偶数盘逆时针（A→C→B→A）。
利用这一性质，可在 $O(1)$ 空间内直接计算第 $k$ 步的移动，无需维护调用栈。
Java实现
圆盘与状态定义
public class Disk {
int size; // 盘的大小（编号）
char from; // 起始柱
char to; // 目标柱
char aux; // 辅助柱
public Disk(int size, char from, char to, char aux) {
this.size = size;
this.from = from;
this.to = to;
this.aux = aux;
}
@Override
public String toString() {
return String.format("Disk[%d]: %c -> %c (aux=%c)", size, from, to, aux);
}
}
public class TowerState {
private Stack<Integer>[] pegs; // 三根柱子上的盘
private int n;
private int moveCount;
@SuppressWarnings("unchecked")
public TowerState(int n) {
this.n = n;
this.pegs = new Stack[3];
for (int i = 0; i < 3; i++) pegs[i] = new Stack<>();
// A柱(0)上放置n到1的盘
for (int i = n; i >= 1; i--) pegs[0].push(i);
this.moveCount = 0;
}
public boolean move(int from, int to) {
if (pegs[from].isEmpty()) return false;
if (!pegs[to].isEmpty() && pegs[from].peek() > pegs[to].peek()) return false;
int disk = pegs[from].pop();
pegs[to].push(disk);
moveCount++;
System.out.printf("Step %d: Move disk %d from %c to %c%n",
moveCount, disk, (char)('A'+from), (char)('A'+to));
return true;
}
public boolean isComplete() {
return pegs[0].isEmpty() && pegs[1].isEmpty() && pegs[2].size() == n;
}
public void printState() {
System.out.println(" A: " + pegs[0]);
System.out.println(" B: " + pegs[1]);
System.out.println(" C: " + pegs[2]);
}
}
递归解法（基准）
public class HanoiRecursive {
private int moveCount;
public void solve(int n, char from, char to, char aux) {
if (n <= 0) return;
solve(n - 1, from, aux, to);
System.out.printf("Move disk %d from %c to %c%n", n, from, to);
moveCount++;
solve(n - 1, aux, to, from);
}
public int getMoveCount() { return moveCount; }
}
栈模拟递归（显式栈非递归）
import java.util.*;
public class HanoiStackSimulation {
/**
* 用显式栈模拟递归调用
* 每个栈帧记录：{n, from, to, aux, stage}
* stage: 0=进入, 1=左递归返回后, 2=右递归返回后
*/
public void solve(int n, char from, char to, char aux) {
// 栈帧：int n, char from, to, aux, int stage
Deque<int[]> stack = new ArrayDeque<>();
// 用int编码: n(8位) | from(8位) | to(8位) | aux(8位) | stage(8位)
stack.push(new int[]{n, from, to, aux, 0});
while (!stack.isEmpty()) {
int[] frame = stack.peek();
int disk = frame[0];
char f = (char) frame[1];
char t = (char) frame[2];
char a = (char) frame[3];
int stage = frame[4];
if (disk <= 0) {
stack.pop();
continue;
}
if (stage == 0) {
// 模拟 solve(n-1, from, aux, to)
frame[4] = 1; // 标记下次进入stage 1
stack.push(new int[]{disk - 1, f, a, t, 0});
} else if (stage == 1) {
// 执行移动
System.out.printf("Move disk %d from %c to %c%n", disk, f, t);
frame[4] = 2; // 标记下次进入stage 2
// 模拟 solve(n-1, aux, to, from)
stack.push(new int[]{disk - 1, a, t, f, 0});
} else {
// stage == 2，当前帧完成
stack.pop();
}
}
}
}
二进制模式直接迭代
public class HanoiBinaryPattern {
/**
* 基于二进制模式的O(1)空间迭代算法
* 第k步移动的盘号 = k末尾0的个数 + 1
* 奇数盘顺时针(A->B->C->A)，偶数盘逆时针(A->C->B->A)
*/
public void solve(int n) {
int totalMoves = (1 << n) - 1;
// 柱编号：0=A, 1=B, 2=C
int[] pegs = {0, 1, 2}; // 奇数盘使用这个顺序（顺时针）
for (int k = 1; k <= totalMoves; k++) {
int disk = Integer.numberOfTrailingZeros(k) + 1; // 移动的盘号
// 计算该盘的移动方向
// 对于n个盘的标准汉诺塔，奇数盘顺时针，偶数盘逆时针
int from, to;
if (disk % 2 == 1) {
// 奇数盘：顺时针 A->B->C->A
// 第k步中，盘disk的位置由 k / 2^disk 的奇偶性决定
int cycle = (k >> disk) % 3;
from = cycle;
to = (cycle + 1) % 3;
} else {
// 偶数盘：逆时针 A->C->B->A
int cycle = (k >> disk) % 3;
from = cycle;
to = (from + 2) % 3; // +2 等价于 -1 (mod 3)
}
System.out.printf("Move disk %d from %c to %c%n",
disk, (char)('A'+from), (char)('A'+to));
}
}
/**
* 更简洁的二进制模式实现
* 利用总步数为奇数的性质，每步只移动一个盘
*/
public void solveOptimized(int n) {
int totalMoves = (1 << n) - 1;
// 记录每根柱子上最顶部盘的奇偶性（简化追踪）
for (int step = 1; step <= totalMoves; step++) {
int disk = Integer.numberOfTrailingZeros(step) + 1;
// 盘disk的当前位置：通过分析step和disk的关系
// 盘disk每 2^disk 步移动一次
int moveIndex = step >> disk; // 盘disk的第几次移动
char from, to;
if (disk % 2 == 1) {
// 奇数盘顺时针: A(0)->B(1)->C(2)->A(0)
int pos = moveIndex % 3;
from = (char)('A' + pos);
to = (char)('A' + (pos + 1) % 3);
} else {
// 偶数盘逆时针: A(0)->C(2)->B(1)->A(0)
int pos = moveIndex % 3;
// 映射: 0->A, 1->C, 2->B
char[] map = {'A', 'C', 'B'};
from = map[pos];
to = map[(pos + 1) % 3];
}
System.out.printf("Step %d: Move disk %d from %c to %c%n",
step, disk, from, to);
}
}
}
状态追踪迭代法（带验证）
public class HanoiIterativeWithState {
/**
* 迭代法配合状态追踪，可验证每一步的合法性
* 核心观察：每步只能移动最小的可移动盘，或唯一合法的移动
*/
public void solveWithValidation(int n) {
TowerState state = new TowerState(n);
int totalMoves = (1 << n) - 1;
// 记录每个盘当前所在的柱子
int[] diskPos = new int[n + 1]; // 1-based, 初始都在A(0)
Arrays.fill(diskPos, 0);
// 方向：奇数盘顺时针(+1)，偶数盘逆时针(-1, 即+2 mod 3)
int[] direction = new int[n + 1];
for (int i = 1; i <= n; i++) {
direction[i] = (i % 2 == 1) ? 1 : 2; // 1=顺时针, 2=逆时针
}
System.out.println("Initial state:");
state.printState();
for (int step = 1; step <= totalMoves; step++) {
int disk = Integer.numberOfTrailingZeros(step) + 1;
int from = diskPos[disk];
int to = (from + direction[disk]) % 3;
state.move(from, to);
diskPos[disk] = to;
}
System.out.println("\nFinal state:");
state.printState();
System.out.println("Complete: " + state.isComplete());
}
/**
* 另一种简洁迭代：利用两个合法移动中必有一个移动最小盘的性质
*/
public void solveFrameStewart(int n) {
// 使用Stack数组显式维护三根柱子
Stack<Integer>[] pegs = new Stack[3];
for (int i = 0; i < 3; i++) pegs[i] = new Stack<>();
for (int i = n; i >= 1; i--) pegs[0].push(i);
int totalMoves = (1 << n) - 1;
int moveCount = 0;
// 对于奇数n，第一步将最小盘移到C；偶数n，移到B
int source = 0, target = (n % 2 == 1) ? 2 : 1, auxiliary = 3 - source - target;
while (moveCount < totalMoves) {
// 移动最小盘
int disk = pegs[source].pop();
pegs[target].push(disk);
moveCount++;
System.out.printf("Step %d: Move disk %d from %c to %c%n",
moveCount, disk, (char)('A'+source), (char)('A'+target));
if (moveCount >= totalMoves) break;
// 执行另一个合法移动（不涉及最小盘）
int otherSrc = -1, otherDst = -1;
// 找两根非空柱子之间唯一的合法移动
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == j) continue;
if (!pegs[i].isEmpty() && (pegs[j].isEmpty() || pegs[i].peek() < pegs[j].peek())) {
if (otherSrc == -1) {
otherSrc = i;
otherDst = j;
}
}
}
}
if (otherSrc != -1) {
disk = pegs[otherSrc].pop();
pegs[otherDst].push(disk);
moveCount++;
System.out.printf("Step %d: Move disk %d from %c to %c%n",
moveCount, disk, (char)('A'+otherSrc), (char)('A'+otherDst));
}
// 更新最小盘的下一个目标
int newTarget = 3 - source - target;
source = target;
target = newTarget;
}
}
}
主程序
public class HanoiMain {
public static void main(String[] args) {
int n = 4;
System.out.println("=== 递归解法 ===");
HanoiRecursive recursive = new HanoiRecursive();
recursive.solve(n, 'A', 'C', 'B');
System.out.println("总步数: " + recursive.getMoveCount());
System.out.println("\n=== 栈模拟递归 ===");
HanoiStackSimulation stackSim = new HanoiStackSimulation();
stackSim.solve(n, 'A', 'C', 'B');
System.out.println("\n=== 二进制模式迭代 ===");
HanoiBinaryPattern binary = new HanoiBinaryPattern();
binary.solveOptimized(n);
System.out.println("\n=== 状态追踪迭代 ===");
HanoiIterativeWithState iterative = new HanoiIterativeWithState();
iterative.solveWithValidation(n);
}
}
复杂度分析
- 时间复杂度：所有解法均为 $O(2^n)$，必须输出 $2^n – 1$ 次移动。
- 空间复杂度：
- 递归解法：$O(n)$ 调用栈深度。
- 栈模拟：$O(n)$ 显式栈空间。
- 二进制模式：$O(1)$ 额外空间（不含输出），最优。
- 状态追踪：$O(n)$ 盘位置数组。
总结
本文展示了汉诺塔问题的三种非递归实现：栈模拟递归、二进制模式直接计算、以及状态追踪迭代法。二进制模式利用数学规律在常数空间内生成移动序列，是最优雅的迭代解法。理解这些非递归实现有助于深入掌握递归与迭代的等价性，以及位运算在算法中的巧妙应用。
