c++中 使用递归算法解决汉诺塔问题,并输出移动的步数。代码
时间: 2024-09-10 18:17:52 浏览: 61
C++基于递归算法解决汉诺塔问题与树的遍历功能示例
5星 · 资源好评率100%
在C++中,汉诺塔是一个经典的递归问题。它涉及到将一堆盘子从一个柱子移动到另一个柱子,遵守规则:每次只能移动一个大盘子,而且大盘子不能放在小盘子之上。以下是使用递归解决汉诺塔问题并计算步骤的C++代码示例:
```cpp
#include <iostream>
// 定义函数,三个参数分别为源柱、目标柱和剩余盘子的数量
void hanoi(int n, char fromRod, char toRod, char auxRod) {
if (n > 0) { // 如果有盘子
// 首先移动n-1个盘子到辅助柱
hanoi(n - 1, fromRod, auxRod, toRod);
// 然后把最大的盘子直接移动到目标柱
std::cout << "Move disk " << n << " from rod " << fromRod << " to rod " << toRod << std::endl;
// 最后,把n-1个盘子从辅助柱移动到目标柱
hanoi(n - 1, auxRod, toRod, fromRod); // 递归回溯
}
}
int main() {
int numDisks = 3; // 指定开始时有3个盘子
hanoi(numDisks, 'A', 'C', 'B'); // A代表起始柱,C代表目标柱,B代表辅助柱
return 0;
}
```
当运行此程序时,它会按照汉诺塔的规则移动盘子,并在控制台输出每一步的操作。注意递归过程中总共移动的步数是2^n - 1,其中n是盘子的数量。
阅读全文