汉诺塔问题——循环算法
时间: 2023-11-07 14:05:51 浏览: 58
汉诺塔问题是一个经典的问题,源于印度一个古老传说。问题是将一根柱子上的64片黄金圆盘按照大小顺序重新摆放到另一根柱子上,且在任何时候,小圆盘上不能放大圆盘,且一次只能移动一个圆盘。
汉诺塔问题的循环算法可以使用迭代的方式来解决。下面是一个示例代码:
```cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;
void hanoiTowerIterative(int N, string from, string to, string help) {
stack<int> s1, s2, s3;
int moves = (1 << N) - 1;
for (int i = N; i > 0; i--) {
s1.push(i);
}
if (N % 2 == 0) {
swap(s2, s3);
}
for (int i = 1; i <= moves; i++) {
if (i % 3 == 1) {
if (s1.empty() || (!s2.empty() && s2.top() < s1.top())) {
cout << "Move " << s2.top() << " from " << to << " to " << from << endl;
s1.push(s2.top());
s2.pop();
} else {
cout << "Move " << s1.top() << " from " << from << " to " << to << endl;
s2.push(s1.top());
s1.pop();
}
} else if (i % 3 == 2) {
if (s1.empty() || (!s3.empty() && s3.top() < s1.top())) {
cout << "Move " << s3.top() << " from " << help << " to " << from << endl;
s1.push(s3.top());
s3.pop();
} else {
cout << "Move " << s1.top() << " from " << from << " to " << help << endl;
s3.push(s1.top());
s1.pop();
}
} else {
if (s2.empty() || (!s3.empty() && s3.top() < s2.top())) {
cout << "Move " << s3.top() << " from " << help << " to " << to << endl;
s2.push(s3.top());
s3.pop();
} else {
cout << "Move " << s2.top() << " from " << to << " to " << help << endl;
s3.push(s2.top());
s2.pop();
}
}
}
}
int main() {
hanoiTowerIterative(3, "A", "B", "C");
return 0;
}
```