C語言超詳細講解遞歸算法漢諾塔

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

漢諾塔問題是一個經典的問題。漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說。本文將用Java求解這一問題，感興趣的可以學習一下

題目描述

漢諾塔問題起源于一個傳說

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

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

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

畫圖分析

由簡到繁，我們先從最簡單的情況來分析：

~~只有一個盤子的時候：

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

~~有兩個盤子的時候：

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

~~有三個盤子的時候：

有三個盤子的時侯，我們把最小的盤子命名為1，中間的為2，最大的為3，那么移動順序應該是：1號移到到C柱，2號移動到B柱，1號移動到B柱，3號移動到C柱，1號移動到A柱，2號移動到C柱，1號移動到C柱；一共移動7次，移動順序是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

思路總結

在上面的移動過程中，B柱始終起著中轉的作用，我們我們可以理解為：

A柱：起始柱
B柱：中轉柱
C柱：目標柱

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

其次，我們可以把上面的移動過程簡化為三個步驟：

把n-1個盤子通過C柱移到B柱上。
把A柱上的最后一個盤子移動到C柱上。
把n-1個盤子通過A柱移動到C柱上。

比如，上面盤子個數(shù)為三的時候，我們可以分解為：第一步：1號移到到C柱，2號移動到B柱，1號移動到B柱；第二步：3號移動到C柱；第三步：1號移動到A柱，2號移動到C柱，1號移動到C柱。

所以，n個盤子的移動順序為：

1、把n-1個盤子通過C柱移到B柱上。

2. 把A柱上的最后一個盤子移動到C柱上。

3. 把n-1個盤子通過A柱移動到C柱上。

代碼實現(xiàn)

#include<stdio.h>

//Move函數(shù)，用來移動盤子，pos1表示起始柱，pos2表示目標柱
void Move(char pos1, char pos2)
{
	printf("%c->%c ", pos1, pos2);  //把pos1的盤子移動到pos2
}

//Hanoi函數(shù)，用來實現(xiàn)漢諾塔，其中n表示盤子的個數(shù)，pos1表示起始柱，pos2表示中轉柱，pos3表示目標柱
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (1 == n)  //當n==1時，直接把盤子從A柱移動到C柱
	{
		Move(pos1, pos3);  
	}
	else   //當n不等于1時，分三步走
	{
		//第一步：將n-1個盤子通過C柱移動到B柱,此時C柱時中轉柱，B柱是目標柱
		Hanoi(n - 1, pos1, pos3, pos2);
		//第二步：把A柱最后一個盤子直接移動到C柱
		Move(pos1, pos3);
		//第三步：將n-1個盤子通過A柱移動到C柱，此時B柱是起始柱，A柱是中轉柱，C柱是目標柱
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	//定義一個變量來表示盤子的個數(shù)
	int n = 0;   
	//定義三個字符變量來表示三根柱子
	char pos1 = 'A';
	char pos2 = 'B';
	char pos3 = 'C';
	//調用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;
}