快捷導(dǎo)航

C語(yǔ)言超詳細(xì)講解遞歸算法漢諾塔

更新時(shí)間：2022年05月05日 15:22:05 作者：野豬佩奇`

漢諾塔問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。漢諾塔（Hanoi Tower），又稱河內(nèi)塔，源于印度一個(gè)古老傳說(shuō)。本文將用Java求解這一問(wèn)題，感興趣的可以學(xué)習(xí)一下

題目描述

漢諾塔問(wèn)題起源于一個(gè)傳說(shuō)

漢諾塔又被稱為河內(nèi)塔，傳說(shuō)，在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。

印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

我們現(xiàn)在要研究的就是在不同情況下盤(pán)子的移動(dòng)順序和移動(dòng)的次數(shù)。

畫(huà)圖分析

由簡(jiǎn)到繁，我們先從最簡(jiǎn)單的情況來(lái)分析：

~~只有一個(gè)盤(pán)子的時(shí)候：

只有一個(gè)盤(pán)子我們直接把它從A柱移到C柱就行，此時(shí)移動(dòng)次數(shù)是1，移動(dòng)順序是 A->C

~~有兩個(gè)盤(pán)子的時(shí)候：

有兩個(gè)盤(pán)子的時(shí)候我們需要先將較小的盤(pán)子移動(dòng)到B柱，然后將較大的盤(pán)子移動(dòng)C柱，再將B柱上的盤(pán)子移動(dòng)到C柱；此時(shí)移動(dòng)次數(shù)是3，移動(dòng)順序是 A->B A->C B->C

~~有三個(gè)盤(pán)子的時(shí)候：

有三個(gè)盤(pán)子的時(shí)侯，我們把最小的盤(pán)子命名為1，中間的為2，最大的為3，那么移動(dòng)順序應(yīng)該是：1號(hào)移到到C柱，2號(hào)移動(dòng)到B柱，1號(hào)移動(dòng)到B柱，3號(hào)移動(dòng)到C柱，1號(hào)移動(dòng)到A柱，2號(hào)移動(dòng)到C柱，1號(hào)移動(dòng)到C柱；一共移動(dòng)7次，移動(dòng)順序是A->C A->B C->B A->C B->A B->C A->C

A->C A->B C->B

A->C B->A

B->C A->C

思路總結(jié)

在上面的移動(dòng)過(guò)程中，B柱始終起著中轉(zhuǎn)的作用，我們我們可以理解為：

A柱：起始柱
B柱：中轉(zhuǎn)柱
C柱：目標(biāo)柱

同時(shí)，我們發(fā)現(xiàn)一個(gè)盤(pán)子時(shí)需要移動(dòng)一次，兩個(gè)盤(pán)子時(shí)需要移動(dòng)3次，3個(gè)盤(pán)子時(shí)需要移動(dòng)7次，所以總結(jié)規(guī)律：n個(gè)盤(pán)子需要移動(dòng)的次數(shù)是 2n-1 次。

其次，我們可以把上面的移動(dòng)過(guò)程簡(jiǎn)化為三個(gè)步驟：

把n-1個(gè)盤(pán)子通過(guò)C柱移到B柱上。
把A柱上的最后一個(gè)盤(pán)子移動(dòng)到C柱上。
把n-1個(gè)盤(pán)子通過(guò)A柱移動(dòng)到C柱上。

比如，上面盤(pán)子個(gè)數(shù)為三的時(shí)候，我們可以分解為：第一步：1號(hào)移到到C柱，2號(hào)移動(dòng)到B柱，1號(hào)移動(dòng)到B柱；第二步：3號(hào)移動(dòng)到C柱；第三步：1號(hào)移動(dòng)到A柱，2號(hào)移動(dòng)到C柱，1號(hào)移動(dòng)到C柱。

所以，n個(gè)盤(pán)子的移動(dòng)順序?yàn)椋?/p>

1、把n-1個(gè)盤(pán)子通過(guò)C柱移到B柱上。

2. 把A柱上的最后一個(gè)盤(pán)子移動(dòng)到C柱上。

3. 把n-1個(gè)盤(pán)子通過(guò)A柱移動(dòng)到C柱上。

代碼實(shí)現(xiàn)

#include<stdio.h>

//Move函數(shù)，用來(lái)移動(dòng)盤(pán)子，pos1表示起始柱，pos2表示目標(biāo)柱
void Move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);  //把pos1的盤(pán)子移動(dòng)到pos2
}

//Hanoi函數(shù)，用來(lái)實(shí)現(xiàn)漢諾塔，其中n表示盤(pán)子的個(gè)數(shù)，pos1表示起始柱，pos2表示中轉(zhuǎn)柱，pos3表示目標(biāo)柱
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (1 == n)  //當(dāng)n==1時(shí)，直接把盤(pán)子從A柱移動(dòng)到C柱
	{
		Move(pos1, pos3);  
	}
	else   //當(dāng)n不等于1時(shí)，分三步走
	{
		//第一步：將n-1個(gè)盤(pán)子通過(guò)C柱移動(dòng)到B柱,此時(shí)C柱時(shí)中轉(zhuǎn)柱，B柱是目標(biāo)柱
		Hanoi(n - 1, pos1, pos3, pos2);
		//第二步：把A柱最后一個(gè)盤(pán)子直接移動(dòng)到C柱
		Move(pos1, pos3);
		//第三步：將n-1個(gè)盤(pán)子通過(guò)A柱移動(dòng)到C柱，此時(shí)B柱是起始柱，A柱是中轉(zhuǎn)柱，C柱是目標(biāo)柱
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	//定義一個(gè)變量來(lái)表示盤(pán)子的個(gè)數(shù)
	int n = 0;   
	//定義三個(gè)字符變量來(lái)表示三根柱子
	char pos1 = 'A';
	char pos2 = 'B';
	char pos3 = 'C';
	//調(diào)用hanoi函數(shù)
	Hanoi(1, pos1, pos2, pos3);  //n為1
	printf("\n");
	Hanoi(2, pos1, pos2, pos3);  //n為2
	printf("\n");
	Hanoi(3, pos1, pos2, pos3);  //n為3
	printf("\n");
	Hanoi(4, pos1, pos2, pos3);  //n為4
	printf("\n");
	return 0;
}

總結(jié)

知道了漢諾塔的邏輯后，我們重新回到這個(gè)問(wèn)題，我們發(fā)現(xiàn)，要把64片金片全部挪完需要挪動(dòng) 264-1 次，假設(shè)這個(gè)僧侶一秒鐘移動(dòng)一次，那么一共要挪 (264-1) / 3600 / 24 / 365 = 584,942,417,355(年)，那時(shí)候地球已經(jīng)毀滅也不是沒(méi)有可能，哈哈。

到此這篇關(guān)于C語(yǔ)言超詳細(xì)講解遞歸算法漢諾塔的文章就介紹到這了,更多相關(guān)C語(yǔ)言漢諾塔內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: