汉诺塔:
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。上帝创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
设柱子为:ABC;把n个盘从A移动到C。先把顶上的n-1个盘从A移动到B,再把地下的1个盘从A移动到C,最后同理把n-1个盘从B移到C,ok。当n==1 时,直接把盘子从A移动到C。
int step = 0;//记录移动次数
void hanno(int n, char src, char mid, char des)
{
if (n == 1) {
step++;
printf("%c -> %c\n", src, des);
return ;
}
hanno(n-1, src, des, mid);
hanno(1, src, mid, des);
hanno(n-1, mid, src, des);
return ;
}
问题解决。
n个盘子,总共移动步数为2^n - 1步。
阅读(1264) | 评论(0) | 转发(0) |