7-17 汉诺塔的非递归实现

输入样例:

3

输出样例:

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

分析：

不会汉罗塔的uu们，先看看图解：

                   

非递归代码：

#include<iostream>
#include<stack>
using namespace std;
struct node{char a,b,c;int d;
};
stack<node>st;
int main(){int n; cin>>n;st.push({'a','b','c',n});while(st.size()){node x=st.top(); st.pop();if(x.d==1) printf("%c -> %c\n",x.a,x.c);else st.push({x.b,x.a,x.c,x.d-1}),st.push({x.a,x.b,x.c,1}),st.push({x.a,x.c,x.b,x.d-1});}return 0;
}

 递归代码：

#include<iostream>
using namespace std;
void dfs(char a,char b,char c,int n){if(n==1){printf("%c -> %c\n",a,c); return;}dfs(a,c,b,n-1);dfs(a,b,c,1);dfs(b,a,c,n-1);
}
int main(){int n; cin>>n;dfs('a','b','c',n);return 0;
}