大家好,我是贤弟!
什么是汉诺塔问题?分别以递归、循环、函数3 种方式,用C语言实现汉诺问题
汉诺塔问题是在三根柱子A、B、C上,把n个大小不同的圆盘从A移到C,每次只能移动一个圆盘,且大圆盘不能叠在小圆盘上面。求移动最少的步数。
以下是三种方式的实现:
一、递归方式实现汉诺塔问题:
#include void hanoi(int n,char start,char temp,char end){ if(n==1) printf("%c->%c\n",start,end); else{ hanoi(n-1,start,end,temp); printf("%c->%c\n",start,end); hanoi(n-1,temp,start,end); }}int main(){ int n; printf("请输入圆盘数:"); scanf("%d",&n); hanoi(n,'A','B','C'); return 0;}
二、循环方式实现汉诺塔问题:
#includeint stack[100000][3];int top=-1;void push(int a,int b,int c){ top++; stack[top][0]=a; stack[top][1]=b; stack[top][2]=c;}void pop(int *a,int *b,int *c){ *a=stack[top][0]; *b=stack[top][1]; *c=stack[top][2]; top--;}void print(int i,char start,char end){ printf("第%d步: %c --> %c\n",i,start,end);}void hanoi(int n,char start,char end,char temp){ int a,b,c; push(n,start,end); int i=1; while(top>=0) { pop(&a,&b,&c); if(a==1) print(i++,b,c); else { push(a-1,b,temp); push(1,b,c); push(a-1,temp,c); } }}int main(){ int n; printf("请输入汉诺塔层数: "); scanf("%d",&n); hanoi(n,'A','C','B'); return 0;}
三、函数方式实现汉诺塔问题:
#include void Move(char ch1,char ch2){ printf("%c->%c\n",ch1,ch2);}void Hanoi(int n,char a,char b,char c){ if(n==1) Move(a,c); else{ Hanoi(n-1,a,c,b); Move(a,c); Hanoi(n-1,b,a,c); }}int main(){ int n; printf("请输入圆盘数:"); scanf("%d",&n); Hanoi(n,'A','B','C'); return 0;}
领取专属 10元无门槛券
私享最新 技术干货