void hanoi(int k,char a,char b,char c)
{if(k==1) printf("%c ->%c",a,c);//1else{hanoi(k-1,a,c,b);//2printf("%c ->%c",a,c);//3hanoi(k-1,b,a,c);//3}//4
}
此处1 2 3 4与上述递归代码注释1 2 3 4等价,那我们用一个栈记录数据和状态即可。
#include
#includetypedef struct funState{int k;//待处理数量char a,b,c;//a是起始柱,b是辅助,c是目标柱子int tag;//见状态分析
}fs;
typedef fs *fsp;int i=-1;//每个i指向存数据的位置,-1为空栈
fsp stk[16];//栈的初始化void pushFsp(int k,char a,char b,char c){stk[++i]=(fsp)malloc(sizeof(fsp));//栈顶上移stk[i]->k=k;//待处理数量stk[i]->a=a,stk[i]->b=b,stk[i]->c=c;//迁跃情况stk[i]->tag=(k==1?1:2);//所进入的状态
}
void popFsp(){free(&stk[i]);//注意释放栈空间i--;//出掉当前栈顶if(i!=-1) stk[i]->tag++;//新栈顶的状态改变
}int main()
{int n;scanf("%d",&n);pushFsp(n,'a','b','c');while (i>=0){if(stk[i]->tag==1)//出口:出到3或4{printf("%c -> %c\n",stk[i]->a,stk[i]->c);popFsp();} else if(stk[i]->tag==2)//入口:入到1或2{pushFsp(stk[i]->k-1,stk[i]->a,stk[i]->c,stk[i]->b);}else if(stk[i]->tag==3)//入口:入到1或2{printf("%c -> %c\n",stk[i]->a,stk[i]->c);pushFsp(stk[i]->k-1,stk[i]->b,stk[i]->a,stk[i]->c);}else if(stk[i]->tag==4)//出口:出到3或4{popFsp();}}return 0;
}