引言
汉诺塔（Tower of Hanoi）是计算机科学中最经典的递归问题之一：将n个大小不一的圆盘从A柱移动到C柱，每次只能移动一个圆盘，且大盘不能叠在小盘之上。传统解法基于递归分治，时间复杂度为O(2ⁿ)。然而，汉诺塔问题与格雷码（Gray Code）之间存在一个深刻而优雅的数学联系：n个圆盘的最优移动序列恰好对应n位格雷码的生成顺序。本文将揭示这一联系，并利用Java的位运算实现一个非递归的迭代解法，其时间复杂度同样为O(2ⁿ)，但避免了递归的栈开销，且能直接计算第k步的移动内容而无需模拟前面所有步骤。
数学原理
格雷码与汉诺塔的同构关系
n位格雷码是一种二进制编码方式，相邻两个编码之间只有一位不同。标准反射格雷码的生成公式为：
$$G(k) = k \oplus \left\lfloor \frac{k}{2} \right\rfloor$$
其中 $k$ 为自然数，$\oplus$ 表示按位异或。
关键发现：将n个圆盘的汉诺塔最优解视为一个长度为 $2^n – 1$ 的操作序列，第 $k$ 步（从1开始计数）移动的圆盘编号，恰好等于 $G(k)$ 与 $G(k-1)$ 异或结果中最低位1的位置（即 Integer.numberOfTrailingZeros(G(k) ^ G(k-1))）。
位运算直接计算
更进一步，第 $k$ 步移动的圆盘编号可以直接通过以下位运算得到，无需计算格雷码：
$$disk = \text{ctz}(k)$$
其中 $\text{ctz}$ 是 “Count Trailing Zeros” 的缩写，即计算 $k$ 的二进制表示中末尾连续0的个数。例如：
– $k=1$ (二进制 1) → ctz=0 → 移动1号圆盘
– $k=2$ (二进制 10) → ctz=1 → 移动2号圆盘
– $k=3$ (二进制 11) → ctz=0 → 移动1号圆盘
– $k=4$ (二进制 100) → ctz=2 → 移动3号圆盘
移动方向判定
圆盘的移动方向取决于圆盘编号的奇偶性和总圆盘数n的奇偶性：
– 当n为奇数时：1号盘按 A→C→B→A 循环，偶数号盘按 A→B→C→A 循环
– 当n为偶数时：1号盘按 A→B→C→A 循环，偶数号盘按 A→C→B→A 循环
用更简洁的方式表达：对于 $disk$ 号圆盘，其移动方向由 $(disk + n) \bmod 2$ 决定。
Java实现
项目结构
src/
├── hanoi/
│ ├── HanoiSolver.java // 汉诺塔求解器接口
│ ├── RecursiveSolver.java // 传统递归解法（对照）
│ ├── GrayCodeSolver.java // 格雷码映射迭代解法
│ └── BitwiseSolver.java // 纯位运算直接计算解法
├── graycode/
│ └── GrayCodeGenerator.java // n位格雷码生成器
└── Main.java
GrayCodeGenerator.java — n位格雷码生成器
package graycode;
import java.util.ArrayList;
import java.util.List;
/**
* n位反射格雷码生成器
* 格雷码性质：相邻两个编码只有一位不同
* 生成公式：G(k) = k ^ (k >> 1)
*/
public class GrayCodeGenerator {
private final int n;
public GrayCodeGenerator(int n) {
if (n <= 0 || n > 31) {
throw new IllegalArgumentException("n必须在1-31之间");
}
this.n = n;
}
/**
* 生成全部2^n个n位格雷码
* @return 格雷码整数列表
*/
public List<Integer> generateAll() {
List<Integer> grayCodes = new ArrayList<>();
int total = 1 << n; // 2^n
for (int k = 0; k < total; k++) {
grayCodes.add(grayCode(k));
}
return grayCodes;
}
/**
* 计算第k个格雷码（从0开始）
* 公式：G(k) = k ^ (k >> 1)
*/
public int grayCode(int k) {
return k ^ (k >> 1);
}
/**
* 将整数转换为n位二进制字符串
*/
public String toBinaryString(int value) {
String bin = Integer.toBinaryString(value);
// 补前导零到n位
StringBuilder sb = new StringBuilder();
for (int i = bin.length(); i < n; i++) sb.append('0');
sb.append(bin);
return sb.toString();
}
/**
* 获取相邻格雷码之间变化的位位置（从0开始，最低位为0）
* @return 每一步变化的位位置列表，长度为2^n - 1
*/
public List<Integer> getBitChangePositions() {
List<Integer> positions = new ArrayList<>();
List<Integer> codes = generateAll();
for (int i = 1; i < codes.size(); i++) {
int diff = codes.get(i) ^ codes.get(i - 1);
// diff是2的幂，计算末尾0的个数即变化的位置
int pos = Integer.numberOfTrailingZeros(diff);
positions.add(pos);
}
return positions;
}
public int getN() { return n; }
}
HanoiSolver.java — 求解器接口与移动记录
package hanoi;
import java.util.List;
/**
* 汉诺塔求解器统一接口
*/
public interface HanoiSolver {
/**
* 求解n个圆盘的汉诺塔问题
* @param n 圆盘数量
* @return 移动步骤列表
*/
List<Move> solve(int n);
/**
* 直接计算第k步（从1开始）移动的圆盘编号
* @param n 圆盘总数
* @param k 步数（1 <= k <= 2^n - 1）
* @return 移动的圆盘编号（1-based）
*/
int getDiskAtStep(int n, int k);
/**
* 封装一次移动操作
*/
class Move {
public final int disk; // 圆盘编号（1表示最小盘）
public final char from; // 起始柱
public final char to; // 目标柱
public Move(int disk, char from, char to) {
this.disk = disk;
this.from = from;
this.to = to;
}
@Override
public String toString() {
return String.format("移动圆盘%d: %c -> %c", disk, from, to);
}
}
}
RecursiveSolver.java — 传统递归解法（对照基准）
package hanoi;
import java.util.ArrayList;
import java.util.List;
/**
* 经典递归分治汉诺塔求解器
* 将n个盘从source移到target，借助auxiliary
* T(n) = 2T(n-1) + 1 = O(2^n)
*/
public class RecursiveSolver implements HanoiSolver {
@Override
public List<Move> solve(int n) {
List<Move> moves = new ArrayList<>();
hanoi(n, 'A', 'C', 'B', moves);
return moves;
}
private void hanoi(int n, char source, char target, char auxiliary, List<Move> moves) {
if (n <= 0) return;
// 第一步：将n-1个盘从source移到auxiliary，借助target
hanoi(n - 1, source, auxiliary, target, moves);
// 第二步：将第n个盘从source移到target
moves.add(new Move(n, source, target));
// 第三步：将n-1个盘从auxiliary移到target，借助source
hanoi(n - 1, auxiliary, target, source, moves);
}
@Override
public int getDiskAtStep(int n, int k) {
// 递归解法无法直接计算第k步，需要先求解全部步骤
List<Move> moves = solve(n);
if (k < 1 || k > moves.size()) {
throw new IllegalArgumentException("步数k超出范围");
}
return moves.get(k - 1).disk;
}
}
GrayCodeSolver.java — 格雷码映射迭代解法
package hanoi;
import graycode.GrayCodeGenerator;
import java.util.ArrayList;
import java.util.List;
/**
* 基于格雷码映射的汉诺塔迭代求解器
* 核心洞察：第k步移动的圆盘 = G(k)与G(k-1)异或结果的最低位1位置
* 等价于：第k步移动的圆盘 = ctz(k)，即k的二进制末尾0的个数
*/
public class GrayCodeSolver implements HanoiSolver {
@Override
public List<Move> solve(int n) {
List<Move> moves = new ArrayList<>();
GrayCodeGenerator grayGen = new GrayCodeGenerator(n);
List<Integer> bitChanges = grayGen.getBitChangePositions();
// 维护三个柱子的状态（栈）
java.util.Stack<Integer>[] pegs = new java.util.Stack[3];
for (int i = 0; i < 3; i++) pegs[i] = new java.util.Stack<>();
// 初始状态：所有圆盘在A柱（柱子0），大盘在栈底
for (int disk = n; disk >= 1; disk--) {
pegs[0].push(disk);
}
char[] pegNames = {'A', 'B', 'C'};
// 根据格雷码位变化序列执行移动
for (int step = 0; step < bitChanges.size(); step++) {
int disk = bitChanges.get(step) + 1; // 位位置0-based转圆盘编号1-based
// 找到该圆盘所在的柱子
int fromPeg = -1;
for (int p = 0; p < 3; p++) {
if (!pegs[p].isEmpty() && pegs[p].peek() == disk) {
fromPeg = p;
break;
}
}
if (fromPeg == -1) {
throw new IllegalStateException("无法找到圆盘" + disk);
}
// 确定目标柱子（只能移动到合法的柱子）
int toPeg = determineTargetPeg(pegs, fromPeg, disk, n);
// 执行移动
pegs[fromPeg].pop();
pegs[toPeg].push(disk);
moves.add(new Move(disk, pegNames[fromPeg], pegNames[toPeg]));
}
return moves;
}
/**
* 根据圆盘奇偶性和当前柱子状态确定目标柱子
*/
private int determineTargetPeg(java.util.Stack<Integer>[] pegs, int fromPeg, int disk, int n) {
// 圆盘移动规则：
// 奇数号盘和偶数号盘的循环方向相反，且与总圆盘数n的奇偶性有关
int[] order;
if ((n % 2) == 1) {
// n为奇数：奇数盘按 0->2->1->0 (A->C->B->A)
// 偶数盘按 0->1->2->0 (A->B->C->A)
order = ((disk % 2) == 1)
? new int[]{0, 2, 1}
: new int[]{0, 1, 2};
} else {
// n为偶数：奇数盘按 0->1->2->0 (A->B->C->A)
// 偶数盘按 0->2->1->0 (A->C->B->A)
order = ((disk % 2) == 1)
? new int[]{0, 1, 2}
: new int[]{0, 2, 1};
}
// 在循环顺序中找到fromPeg的下一个合法柱子
int fromIndex = -1;
for (int i = 0; i < 3; i++) {
if (order[i] == fromPeg) {
fromIndex = i;
break;
}
}
// 尝试循环顺序中的下一个柱子
for (int offset = 1; offset <= 2; offset++) {
int candidate = order[(fromIndex + offset) % 3];
// 合法移动：目标柱子为空，或目标柱子顶盘比当前盘大
if (pegs[candidate].isEmpty() || pegs[candidate].peek() > disk) {
return candidate;
}
}
throw new IllegalStateException("无法找到合法的目标柱子");
}
@Override
public int getDiskAtStep(int n, int k) {
if (k < 1 || k >= (1 << n)) {
throw new IllegalArgumentException("步数k必须在[1, 2^n - 1]范围内");
}
// 第k步（1-based）移动的圆盘编号 = ctz(k) + 1
// ctz = count trailing zeros
return Integer.numberOfTrailingZeros(k) + 1;
}
}
BitwiseSolver.java — 纯位运算直接计算（最优实现）
package hanoi;
import java.util.ArrayList;
import java.util.List;
/**
* 纯位运算汉诺塔求解器
* 完全避免格雷码生成和状态模拟，直接通过数学公式计算每一步
*
* 核心公式：
* 1. 第k步移动的圆盘：disk = ctz(k) + 1
* 2. 移动方向：由(disk + n) % 2决定
* 3. 可以直接计算第k步，无需前驱步骤
*/
public class BitwiseSolver implements HanoiSolver {
@Override
public List<Move> solve(int n) {
List<Move> moves = new ArrayList<>();
int totalSteps = (1 << n) - 1; // 2^n - 1
// 追踪每个圆盘当前所在的柱子（0=A, 1=B, 2=C）
// 初始：所有圆盘在A柱
int[] diskPeg = new int[n + 1]; // diskPeg[d] 表示圆盘d所在的柱子
for (int d = 1; d <= n; d++) diskPeg[d] = 0;
char[] pegNames = {'A', 'B', 'C'};
for (int k = 1; k <= totalSteps; k++) {
int disk = getDiskAtStep(n, k);
int fromPeg = diskPeg[disk];
int toPeg = getTargetPeg(disk, fromPeg, n);
moves.add(new Move(disk, pegNames[fromPeg], pegNames[toPeg]));
diskPeg[disk] = toPeg;
}
return moves;
}
@Override
public int getDiskAtStep(int n, int k) {
if (k < 1 || k >= (1 << n)) {
throw new IllegalArgumentException(
String.format("步数k=%d超出范围[1, %d]", k, (1 << n) - 1));
}
// 数学定理：第k步移动的圆盘编号 = ctz(k) + 1
return Integer.numberOfTrailingZeros(k) + 1;
}
/**
* 计算指定圆盘在指定柱子上的下一个目标柱子
*/
public int getTargetPeg(int disk, int fromPeg, int n) {
// 移动方向由 (disk + n) 的奇偶性决定
boolean clockwise = ((disk + n) % 2) == 0;
// clockwise: 0->1->2->0 (A->B->C->A)
// counter-clockwise: 0->2->1->0 (A->C->B->A)
if (clockwise) {
return (fromPeg + 1) % 3;
} else {
return (fromPeg + 2) % 3; // 等价于 (fromPeg - 1 + 3) % 3
}
}
/**
* 直接计算第k步的完整移动信息，无需模拟
* 这是位运算解法最强大的特性：O(1)时间回答任意步骤的查询
*/
public Move getMoveAtStep(int n, int k) {
int disk = getDiskAtStep(n, k);
// 计算第k步时该圆盘所在的柱子
// 利用：圆盘d每 2^d 步移动一次
int moveCount = (k - 1) / (1 << disk) + 1; // 这是该圆盘的第几次移动
int startPeg = 0; // 所有圆盘初始在A柱
boolean clockwise = ((disk + n) % 2) == 0;
int fromPeg, toPeg;
if (clockwise) {
fromPeg = (startPeg + (moveCount - 1)) % 3;
toPeg = (fromPeg + 1) % 3;
} else {
fromPeg = (startPeg + 3 - (moveCount - 1) % 3) % 3;
toPeg = (fromPeg + 2) % 3;
}
char[] pegNames = {'A', 'B', 'C'};
return new Move(disk, pegNames[fromPeg], pegNames[toPeg]);
}
/**
* 批量验证：对比位运算解法和递归解法的输出一致性
*/
public boolean verifyAgainstRecursive(int n) {
RecursiveSolver recursive = new RecursiveSolver();
List<Move> recursiveMoves = recursive.solve(n);
List<Move> bitwiseMoves = solve(n);
if (recursiveMoves.size() != bitwiseMoves.size()) return false;
for (int i = 0; i < recursiveMoves.size(); i++) {
Move r = recursiveMoves.get(i);
Move b = bitwiseMoves.get(i);
if (r.disk != b.disk || r.from != b.from || r.to != b.to) {
return false;
}
}
return true;
}
}
Main.java — 演示与验证
import graycode.GrayCodeGenerator;
import hanoi.*;
import java.util.List;
public class Main {
public static void main(String[] args) {
int n = 4; // 测试4个圆盘
System.out.println("=== 汉诺塔格雷码/位运算求解器演示 ===\n");
// 1. 展示格雷码与汉诺塔的对应关系
System.out.println("1. 格雷码与汉诺塔步的对应关系（n=" + n + "）：");
GrayCodeGenerator gen = new GrayCodeGenerator(n);
List<Integer> grayCodes = gen.generateAll();
List<Integer> bitChanges = gen.getBitChangePositions();
System.out.println(" 步数k | 格雷码G(k) | G(k)^G(k-1) | 变化位 | 移动圆盘");
System.out.println(" ------------------------------------------------");
for (int k = 1; k <= bitChanges.size() && k <= 8; k++) {
int gk = grayCodes.get(k);
int gk_1 = grayCodes.get(k - 1);
int diff = gk ^ gk_1;
int bitPos = bitChanges.get(k - 1);
System.out.printf(" %3d | %6s | %6s | %d | %d%n",
k, gen.toBinaryString(gk), gen.toBinaryString(diff), bitPos, bitPos + 1);
}
if (bitChanges.size() > 8) {
System.out.println(" ... (共" + bitChanges.size() + "步)");
}
// 2. 位运算直接计算第k步
System.out.println("\n2. 位运算直接计算第k步（无需前驱步骤）：");
BitwiseSolver bitwise = new BitwiseSolver();
for (int k = 1; k <= 7; k++) {
int disk = bitwise.getDiskAtStep(n, k);
HanoiSolver.Move move = bitwise.getMoveAtStep(n, k);
System.out.printf(" 第%d步: 圆盘%d (ctz(%d)=%d+1) → %s%n",
k, disk, k, disk - 1, move);
}
// 3. 三种解法的输出对比与验证
System.out.println("\n3. 三种解法输出对比（n=" + n + "）：");
RecursiveSolver recursive = new RecursiveSolver();
GrayCodeSolver graySolver = new GrayCodeSolver();
List<HanoiSolver.Move> rMoves = recursive.solve(n);
List<HanoiSolver.Move> gMoves = graySolver.solve(n);
List<HanoiSolver.Move> bMoves = bitwise.solve(n);
System.out.println(" 递归法步骤数: " + rMoves.size());
System.out.println(" 格雷码法步骤数: " + gMoves.size());
System.out.println(" 位运算法步骤数: " + bMoves.size());
// 验证一致性
boolean consistent = bitwise.verifyAgainstRecursive(n);
System.out.println(" 位运算 vs 递归验证: " + (consistent ? "通过" : "失败"));
// 4. 打印完整移动序列
System.out.println("\n4. 位运算法完整移动序列：");
for (int i = 0; i < bMoves.size(); i++) {
System.out.println(" " + (i + 1) + ". " + bMoves.get(i));
}
// 5. 性能对比
System.out.println("\n5. 性能对比（n=20）：");
int testN = 20;
long start = System.nanoTime();
// 只计算第100万步，不生成全部序列
int disk = bitwise.getDiskAtStep(testN, 1_000_000);
long bitwiseTime = System.nanoTime() - start;
System.out.println(" 位运算直接查询第1,000,000步: " + bitwiseTime / 1000 + " μs");
System.out.println(" 结果: 移动圆盘" + disk);
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 第k步查询 | 特点 |
|---|---|---|---|---|
| 递归分治 | O(2ⁿ) | O(n)栈空间 | O(2ⁿ)需全模拟 | 代码最简洁 |
| 格雷码映射 | O(2ⁿ) | O(2ⁿ) | O(1)数学公式 | 揭示数学本质 |
| 纯位运算 | O(2ⁿ) | O(n) | O(1) | 最优实现，无额外空间 |
总结
本文从格雷码与汉诺塔的同构关系出发，推导出纯位运算的O(1)步骤查询算法。其核心洞察包括：
- 同构映射：n盘汉诺塔的最优解与n位格雷码的生成序列一一对应
- ctz定理：第k步移动的圆盘编号等于
Integer.numberOfTrailingZeros(k) + 1 - 方向公式：移动方向由
(disk + n) % 2的奇偶性唯一确定
该解法的独特价值在于能够直接计算任意步骤的内容而无需模拟前面所有步骤，这在需要”跳转到第k步”或”分布式并行验证”的场景中具有不可替代的优势。同时，它也展示了位运算在算法优化中的强大威力——将看似需要遍历的问题转化为纯数学公式。
