利用栈解决汉诺塔问题

利用栈解决汉诺塔问题

#include<iostream> using namespace std; #include<stack>//stl栈模板 #include<string> //定义一个解决汉诺塔的类 class HanNuoTa{ //保存要解决问题的规模与状态 （每一个规模对应一个状态） //当需要解决一个问题时将问题进行压栈 stack<int> m_n; //规模：即碟子的个数 stack<string>m_str;//状态：即从针str[0]借助针str[1]针到针str[2]， // 当问题进行解决时，应该将问题的规模与状态弹出栈 int n;//弹出的规模 string s;//弹出的状态 //辅助变量 char ch; public: //初始化问题 ：需要解决将n个碟子从针a,借助针b,移动到针c。 void init(int n, char ch1 = 'a', char ch2 = 'b', char ch3 = 'c'){ this->n = n; s = "abc"; s[0] = ch1; s[1] = ch2; s[2] = ch3; this->m_n.push(n); this->m_str.push(s); } void move(){ while(this->m_n.size() != 0){ this->func1(); this->func2(); } } //递推函数：若要解决将n个碟子从针a,借助针b,移动到针c。 //那么就得先解决将n-1个碟子从针a,借助针c,移动到针b的问题，将问题压栈。 void func1(){ while(this->m_n.top() > 1){//直到栈顶问题的规模为1才停止压栈。 m_n.push(m_n.top() - 1); s = m_str.top(); ch = s[1]; s[1] = s[2]; s[2] = ch; m_str.push(s); } } //出栈解决问题 void func2(){ //解决栈顶规模为1的问题，将1个碟子从s[0]->s[2]; n = this->m_n.top(); this->m_n.pop(); s = this->m_str.top(); this->m_str.pop(); cout << s[0] << "->" << s[2] << endl; //解决栈顶规模为n(n > 1)的问题, //问题在栈顶，表明已经将s[0]上面（n-1)个碟子从s[0]移动到了s[1], //第一步：把最下面的碟子从s[0]移动到s[2]即可 //第二步：把（n-1)个碟子从s[1]，借助s[0],移动到s[2](将问题入栈) if(m_n.size() != 0){ n = this->m_n.top(); this->m_n.pop(); s = this->m_str.top(); this->m_str.pop(); cout << s[0] << "->" << s[2] << endl; //第一步 //第二步 m_n.push(n-1); ch = s[0]; s[0] = s[1]; s[1] = ch; m_str.push(s); } } }; int main(){ HanNuoTa han; int n = 0; cout << "请输入碟子个数n(将给出n个碟子从a借组b搬运到c的移动步骤)：" << endl; cin >> n; han.init(n); han.move(); return 0; }