Hanoi汉诺塔问题

最新推荐文章于 2022-09-05 16:01:58 发布

cassiePython

最新推荐文章于 2022-09-05 16:01:58 发布

阅读量1.6k

点赞数

分类专栏：最爱数学文章标签： c语言函数计算机

本文链接：https://blog.csdn.net/cassiePython/article/details/48182743

版权

最爱数学专栏收录该内容

4 篇文章

订阅专栏

Hanoi汉诺塔

汉诺塔问题：

设A，B，C是三个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自上到下，由大到小地叠放在一起。现要求将塔座A上的这一叠圆盘移动到塔座C上 ( 可以借助于塔座B），仍按同样的顺序叠置。规定：每次只能移动一个圆盘，任何时刻不允许将较大的圆盘压在较小的圆盘之上。

例如 n = 3 时，有：

我们讨论对于n个圆盘，至少需要多少次可以从A移动到C，设用Tn 来表示这个最小值。对于n = 0 ，显然 T0 = 0 ，对于 n = 1 ， T1 = 1，对于 n = 2 ，T2 = 3

由上图 T3 = 7 。

我们可以得到一个递归式：

T0 = 0

Tn = 2Tn-1 + 1 n > 0

我们可以使用递归式计算对于任意一个给定的正整数 n ，但是当 n 很大时，使用递归式计算就比较耗时了（递归式不是封闭形式的），我们能不能得到一个封闭的形式来计算

Tn呢？答案是肯定的：

T3 = 2 * 3 + 1

T4 = 2 * 7 + 1

T5 = 2 * 15 + 1

T6 = 2 * 31 + 1

看起来好像 Tn = 2的n次方 - 1 n > = 0

我们利用数学归纳法可以很容易的证明其正确性： T0 = 2 的0次方 - 1 = 0 n> 0 时 Tn = 2 Tn-1 + 1 = 2（2的n-1次方 - 1 ）+ 1 = 2 的n次方 - 1

利用上式我们就很容易计算移动的最少次数了。

下面我们使用C语言来模拟这个过程：

<span style="font-size:14px;">#include<stdio.h>
int times = 0; //用于记录移动次数
void hanoi(int n,char A,char B,char C)
{
	times += 1;
	if(n==1)
	{
		printf("Move disk %d from %c to %c\n",n,A,C);
	}
	else
	{
		hanoi(n-1,A,C,B);
		printf("Move disk %d from %c to %c\n",n,A,C);
		hanoi(n-1,B,A,C);
	}
}
int main()
{
	int n;
	printf("请输入圆盘个数n\n");
	scanf("%d",&n);
	hanoi(n,'A','B','C');
	printf("总共需要次数为:%d\n",times);
	return 0;
}</span>