网络知识 娱乐 c语言汉诺Hanoi塔

c语言汉诺Hanoi塔

题目要求:

一块板上有三根针,A,B,C。A针上套有64个大小不等的圆盘,大的在下,小的在上。如下图所示。要把这64个圆盘从A针移动C针上,每次只能移动一个圆盘,移动可以借助B针进行。但在任何时候,任何针上的圆盘都必须保持大盘在下,小盘在上。求移动的步骤。

这是一道非常经典的数学题和程序算法题,上学期间老师讲解数学归纳法,通过等比数列可行运行次数的规律是-1。若我们用编程的方式去解决汉诺塔,采用递归算法完成,并且记录执行的顺序,请看如下代码。


c语言汉诺Hanoi塔

Hanoi塔示意图

#include <stdio.h>n#include <math.h>nstatic unsigned long number=0;//搬运次数nnmove(int n,char x,char y,char z)n{n if(n==1)nt{ nt number++;n printf("%c-->%cn",x,z); nt}n elsen {n move(n-1,x,z,y); // A C Bnt printf("%c-->%cn",x,z);n move(n-1,y,x,z); // B A Cnt number++;n }n}nint main(void) n{ n int n;ntunsigned long sum;n printf("input diskes number:n");n scanf("%d",&n);tttttt/*输入盘子数目n*/n printf("The step to moving %d diskes:n",n);n move(n,'A','B','C');tttt/*递归调用move(),求解盘子的搬运过程*/ntprintf("Handling times=%drn",number);//搬移次数nt//printf("n=%dn",n);ntsum=pow(2,n)-1;ntprintf("Handling times=%drn",sum);//搬移次数n getche();n return 0;n}n

运行结果:

c语言汉诺Hanoi塔

运行结果