快捷導(dǎo)航

C語言編程遞歸算法實(shí)現(xiàn)漢諾塔

更新時(shí)間：2021年09月17日 11:57:41 作者：Booksort

遞歸，大家都了解，著名的斐波那契數(shù)，就為該知識(shí)點(diǎn)的經(jīng)典例題。今天來看看更為經(jīng)典的遞歸題漢諾塔不過這其實(shí)是數(shù)學(xué)問題，先來看看漢諾塔

漢諾塔

法國數(shù)學(xué)家愛德華·盧卡斯曾編寫過一個(gè)印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

這個(gè)傳說挺有意思的，這個(gè)傳說是說有64片金片。但我們要討論是只有3片或4片金片。看看網(wǎng)圖吧。

在這里插入圖片描述

我們以三片開始討論。而討論題目開始先明白，這個(gè)柱子的位置并不影響移動(dòng)，只是特定的柱子才是關(guān)鍵。
我們來看看如果只有一個(gè)金片，要移動(dòng)多少次。

在這里插入圖片描述

很明顯，只要一次就夠了。
再來看看兩片金片。

在這里插入圖片描述

由于要全移動(dòng)到C柱

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

三步就可以全移動(dòng)過去。
或者想要移動(dòng)b片要先移動(dòng)a片，將空C柱留給b片，去考慮a片的移動(dòng)。
再來看看三片的移動(dòng)

在這里插入圖片描述

再來根據(jù)上面的思路，要想移動(dòng)c片，得先移動(dòng)a和b兩片，把C柱留給c片。
要先滿足這個(gè)條件

在這里插入圖片描述

且大不能在小上面。要先移成這個(gè)樣子。

在這里插入圖片描述

且，要滿足這個(gè)樣子得，先這樣。

在這里插入圖片描述

總結(jié)一下

第一步

在這里插入圖片描述

第二步

在這里插入圖片描述

第三步

在這里插入圖片描述

這么看下來，跟先前我們探討只移兩片，就沒什么區(qū)別了。
再將c片移動(dòng)到C柱。

在這里插入圖片描述

成了這個(gè)樣子。再來看看，我文章開頭說的，柱子的位置不是關(guān)鍵，位置是可以改變，只是要移動(dòng)到特定的柱子。現(xiàn)在這樣，像不像，我們先前去移動(dòng)兩個(gè)金片的步驟？

在這里插入圖片描述

看清楚，這個(gè)樣子，就是移動(dòng)兩個(gè)金片的步驟。再按上面的方法步驟，就行了。
我們來計(jì)算一下這寫步驟

第一部分：
移動(dòng)兩個(gè)金片到B柱。
第二部分：
移動(dòng)C片到C柱
第三部分：
在移動(dòng)兩個(gè)金片到C柱。

總結(jié)一下
就是移兩個(gè)金片的步驟，移兩次，再移一次最下面的金片?？偣?*3+1==7次。

再來看看四個(gè)金片的步驟。

要想移動(dòng)這四個(gè)金片，必需要將這最下面的金片移動(dòng)

在這里插入圖片描述

這樣來看，分兩部分。

一：
移動(dòng)d片到C柱
二：
移動(dòng)a.b.c這仨個(gè)金片到C柱。

與上面移三片類比，、

第一目的

在這里插入圖片描述

第二目的

在這里插入圖片描述

第三目的

在這里插入圖片描述

可以分三部完成?？梢娙品ㄒ苾纱?。
就是2*7+1==15次。

依此類推

當(dāng)移動(dòng)N片金片時(shí)，要先考慮，
一–>移動(dòng)這N-1片金片。
二–>再移第N片，
三–>再移動(dòng)那N-1片到目的地。
可以分這三步。
柱子的位置對(duì)移動(dòng)并沒有上面影響。
看代碼，這是計(jì)算次數(shù)的代碼。

#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);//一個(gè)是特例，不存在中間位置
	else
	{
		hanoi(n - 1, pose1, pose3, pose2);//對(duì)應(yīng)第一次移動(dòng)N-1個(gè)金片
		move(pose1, pose3, n);//對(duì)應(yīng)移動(dòng)第N個(gè)金片
		hanoi(n - 1, pose2, pose1, pose3);//最后一次移動(dòng)N-1個(gè)金片
	}
}
int main(void)
{	
	char pose1 = 'A';//起始位置
	char pose2 = 'B';//中間位置
	char pose3 = 'C';//結(jié)束位置
	int n;
	scanf("%d", &n);
	hanoi(n, pose1, pose2, pose3);
	return 0;
}

使用遞歸時(shí)，要將其理解成一個(gè)功能模塊，而不是一步一步去分析。使用它的功能，同時(shí)確定終止條件并接近這個(gè)條件。
運(yùn)用遞歸寫函數(shù)，可以”輕松“計(jì)算。
只為加深自己理解，含有學(xué)生氣，勿笑。
如有問題，煩請(qǐng)指點(diǎn)一二。

以上就是C語言編程遞歸算法實(shí)現(xiàn)漢諾塔的詳細(xì)內(nèi)容，更多關(guān)于C語言遞歸算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: