汉诺塔c语言代码实现

article/2025/3/11 0:05:03

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

在这里插入图片描述

塔数	步数	规律
1	2	2¹-1
2	3	2²-1
3	7	2³-1
4	15	2⁴-1
......	......	......

不难看出，汉诺塔步数的数学规律为2的n次方减1，n为塔数。

首先我们可以用c语言库函数里的pow函数求解。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{int n = 0;printf("请输入汉诺塔的塔数\n");scanf("%d", &n);n = pow( 2, n) - 1;printf("步数:>%d\n",n );return 0;
}

好像能够实现

我们试试前言中64层的塔数，看需要多少步。。。。。。

代码很快就实现了，结果虽然是负数。

好叭，2的64次方挺大的

看来是复制到缓冲区的数据太大导致栈溢出了。

用函数的递归来实现一下

首先定义一个函数f(x)=2*f(x-1)且f(1)=1，

f(4)=2*f(3)

f(3)=2*f(2)

f(2)=2*f(1)

根据定义，f(1)=1，所以f(4)=2*(2*(2*f(1)))=8。也就是说函数不停的调用自己就是递归函数。

假设有n个盘子

有3个阶段

第一阶段：（n-1）A—>B（把所有的n-1个盘子从A移动到B上）

第二阶段：n A—>C（把最底下的n号盘从A移动到C上）

第三阶段：（n-1）B—>C（把n-1个盘子从B移动到C上）

这是第三阶段的两个步骤

那么汉诺塔步数就为f (n -1 ) + 1 + f (n - 1)， 2 * +1。

注意：f (1)=1。所以当层数等于1时，步数为1，函数返回值为1。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int Tower_Hanoi(int x)
{if (1 == x)return 1;elsereturn 2 * Tower_Hanoi(x - 1) + 1;
}int main()
{int x = 0;int y = 0;printf("请输入汉诺塔的塔数\n");scanf("%d", &x);y = Tower_Hanoi(x);printf("步数:>%d\n", y);return 0;
}