亲宝软件园·资讯

展开

C语言递归算法

Booksort 人气:0

汉诺塔

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

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

在这里插入图片描述

在这里插入图片描述

我们以三片开始讨论。而讨论题目开始先明白,这个柱子的位置并不影响移动,只是特定的柱子才是关键。
我们来看看如果只有一个金片,要移动多少次。

在这里插入图片描述

很明显,只要一次就够了。
再来看看两片金片。

在这里插入图片描述

在这里插入图片描述

由于要全移动到C柱

1:
a:A->B
2:
b:A->C
3;
a:B->C

三步就可以全移动过去。
或者想要移动b片要先移动a片,将空C柱留给b片,去考虑a片的移动。
再来看看三片的移动

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

总结一下

第一步

在这里插入图片描述

第二步

在这里插入图片描述

第三步

在这里插入图片描述

这么看下来,跟先前我们探讨只移两片,就没什么区别了。
再将c片移动到C柱。

在这里插入图片描述

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

在这里插入图片描述

看清楚,这个样子,就是移动两个金片的步骤。再按上面的方法步骤,就行了。
我们来计算一下这写步骤

第一部分:
移动两个金片到B柱。
第二部分:
移动C片到C柱
第三部分:
在移动两个金片到C柱。

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

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

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

在这里插入图片描述

这样来看,分两部分。

一:
移动d片到C柱
二:
移动a.b.c这仨个金片到C柱。

与上面移三片类比,、

第 一目的

在这里插入图片描述

第 二目的

在这里插入图片描述

第三目的

在这里插入图片描述

可以分三部完成。可见三片移法要移两次。
就是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;
}

使用递归时,要将其理解成一个功能模块,而不是一步一步去分析。使用它的功能,同时确定终止条件并接近这个条件。
运用递归写函数,可以”轻松“计算。
只为加深自己理解,含有学生气,勿笑。
如有问题,烦请指点一二。

以上就是C语言编程递归算法实现汉诺塔的详细内容,更多关于C语言递归算法的资料请关注其它相关文章!

加载全部内容

相关教程
猜你喜欢
用户评论