汉诺塔问题递归与非递归实现

汉诺塔问题描述

• 问题：有三根柱子（A、B、C）和若干个不同大小的盘子，最初所有盘子都在柱子 A 上，按大小顺序从上到下排列。目标是将所有盘子移动到柱子 C 上，遵循以下规则：
  1. 每次只能移动一个盘子。
  2. 不能将较大的盘子放在较小的盘子上。
  3. 需要使用辅助柱子 B。

递归解决方案

汉诺塔问题的解决方案可以通过递归来实现，具体步骤如下：

1. 基本情况：如果只有一个盘子，直接将其从源柱子 A 移动到目标柱子 C。
2. 递归步骤：
   • 将上面的 n−1个盘子从 A 移动到辅助柱子 B（使用 C 作为辅助）。
   • 将第 n个盘子直接从 A 移动到 C。
   • 将 n−1个盘子从 B 移动到 C（使用 A 作为辅助）。

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>// 汉诺塔递归函数
void hanoi(int n, char A, char B, char C)
{if (n == 1){printf("将盘子 1 从 %c 移动到 %c\n", A, C);return;}// 将 n-1 个盘子从 A 移动到 B，使用 C 作为辅助hanoi(n - 1, A, C, B);// 将第 n 个盘子从 A 移动到 Cprintf("将盘子 %d 从 %c 移动到 %c\n", n, A, C);// 将 n-1 个盘子从 B 移动到 C，使用 A 作为辅助hanoi(n - 1, B, A, C);
}int main()
{int n;printf("请输入盘子个数：");scanf("%d", &n);// 从 A 移动到 C，使用 B 作为辅助hanoi(n, 'A', 'B', 'C');return 0;
}

调用过程示例

假设我们有 3 个盘子，调用 hanoi(3, 'A', 'B', 'C')。

hanoi(3, A, B, C)
├── hanoi(2, A, C, B)
│   ├── hanoi(1, A, B, C)
│   │   └── 打印: 将盘子 1 从 A 移动到 C
│   ├── 打印: 将盘子 2 从 A 移动到 B
│   └── hanoi(1, C, A, B)
│       └── 打印: 将盘子 1 从 C 移动到 B
├── 打印: 将盘子 3 从 A 移动到 C
└── hanoi(2, B, A, C)├── hanoi(1, B, C, A)│   └── 打印: 将盘子 1 从 B 移动到 A├── 打印: 将盘子 2 从 B 移动到 C└── hanoi(1, A, B, C)└── 打印: 将盘子 1 从 A 移动到 C

输出：

请输入盘子个数：3
将盘子 1 从 A 移动到 C
将盘子 2 从 A 移动到 B
将盘子 1 从 C 移动到 B
将盘子 3 从 A 移动到 C
将盘子 1 从 B 移动到 A
将盘子 2 从 B 移动到 C
将盘子 1 从 A 移动到 C

非递归解决方案

虽然递归是直观的，但在某些情况下，非递归解决方案可能更高效。

对于 n个盘子的汉诺塔问题，移动盘子最少次数为 2^n−1。

汉诺塔移动的基本规则

在汉诺塔中，盘子只能一个一个地移动，且较大的盘子不能放在较小的盘子上。

1. 目标：将所有盘子从源柱子（A）移动到目标柱子（C），使用辅助柱子（B）。
2. 移动的奇偶性：移动的顺序依赖于盘子的数量 n 的奇偶性。
    

3. 偶数盘子：当盘子的数量为偶数时，交换辅助柱子 B 和目标柱子 C 是必要的。这是因为在偶数情况下，最后一个盘子的移动需要在辅助柱子和目标柱子之间进行调整。

4. 奇数盘子：当盘子的数量为奇数时，移动的顺序则是直接按照汉诺塔的标准规则进行，不需要交换柱子。在这种情况下，移动的顺序会自然按照规则完成，确保每个盘子都能正确地从源柱子 A 移动到目标柱子 C，而无需进行柱子的交换。

如果盘子数量为偶数，交换辅助柱子 B 和目标柱子 C，以确保移动顺序正确。

在汉诺塔问题中，有三个柱子（A、B、C），需要将盘子从源柱子移动到目标柱子。非递归的实现中，可以通过循环来控制移动的顺序。这里的关键在于使用 % 运算符来决定每一步的移动。

代码解析

// 确定源柱子与目标柱子
if (i % 3 == 1) 
{from = A; to = C; // 第一步：A → C
}
else if (i % 3 == 2) 
{from = A; to = B; // 第二步：A → B
}
else 
{from = B; to = C; // 第三步：B → C
}

这里第三步看着像错误的，其实不是，因为只是赋值并没移动，后面这是在栈保证大小顺序的情况下才进行移动的。

逻辑解释

1. i 的角色：

   • i 是当前的移动步骤，从 1 到 2^n−1。
   • 每一个步骤代表着一个盘子的移动。

2. i % 3 的使用：

   • 使用 % 运算符是为了实现循环和定期的移动模式。结果可能是 0、1 或 2。

3. 具体移动：

   • i % 3 == 1：
     • 当 i 能被 3 取余为 1 时，这表示是第一个移动。
     • 将盘子从柱子 A 移动到柱子 C。
     • 这是因为在第 1 步，最小的盘子应该从源柱子直接移动到目标柱子。
   • i % 3 == 2：
     • 当 i 能被 3 取余为 2 时，表示是第二个移动。
     • 将盘子从柱子 A 移动到柱子 B。
     • 这通常是将一个较大的盘子暂时放到辅助柱子，以便后续的移动操作。
   • i % 3 == 0：
     • 当 i 能被 3 取余为 0 时，表示是第三个移动。
     • 将盘子从柱子 B 移动到柱子 C。
     • 这一步通常是将之前放在辅助柱子上的盘子移动到目标柱子。

#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>// 模拟栈结构
typedef struct
{int data[64]; // 最多支持64个盘子int top;      // 栈顶指针
} Stack;// 初始化栈
void initStack(Stack* s)
{s->top = -1; // 栈顶指针初始化为-1，表示栈为空
}// 入栈操作
void push(Stack* s, int x)
{s->data[++s->top] = x; // 将元素x压入栈中，并更新栈顶指针
}// 出栈操作
int pop(Stack* s)
{return s->data[s->top--]; // 返回栈顶元素，并更新栈顶指针
}// 判断栈是否为空
int isEmpty(Stack* s)
{return s->top == -1; // 如果栈顶指针为-1，表示栈为空
}// 获取栈顶元素
int getTop(Stack* s)
{return s->data[s->top]; // 返回栈顶元素
}// 汉诺塔非递归实现
void hanoi_iterative(int n, char A, char B, char C)
{Stack a, b, c; // 定义三个栈，分别表示柱子A、B、CinitStack(&a); // 初始化栈AinitStack(&b); // 初始化栈BinitStack(&c); // 初始化栈C// 初始化A柱子上的盘子，从大到小压入栈中for (int i = n; i >= 1; i--){push(&a, i);}int total_moves = (1 << n) - 1; // 计算总移动次数，2^n - 1// 如果盘子数量为偶数，交换B和C柱子if (n % 2 == 0){char temp = B; // 临时变量存储BB = C;         // B赋值为CC = temp;     // C赋值为B}// 遍历所有移动操作for (int i = 1; i <= total_moves; i++){char from, to;// 确定源柱子与目标柱子if (i % 3 == 1){from = A; to = C; // 第一步：A → C}else if (i % 3 == 2){from = A; to = B; // 第二步：A → B}else{from = B; to = C; // 第三步：B → C}// 确定对应的栈Stack* fromStack, * toStack;if (from == A) fromStack = &a; // 根据源柱子选择栈else if (from == B) fromStack = &b;else fromStack = &c;if (to == A) toStack = &a; // 根据目标柱子选择栈else if (to == B) toStack = &b;else toStack = &c;// 确保从小盘子移动到大盘子if (!isEmpty(fromStack) && (isEmpty(toStack) || getTop(fromStack) < getTop(toStack))){// 从源柱子移动到目标柱子int disk = pop(fromStack); // 从源栈中弹出盘子push(toStack, disk);       // 将盘子压入目标栈printf("将盘子%d从 %c 移动到 %c\n", disk, from, to);}else{// 如果目标柱子有盘子，反向移动int disk = pop(toStack); // 从目标栈中弹出盘子push(fromStack, disk);   // 将盘子压入源栈printf("将盘子%d从 %c 移动到 %c\n", disk, to, from);}}
}int main()
{int n;printf("请输入盘子个数：");scanf("%d", &n); // 用户输入盘子数量hanoi_iterative(n, 'A', 'B', 'C'); // 调用非递归汉诺塔函数return 0; // 返回0，表示程序成功结束
}

输出：

请输入盘子个数：3
将盘子1从 A 移动到 C
将盘子2从 A 移动到 B
将盘子1从 C 移动到 B
将盘子3从 A 移动到 C
将盘子1从 B 移动到 A
将盘子2从 B 移动到 C
将盘子1从 A 移动到 C

跟上面递归的输出一样

总结：

递归实现：

特点

• 简洁性：代码简洁易读，直接表达了问题的递归性质。
• 直观：递归调用自然地描述了移动过程。

优点

• 逻辑清晰，易于理解和实现。
• 适合较小规模的盘子。

缺点

• 对于较大的盘子，递归深度可能导致栈溢出。
• 空间复杂度较高，主要是由于函数调用栈。

非递归实现

特点

• 使用栈：通过栈模拟柱子的行为，实现非递归的移动。
• 循环控制：使用循环而非递归，避免了栈溢出的问题。

优点

• 能处理更大规模的盘子，避免了递归深度限制。
• 空间复杂度更低。

缺点

• 代码相对复杂，需要手动管理栈的状态。
• 理解上可能不如递归直观。

汉诺塔问题的时间复杂度

        汉诺塔问题的时间复杂度是 指数级 的，具体为 O(2^n)，这意味着随着盘子数量 n 的增加，所需的时间将指数级增加。这也是为什么在实际应用中，处理较大数量的盘子（如 64 个盘子）是不可行的。