漢諾塔

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

這個傳說挺有意思的，這個傳說是說有64片金片。但我們要討論是只有3片或4片金片?？纯淳W(wǎng)圖吧。

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

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

由于要全移動到C柱

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

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

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

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

且，要滿足這個樣子得，先這樣。

總結(jié)一下

第一步

第二步

第三步

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

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

看清楚，這個樣子，就是移動兩個金片的步驟。再按上面的方法步驟，就行了。
我們來計算一下這寫步驟

第一部分：
移動兩個金片到B柱。
第二部分：
移動C片到C柱
第三部分：
在移動兩個金片到C柱。

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

再來看看四個金片的步驟。

要想移動這四個金片，必需要將這最下面的金片移動

這樣來看，分兩部分。

一：
移動d片到C柱
二：
移動a.b.c這仨個金片到C柱。

與上面移三片類比，、

第 一目的

第 二目的

第三目的

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

依此類推

當(dāng)移動N片金片時，要先考慮，
一–>移動這N-1片金片。
二–>再移第N片，
三–>再移動那N-1片到目的地。
可以分這三步。
柱子的位置對移動并沒有上面影響。
看代碼，這是計算次數(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);//一個是特例，不存在中間位置
	else
	{
		hanoi(n - 1, pose1, pose3, pose2);//對應(yīng)第一次移動N-1個金片
		move(pose1, pose3, n);//對應(yīng)移動第N個金片
		hanoi(n - 1, pose2, pose1, pose3);//最后一次移動N-1個金片
	}
}
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ù)，可以”輕松“計算。
只為加深自己理解，含有學(xué)生氣，勿笑。
如有問題，煩請指點一二。

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

最新評論