汉诺塔问题简述:有三根柱子,编号分别为a,b,c,a柱子自下而上、由大到小按顺序放置n个圆盘,实现将a柱上的圆盘全部移到c柱上,并仍保持原有顺序叠好。移动规则:每次只能移动一个圆盘,并且在移动过程中三根柱上都始终保持大盘在下,小盘在上,移动过程中圆盘可以置于a,b,c任一根柱子上。
解题思想:
(1)以c柱为中介,先将n-1个圆盘按规则从a柱移动到b柱上;
(2)将最底层的圆盘移动到c柱上;
(3)以a柱为中介,将b柱上的n-1个圆盘按规则移动到c柱上。
c语言简单实现如下:
#include <stdio.h>void main(){ void move(char, char);//移动盘子 void TowerOfHanoi(int, char, char, char);//汉诺塔函数 int n; char t1 = 'a', t2 = 'b', t3 = 'c'; printf("input the number of plates:"); scanf("%d", &n); printf("the results are as follows:n"); TowerOfHanoi(n, t1, t2, t3);}void TowerOfHanoi(int m, char t1, char t2, char t3){ //圆盘数目m,圆柱 t1,t2,t3 void move(char x, char y); if(m == 1) move(t1, t3); else { TowerOfHanoi(m-1, t1, t3, t2);//将m-1个圆盘从t1移动到t2 move(t1, t3);//将最底层的圆盘移动到t3 TowerOfHanoi(m-1, t2, t1, t3); //将m-1个圆盘从t2移动到t3 } }void move(char x, char y){ printf("%c-->%cn", x, y);}运行结果(以圆盘数目1,2,3为例):