c++解决汉诺塔问题
时间: 2023-12-02 15:40:57 浏览: 30
以下是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;
}
```