这是一个古典的数学问题,是一个只有用递归方法解决的问题。问题是这样的:古代有一个梵塔,塔内有3个座A,B,C,开始时A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个老和尚想把这64个盘子从A座移到B座,但每次只允许移动一个盘,且在移动过程中在3个座上都始终保持大盘在下,小盘在上。在移动过程中可以利用C座。要求编程打印出移动的步骤。
其目的是让A中的盘子通过C全部移动到B上面,A为起始,B为终止,C是中转。其中设计到了递归思想,首先写一段打印代码
void move(char pos1,char pos2)
{printf("%c->%c\n",pos1,pos2);
}
目的是等下在递归中频繁调用打印操作,从而建去了一系列的操作。
其次是实现核心代码,
void Hanoi(int n,char pos1,char pos2,char pos3)
{if(n==1){move(pos1,pos2);}else{Hanoi(n-1,pos1,pos3,pos2);move(pos1,pos2);Hanoi(n-1,pos3,pos2,pos1);}
}
这里只针对汉诺塔进行分析,详细递归还需大家慢慢积累,
首先定义n个盘子,pos1为起止地,POS3为中转地,POS2为目标地,递归是有结束条件的,结束的条件就是最后一个盘子从起止地挪到目标地,用代码实现就是move(pos1,pos2),当n不等于1时,程序进入其他选项,根据顺序要把第一个盘子先挪到目标地,要挪到最底下的盘子就要先挪动上面的n-1个盘子,将他们从pos1起始挪到pos3中转,然后最低下的盘子可以从pos1挪到pos2了,就调用move这个函数,当把最底下的盘子挪了之后,就又要将序最底下序号n-1个盘子以pos3为起止,然后以pos1为中转,挪到到pos2目标,依次类推,一个汉诺塔的递归就实现了,最后是源代码。
#include<stdio.h>
void move(char pos1,char pos2)
{printf("%c->%c\n",pos1,pos2);
}
void Hanoi(int n,char pos1,char pos2,char pos3)
{if(n==1){move(pos1,pos2);}else{Hanoi(n-1,pos1,pos3,pos2);move(pos1,pos2);Hanoi(n-1,pos3,pos2,pos1);}
}
int main()
{int a;scanf("%d",&a);Hanoi(a,'A','B','C');
}