首页
登录 | 注册

C语言编程之汉诺塔

汉诺塔游戏
游戏规则:,输入一个数字,代表圆盘数量。然后有3根柱子A,B,C.把圆盘从下面开始按大小顺序重新摆放在A柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。,将A柱子上的圆盘全部放到C柱子上去。

代码
void hanoi(int n, char a, char b, char c)
{
	if(n == 1)//判断结束标志
	{
		count++;//计数
		printf("%c->%c\n",a,c);
	}
	
	else
	{
		hanoi(n - 1, a ,c, b);//递归函数,将a盘移到c盘上去。
		count++;//计数
		printf("%c->%c\n",a,c);//递归函数,将b盘移到a盘上去
		hanoi(n - 1, b ,a, c);
	}
	
}

int main()
{
	int n;
	printf("请输入要移动的块数:");
	scanf("%d",&n);
	
	hanoi(n, 'a', 'b', 'c');
	
	printf("移动次数:%d\n",count);//输出移到的次数
	
	return 0;
}

总结:汉诺塔是一个很经典的一个递归算法。其实它的思想并不难理解。首先,我们从最简单的一个圆盘开始算起,就直接从A到C。当有2个的时候,把第一个放到B上,再把第二个放到C上,再把B上的放到C上,以此类推。
到最后可以退出一个结论,圆盘移动的次数符合数学公式2^n – 1。

实现这个算法可以简单分为三个步骤:
(1)   把n-1个盘子由A 移到 B;
    (2)     把第n个盘子由 A移到 C;
    (3)     把n-1个盘子由B 移到 C;
从这里入手,在加上上面数学问题解法的分析,我们不难发现,移到的步数必定为奇数步:
    (1)中间的一步是把最大的一个盘子由A移到C上去;
    (2)中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,
    (3)中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号