快捷導(dǎo)航

C語(yǔ)言運(yùn)用函數(shù)的遞歸實(shí)現(xiàn)漢諾塔

更新時(shí)間：2022年07月08日 09:33:05 作者：hania_w

遞歸（recursive）函數(shù)是“自己調(diào)用自己”的函數(shù)，無(wú)論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個(gè)函數(shù)（然后可能又調(diào)用第三個(gè)函數(shù)等），最后又調(diào)用第一個(gè)函數(shù)。因?yàn)楹瘮?shù)不可以一直不停地調(diào)用自己，所以遞歸函數(shù)一定具備結(jié)束條件

1、漢諾塔是如何實(shí)現(xiàn)的

下面是有三個(gè)盤(pán)子的示例：

從左到右一次是 A柱 B柱 C柱

A柱：起始位置

B柱：目標(biāo)位置

C柱：過(guò)度位置

漢諾塔為題即是，將A柱上的所有盤(pán)子移動(dòng)到B柱上，且每次只能移動(dòng)一個(gè)盤(pán)子，并且小盤(pán)子必須在大盤(pán)子上面

2、漢諾塔問(wèn)題畫(huà)圖詳解

下面的例子是以A柱為起始位置，B柱為中間位置，C柱為目標(biāo)位置的

如果初始狀態(tài)下：A柱只有一個(gè)盤(pán)子：A->C

A柱有兩個(gè)盤(pán)子：A->B A->C B->C

A柱有三個(gè)盤(pán)子：A->C A->B C->B A->C B->A

B->C A->C

下面我們畫(huà)圖來(lái)詳細(xì)解釋一下初始狀態(tài)下為三個(gè)盤(pán)子的方法：

3、漢諾塔問(wèn)題代碼解釋

//用c語(yǔ)言解決漢諾塔問(wèn)題（函數(shù)遞歸）
#include<stdio.h>
//n：代表盤(pán)子的個(gè)數(shù)
//a：起始位置
//b：過(guò)度位置
//c：目的位置
void Move(char x1, char x2)
{
	printf("%c -> %c  ",x1,x2);//打印盤(pán)子的移動(dòng)情況
}
void Hanoi(int n, char x1, char x2, char x3)
{
	if (n == 1)//遞歸的終止條件
	{
		Move(a, c);//當(dāng)起始位置只有一個(gè)盤(pán)子時(shí)，直接將他挪到終止位置
	}
	else
	{
		Hanoi(n - 1, a, c, b);
		//將除掉最底部的一個(gè)盤(pán)子外，其余盤(pán)子通過(guò)起始位            
		//置A柱，過(guò)度位置C柱，最終移動(dòng)到B柱上
		Move(a, c);//接著將A柱上的盤(pán)子直接移動(dòng)到C柱上
		Hanoi(n - 1, b, a, c);
		//把B柱上的n-1個(gè)盤(pán)子，通過(guò)A柱，全部移動(dòng)到C柱上
	}
}
int main()
{
	char a = 'A';
	char b = 'B';
	char c = 'C';
	int n = 0;
	printf("請(qǐng)輸入起始位置的盤(pán)子數(shù)目:>");
	scanf("%d", &n);
	Hanoi(n, a, b, c);
	printf("\n");
	return 0;
}