汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
故事导入,开始正文
我们自己先玩三个会发现,都会有一个步骤是,最大的在原地,目标的杆子没有盘,中间暂存的盘子有从小到大的盘子,那么将最大的盘子移动到目标杆子上后,此时他的塔可以看作和上一层塔,(假如原先4层,这一步后就可以将它看作为三层),换句话说他就是可以将一个大问题,转换成小问题。
void move(char pos1,char pos2){ printf("%c->%c\n",pos1,pos2); } void hanoita(int n,char pos1,char pos2,char pos3){ if(n==1) move(pos1,pos3); //将初始的只有一个盘子,移动到目标杆子 else{ hanoita(n-1,pos1,pos3,pos2); move(pos1,pos3); hanoita(n-1,pos2,pos1,pos3); } } int main () { int n=0 ; char a='A'; char b='B'; char c='C'; scanf("%d",&n); hanoita(n,a,b,c); return 0; }
所以,上面的那个就相当于输出移动的盘子名,,下面的是遍历一层一层将它剥开