锐客网

  1. 首页 > 生活百科 > it技术 > >

汉诺塔c语言主函数验证 c语言解决汉诺塔程序代码

IT技术圆盘

c语言证明汉诺塔次数公式c语言证明汉诺塔次数公式：f(k 1）=2*f(k) 1来计算 。
#includestdio.h
usingnamespacestd
#defineMOD1000000
longlongcal（longlonga，intn，intm）
longlongans=1
a=a%m
while（n）
ans=（ans*a）%m
n=n1
a=（a*a）%m；//
returnans；
intmain（void）
intn，i ， m，ans
scanf（"%d"，n）
while（n——）
scanf（"%d"，m）
printf（"%lld\n"，cal（2，m，MOD）-1）
return0
分析
来说明一个现象，假如A柱子上有两个大小相同的盘子 ， 上面一个是黑色的，下面一个是白色的 ， 我们把两个盘子移动到B上，需要两次 ， 盘子顺序将变成黑的在下，白的在上，然后再把B上的盘子移动到C上，需要两次 ， 盘子顺序将与A上时相同，由此我们归纳出当相邻两个盘子都移动偶数次时，盘子顺序将不变，否则上下颠倒 。
c语言汉诺塔递归原理简单明了：
先把上面的n-1个金片从第1个针移动到第2个针
再把最下面的那个（第N个）从第1个针移到目标第3个针上
现在问题变为把n-1个从第2针移到第3针
先把上面的n-2个金片从第2个针移动到第1个针
再把最下面的那个（的N-1个）从第2个针移到目标第3个针上
void move( char x, char y )
{
printf( "%c --- %c\n", x, y ); /* 打印步骤 从 x 移动到 y */
}
/* 把 one 上 n 个 经过 two 移动到three */
void hanoi( int n, char one, char two, char three )
{
if ( n == 1 ) move( one , three ); /* 剩下最后一个，移动打印步骤 */
else
{
hanoi( n - 1, one , three, two ); /* 把 one 上 n-1 个 经过 three 移动到two */
move( one, three );/* 最下面的那个移动从one到three */
hanoi( n - 1, two, one, three );/* 把 two 上 n－1 个 经过 one 移动到three */
}
}
void main()
{
int n;
printf("Input N=");
scanf("%d", n);
hanoi(n, '1', '2', '3');
printf("Press any key to exit!\n");
getch();
}
N=3时
(123 0 0)
1 --- 3 (23 0 1)
1 --- 2 (3 2 1)
3 --- 2 (3 12 0)
1 --- 3 (0 12 3) /*这里完成把最后一个从1移到了3*/
2 --- 1 (1 2 3)
2 --- 3 (1 0 23)
1 --- 3 (0 0 123)
在C语言中用函数编写汉诺塔*问题分析与算法设计
这是一个著名的问题，几乎所有的教材上都有这个问题 。由于条件是一次只能移动一个盘 ， 且不允许大盘放在小盘上面，所以64个盘的移动次数是汉诺塔c语言主函数验证：
18，446，744，073，709，551，615
这是一个天文数字 ， 若每一微秒可能计算(并不输出)一次移动 ， 那么也需要几乎一百万年 。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔 。
分析问题，找出移动盘子的正确算法 。
首先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了：
*将上面的63个盘子移到b杆上汉诺塔c语言主函数验证；
*将a杆上剩下的盘子移到c杆上；
*将b杆上的全部盘子移到c杆上 。
将这个过程继续下去 ， 就是要先完成移动63个盘子、62个盘子、61个盘子....的工作 。
为了更清楚地描述算法，可以定义一个函数movedisc(n,a,b,c) 。该函数的功能是：将N个盘子从A杆上借助C杆移动到B杆上 。这样移动N个盘子的工作就可以按照以下过程进行：
1) movedisc(n-1,a,c,b);
2) 将一个盘子从a移动到b上；
3) movedisc(n-1,c,b,a)；
重复以上过程 ， 直到将全部的盘子移动到位时为止 。
*程序与程序注释
#includestdio.h
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",n); /*输入N值*/
printf("\tneedle:\ta\t b\t c\n");
movedisc(n,'a','c','b'); /*从A上借助B将N个盘子移动到C上*/
printf("\t Total: %d\n",i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*从fromneedle上借助toneedle将N-1个盘子移动到usingneedle上*/
i;
switch(fromneedle) /*将fromneedle 上的一个盘子移到toneedle上*/
{
case 'a': switch(toneedle)
{
case 'b': printf("\t[%d]:\t-.........-\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t-...............-\n",i,n,n);
break;
}
break;
case 'b': switch(toneedle)
{
case 'a': printf("\t[%d]:\t-...............-\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t -........-\n",i,n,n);
break;
}
break;
case 'c': switch(toneedle)
{
case 'a': printf("\t[%d]:\t-............-\n",i,n,n);
break;
case 'b': printf("\t[%d]:\t-........-\n",i,n,n);
break;
}
break;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*从usingneedle上借助fromneedle将N-1个盘子移动到toneedle上*/
}
}
C语言实验题——汉诺塔【例】Hanoi塔问题
一块板上有三根针，A，B，C 。A针上套有64个大小不等的圆盘，大的在下，小的在上 。如图5.4所示 。要把这64个圆盘从A针移动C针上 ， 每次只能移动一个圆盘，移动可以借助B针进行 。但在任何时候，任何针上的圆盘都必须保持大盘在下 ， 小盘在上 。求移动的步骤 。
本题算法分析如下，设A上有n个盘子 。
如果n=1，则将圆盘从A直接移动到C 。
如果n=2 ， 则：
1.将A上的n-1(等于1)个圆盘移到B上；
2.再将A上的一个圆盘移到C上；
3.最后将B上的n-1(等于1)个圆盘移到C上 。
如果n=3，则：
A. 将A上的n-1(等于2，令其为n`)个圆盘移到B(借助于C)，步骤如下：
(1)将A上的n`-1(等于1)个圆盘移到C上 。
(2)将A上的一个圆盘移到B 。
(3)将C上的n`-1(等于1)个圆盘移到B 。
B. 将A上的一个圆盘移到C 。
C. 将B上的n-1(等于2 ， 令其为n`)个圆盘移到C(借助A)，步骤如下：
(1)将B上的n`-1(等于1)个圆盘移到A 。
(2)将B上的一个盘子移到C 。
(3)将A上的n`-1(等于1)个圆盘移到C 。
到此，完成了三个圆盘的移动过程 。
从上面分析可以看出，当n大于等于2时 ， 移动的过程可分解为三个步骤：
第一步把A上的n-1个圆盘移到B上；
第二步把A上的一个圆盘移到C上；
第三步把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的 。
当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上 ， 这里的n`=n-1 。显然这是一个递归过程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf("%c--%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c--%c\n",x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf("\ninput number:\n");
scanf("%d",h);
printf("the step to moving - diskes:\n",h);
move(h,'a','b','c');
}
从程序中可以看出,move函数是一个递归函数，它有四个形参n,x,y,z 。n表示圆盘数，x,y,z分别表示三根针 。move 函数的功能是把x上的n个圆盘移动到z上 。当n==1时，直接把x上的圆盘移至z上，输出x→z 。如n!=1则分为三步：递归调用move函数，把n-1个圆盘从x移到y；输出x→z；递归调用move函数，把n-1个圆盘从y移到z 。在递归调用过程中n=n-1，故n的值逐次递减，最后n=1时，终止递归，逐层返回 。当n=4 时程序运行的结果为：
input number:
4
the step to moving 4 diskes:
a→b
【汉诺塔c语言主函数验证 c语言解决汉诺塔程序代码】a→c
b→c
a→b
c→a
c→b
a→b
a→c
b→c
b→a
c→a
b→c
a→b
a→c
b→c
关于汉诺塔c语言主函数验证和c语言解决汉诺塔程序代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：远程连接服务器没反应 远程服务器怎么连接失败

    下一篇：ChatGPT题材暂歇的简单介绍