漢諾塔（Hanoi）是什么？

一個(gè)簡(jiǎn)單的漢諾塔就如上圖所示，有三個(gè)放置點(diǎn)，放置物必須遵循上小下大的規(guī)則，依次將1中的放置物全部放置到3中。就比如該圖中有4個(gè)放置物，若將A上的放置物全部移至C上，具體的步驟是：A->B A->C B->C A->B C->A C->B A->B A->C B->C B->A C->A B->C A->B A->C B->C。

那么，C語(yǔ)言如何實(shí)現(xiàn)漢諾塔呢？

第一步要先確定起始位置、中轉(zhuǎn)位置、目的位置，在一開(kāi)始A是起始位置，B是中轉(zhuǎn)位置，C是目的位置，在后續(xù)移動(dòng)物塊的時(shí)候會(huì)一直改變這三個(gè)位置的功能，以達(dá)到最終目標(biāo)。

漢諾塔的基本思路是：

第一階段：將n-1個(gè)物塊（也就是除最底部的物塊外）經(jīng)過(guò)一系列地堆放（這里就可以使用到遞歸的方法來(lái)實(shí)現(xiàn)），最后放置到中轉(zhuǎn)位置上，然后把起始位置剩下的物塊放到目的位置上，如下圖：

 以上一系列地堆放是指：以A為起始位置，C為中轉(zhuǎn)位置，B為目的位置，也就相當(dāng)于把C看作是一個(gè)中間存放點(diǎn)，來(lái)幫助這n-1個(gè)物塊放到B里面去。

第二階段：然后會(huì)發(fā)現(xiàn)，變化后的漢諾塔的形式也和之前是差不多的，如果把B看作是起始位置，A是中轉(zhuǎn)位置，C是目的位置。就可以一直按照上面的那個(gè)方法一直遞歸下去，如下圖：

以此類(lèi)推……最后就能實(shí)現(xiàn)把所有的物塊全部從A搬到C。

具體代碼見(jiàn)下（注意點(diǎn)在代碼下面）：

//C語(yǔ)言實(shí)現(xiàn)漢諾塔
#include <stdio.h>
 
void move(char p1, char p2)
{
	printf("%c->%c  ", p1, p2);
}
 
//n:個(gè)數(shù)  pos1:起始位置  pos2:中轉(zhuǎn)位置  pos3:目的位置
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
 
int main()
{
	Hanoi(1, 'A', 'B', 'C');
	printf("\n");
	Hanoi(2, 'A', 'B', 'C');
	printf("\n");
	Hanoi(3, 'A', 'B', 'C');
	printf("\n");
	Hanoi(4, 'A', 'B', 'C');
	printf("\n");
	return 0;
}

注意點(diǎn)一：代碼中的n值不能太大，因?yàn)橐苿?dòng)次數(shù)是隨n的增大呈指數(shù)倍增長(zhǎng)。

注意點(diǎn)二：n為1的時(shí)候已近到達(dá)最小單位（也就是最底層），不需要使用遞歸；n為大于1的值時(shí)，需要遞歸到1才能進(jìn)行。

注意點(diǎn)三：第一階段使用遞歸表示的是把上面n-1層全部移到B中；而第二階段使用遞歸表示的是把B中全部移到C中。

總結(jié)

這樣就可以簡(jiǎn)單地完成漢諾塔，此代碼并不是最優(yōu)方法，但是理解起來(lái)比較容易。遞歸在實(shí)際中運(yùn)用的不是很多，但是也要看得懂代碼和寫(xiě)出類(lèi)似這種漢諾塔等遞歸函數(shù)的基礎(chǔ)代碼。

到此這篇關(guān)于C語(yǔ)言用遞歸函數(shù)實(shí)現(xiàn)漢諾塔的文章就介紹到這了,更多相關(guān)C語(yǔ)言漢諾塔內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論