C语言编程递归算法实现汉诺塔

递归,大家都了解,著名的斐波那契数,就为该知识点的经典例题。

今天来看看更为经典的递归题汉诺塔青蛙跳台阶,不过这其实是数学问题。先来看看汉诺塔。

汉诺塔

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

这个传说挺有意思的,这个传说是说有64片金片。但我们要讨论是只有3片或4片金片。看看网图吧。

455DD9E0-22EA-4D81-61FE-D93ADAA9EAAC.png

9AEA7F37-E92D-DE5E-6F77-3029A23C0D5D.png

我们以三片开始讨论。而讨论题目开始先明白,这个柱子的位置并不影响移动,只是特定的柱子才是关键。

我们来看看如果只有一个金片,要移动多少次。

9FA988F7-19CF-8427-219A-0A858488BE72.png

很明显,只要一次就够了。

再来看看两片金片。

62583D18-9F0B-ECA4-7103-DBBFCB6D783B.png

BF59D565-ED16-CE64-7C48-AFA07B57E051.png

由于要全移动到C柱

1:

a:A->B

2:

b:A->C

3;

a:B->C

三步就可以全移动过去。

或者想要移动b片要先移动a片,将空C柱留给b片,去考虑a片的移动。

再来看看三片的移动

22E9568B-140A-CC32-57B7-507B15677D9D.png

再来根据上面的思路,要想移动c片,得先移动a和b两片,把C柱留给c片。

要先满足这个条件

C550C428-4047-8CC2-4C07-13024CC4422F.png

且大不能在小上面。要先移成这个样子。

1FE6E824-23E3-45B2-3AC9-D344DD432621.png

且,要满足这个样子得,先这样。

74C1BA8D-11F8-0673-B48D-CA53E38F3F3E.png

总结一下,

第一步

74C1BA8D-11F8-0673-B48D-CA53E38F3F3E.png

第二步

1FE6E824-23E3-45B2-3AC9-D344DD432621.png

第三步

C550C428-4047-8CC2-4C07-13024CC4422F.png

这么看下来,跟先前我们探讨只移两片,就没什么区别了。

再将c片移动到C柱。

5D8028E4-9DD7-7B24-B288-D3D8A592575A.png

成了这个样子。再来看看,我文章开头说的,柱子的位置不是关键,位置是可以改变,只是要移动到特定的柱子。现在这样,像不像,我们先前去移动两个金片的步骤?

F4F8F4F2-A1F0-D81A-4B29-C15731D093C8.png

看清楚,这个样子,就是移动两个金片的步骤。再按上面的方法步骤,就行了。

我们来计算一下这写步骤

第一部分:

移动两个金片到B柱。

第二部分:

移动C片到C柱

第三部分:

在移动两个金片到C柱。

总结一下

就是移两个金片的步骤,移两次,再移一次最下面的金片。总共2*3+1==7次。

再来看看四个金片的步骤。

要想移动这四个金片,必需要将这最下面的金片移动

5AE93C22-17E5-AF3D-D5AA-412A08910AB2.png

这样来看,分两部分。

一:

移动d片到C柱

二:

移动a.b.c这仨个金片到C柱。

与上面移三片类比,

第 一目的

9DD9584A-AB5C-5854-CADF-78ADAA09D52E.png

第 二目的

5365A005-01D0-03B4-5E1F-B418B58408FF.png

第三目的

DBCA7B2F-61F5-1F3C-05C6-1808B4EF32CC.png

可以分三部完成。可见三片移法要移两次。

就是2*7+1==15次。

**

依此类推

**

当移动N片金片时,要先考虑,

一–>移动这N-1片金片。

二–>再移第N片,

三–>再移动那N-1片到目的地。

可以分这三步。

柱子的位置对移动并没有上面影响。

看代码,这是计算次数的代码。

#include <stdio.h>
int hanoi(int n)
{
	if (n >= 2)
		return 2 * hanoi(n - 1) + 1;
	return 1;
}
int main(void)
{
	printf("Problem of Hanoi\n");
	printf("please input the number for problem:>\n");
	int n;
	scanf("%d", &n);
	printf("%d",hanoi(n));
	return 0;
}

这是编译步骤的代码

#include <stdio.h>
void move(char start,char end,int n)
{
	static int count = 0;
	count++;
	printf("NO.%d step,the %d moves from %c to %c\n", count, n, start, end);
}
void hanoi(int n,char pose1,char pose2,char pose3)
{
	if (n == 1)
		move(pose1, pose3, 1);//一个是特例,不存在中间位置
	else
	{
		hanoi(n - 1, pose1, pose3, pose2);//对应第一次移动N-1个金片
		move(pose1, pose3, n);//对应移动第N个金片
		hanoi(n - 1, pose2, pose1, pose3);//最后一次移动N-1个金片
	}
}
int main(void)
{
	
	char pose1 = 'A';//起始位置
	char pose2 = 'B';//中间位置
	char pose3 = 'C';//结束位置
	int n;
	scanf("%d", &n);
	hanoi(n, pose1, pose2, pose3);
	
	return 0;
}

使用递归时,要将其理解成一个功能模块,而不是一步一步去分析。使用它的功能,同时确定终止条件并接近这个条件。

运用递归写函数,可以”轻松“计算。

收藏 (0)
评论列表
正在载入评论列表...
我是有底线的
为您推荐
    暂时没有数据