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

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

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

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

下面是有三個盤子的示例：

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

A柱：起始位置

B柱：目標位置

C柱：過度位置

漢諾塔為題即是，將A柱上的所有盤子移動到B柱上，且每次只能移動一個盤子，并且小盤子必須在大盤子上面

2、漢諾塔問題畫圖詳解

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

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

A柱有兩個盤子：A->B A->C B->C

A柱有三個盤子：A->C A->B C->B A->C B->A

B->C A->C

下面我們畫圖來詳細解釋一下初始狀態(tài)下為三個盤子的方法：

3、漢諾塔問題代碼解釋

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