C++汉诺塔问题解决代码
时间: 2023-03-16 19:43:59 浏览: 80
汉诺塔问题的解决方案是使用递归算法。下面是一个具体的实现:
def hanoi(n, a, b, c):
if n == 1:
print(a, '-->', c)
else:
hanoi(n-1, a, c, b)
print(a, '-->', c)
hanoi(n-1, b, a, c)
hanoi(3, 'A', 'B', 'C')
相关问题
汉诺塔问题c++代码
下面是汉诺塔问题的递归解法的 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
void hanoi(int n, char a, char b, char c) {
if (n == 1) {
cout << "Move disk " << n << " from " << a << " to " << c << endl;
} else {
hanoi(n-1, a, c, b);
cout << "Move disk " << n << " from " << a << " to " << c << endl;
hanoi(n-1, b, a, c);
}
}
int main() {
int n;
cout << "Enter the number of disks: ";
cin >> n;
hanoi(n, 'A', 'B', 'C');
return 0;
}
```
其中,`hanoi` 函数用于解决汉诺塔问题,参数 `n` 表示当前需要移动的盘子数目,`a`、`b` 和 `c` 分别表示三个柱子的名称。
当只有一个盘子时,直接将它从 `a` 移动到 `c` 即可。否则,先将 `n-1` 个盘子从起始柱子 `a` 移动到辅助柱子 `b`,再将最后一个盘子从 `a` 移动到 `c`,最后将 `n-1` 个盘子从 `b` 移动到 `c`。
在 `main` 函数中,用户需要输入需要移动的盘子数,然后调用 `hanoi` 函数进行求解。
c++解决汉诺塔问题
以下是C++递归和迭代两种解决汉诺塔问题的代码:
递归解法:
```c++
#include <iostream>
using namespace std;
void hanoi(int n, char A, char B, char C) {
if (n == 1) {
cout << "Move disk " << n << " from " << A << " to " << C << endl;
} else {
hanoi(n - 1, A, C, B);
cout << "Move disk " << n << " from " << A << " to " << C << endl;
hanoi(n - 1, B, A, C);
}
}
int main() {
int n;
cout << "Enter the number of disks: ";
cin >> n;
hanoi(n, 'A', 'B', 'C');
return 0;
}
```
迭代解法:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct Move {
int n;
char from, to, via;
Move(int n, char from, char to, char via) : n(n), from(from), to(to), via(via) {}
};
void hanoi(int n, char A, char B, char C) {
stack<Move> s;
s.push(Move(n, A, C, B));
while (!s.empty()) {
Move m = s.top();
s.pop();
if (m.n == 1) {
cout << "Move disk " << m.n << " from " << m.from << " to " << m.to << endl;
} else {
s.push(Move(m.n - 1, m.via, m.to, m.from));
s.push(Move(1, m.from, m.to, m.via));
s.push(Move(m.n - 1, m.from, m.via, m.to));
}
}
}
int main() {
int n;
cout << "Enter the number of disks: ";
cin >> n;
hanoi(n, 'A', 'B', 'C');
return 0;
}
```