用栈替代递归
#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
//非递归解法
struct problem{
int n;
char src, mid, dest;
problem(int nn, char s, char m, char d) :n(nn), src(s), mid(m), dest(d){
}
};
stack<problem>stk;
//递归解法
void Hanoi(int n, char src, char mid, char dest){
if (n == 1){
cout << src << "->" << dest << endl;
return;
}
Hanoi(n - 1, src, dest, mid);
cout << src << "->" << dest << endl;
Hanoi(n - 1, mid, src, dest);
return;
}
int main(){
int n;
cin >> n;
cout << "Recursion:" << endl;
stk.push(problem(n, 'A', 'B', 'C'));
while (!stk.empty()){//栈不为空
problem curPrb = stk.top(); //获取最上层问题
stk.pop();//出栈
if (curPrb.n == 1)cout << curPrb.src << "->" << curPrb.dest << endl;
else
{
//分解子问题
//放入第三个问题
stk.push(problem(curPrb.n - 1, curPrb.mid, curPrb.src, curPrb.dest));
//放入第二个问题
stk.push(problem(1, curPrb.src, curPrb.mid, curPrb.dest));
//放入第一个问题
stk.push(problem(curPrb.n - 1, curPrb.src, curPrb.dest, curPrb.mid));
}
}
cout << "Non-Recursion:" << endl;
Hanoi(n, 'A', 'B', 'C');
return 0;
}
