C語言運用函數的遞歸實現漢諾塔

Posted on by

1、漢諾塔是如何實現的

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

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

A柱：起始位置

B柱：目標位置

C柱：過度位置

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

2、漢諾塔問題畫圖詳解

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

如果初始狀態下：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

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

3、漢諾塔問題代碼解釋

//用c語言解決漢諾塔問題（函數遞歸）
#include<stdio.h>
//n：代表盤子的個數
//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("請輸入起始位置的盤子數目:>");
	scanf("%d", &n);
	Hanoi(n, a, b, c);
	printf("\n");
	return 0;
}

當A柱起始位置有三個盤子是與我們分析的結果是一樣的

總結

漢諾塔問題，需要用到遞歸思想，即從大到小考慮，

搞清楚每一步的起始位置與目標位置，巧妙借助過度位置的柱子去解決問題！

到此這篇關於C語言運用函數的遞歸實現漢諾塔的文章就介紹到這瞭,更多相關C語言漢諾塔內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：