快捷導(dǎo)航

C語(yǔ)言實(shí)現(xiàn)漢諾塔(圖文詳解)

更新時(shí)間：2021年08月13日 15:07:44 作者：流浪孤兒

個(gè)人覺(jué)得漢諾塔這個(gè)遞歸算法比電子老鼠的難了一些，不過(guò)一旦理解了也還是可以的，其實(shí)網(wǎng)上也有很多代碼，可以直接參考。記得大一開(kāi)始時(shí)就做過(guò)漢諾塔的習(xí)題，但是那時(shí)代碼寫(xiě)得很長(zhǎng)很長(zhǎng)，也是不理解遞歸的結(jié)果。今天重新來(lái)實(shí)現(xiàn)一下

漢諾塔的游戲規(guī)則：

有三根金剛石柱子A、B、C，在A柱子上從下往上按照大小依次減小的順序摞著64片黃金環(huán)。大梵天命令婆羅門(mén)把環(huán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在任何一個(gè)柱子上，小環(huán)上不能放大環(huán)，在三根柱子之間一次只能移動(dòng)一個(gè)環(huán)。

即將A柱子上全部的環(huán)通過(guò)中間柱子B（B柱子作為中介）移動(dòng)到C柱子上

當(dāng)A只有一個(gè)環(huán)的時(shí)候：

A->C

當(dāng)A只有兩個(gè)環(huán)的時(shí)候：

A->B A->C B->C

當(dāng)A只有三個(gè)環(huán)的時(shí)候：

A->C A->B C->B A->C B->A B->C A->C

思路：

1、將 n-1個(gè)環(huán)先放到B柱子上
2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上
3、將n-1個(gè)環(huán)從B柱子移動(dòng)到C柱子上

當(dāng)n=1時(shí)：

1、將0個(gè)環(huán)先放到B柱子上

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上：A->C

3、將0個(gè)環(huán)從B柱子移動(dòng)到C柱子上

當(dāng)n=2時(shí)：

1、將1個(gè)環(huán)先放到B柱子上：A->B

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上：A->C

3、將1個(gè)環(huán)從B柱子移動(dòng)到C柱子上:B->C

當(dāng)n=3時(shí)：

1、將2個(gè)環(huán)先放到B柱子上：使用遞歸將2個(gè)環(huán)放到B上，因?yàn)锳柱子的最后一個(gè)環(huán)是最大的因此可以先不理會(huì)，遞歸重復(fù)當(dāng)n=2時(shí)的步驟，不過(guò)是從將2個(gè)環(huán)從A放到C上改為將2個(gè)環(huán)從A放到B上了

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上：A->C

3、將2個(gè)環(huán)從B柱子移動(dòng)到C柱子上:使用遞歸將2個(gè)環(huán)從B柱子移動(dòng)到C柱子上，此時(shí)C柱子上已經(jīng)有了最大的一個(gè)環(huán)因此可以不用再理會(huì)了，遞歸重復(fù)當(dāng)n=2的步驟，不過(guò)是從將2個(gè)環(huán)從A放到C上改為將2個(gè)環(huán)從B放到C上了

當(dāng)n=4時(shí)：

1、將3個(gè)環(huán)先放到B柱子上：遞歸重復(fù)n=3的步驟，不過(guò)是從將3個(gè)環(huán)從A放到C上改為將3個(gè)環(huán)從A放到B上了

2、將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上：A->C

3、將3個(gè)環(huán)從B柱子移動(dòng)到C柱子上:遞歸重復(fù)當(dāng)n=3的步驟，不過(guò)是從將3個(gè)環(huán)從A放到C上改為將3個(gè)環(huán)從B放到C上了

見(jiàn)代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void move(char X, char Y)
{
	printf("%c->%c ", X, Y);
}

void HanoiTower(int n, char A, char B, char C)
{
	if (n == 1)//遞歸終止條件
	{
		move(A, C);
		return;
	}
		
	else
	{
		HanoiTower(n - 1, A, C, B);//將n-1個(gè)環(huán)從A柱子放到B柱子上，C柱子作為中介
		move(A, C);//將A柱子上的最后一個(gè)環(huán)移動(dòng)到C柱子上
		HanoiTower(n - 1, B, A, C);//將n-1個(gè)環(huán)從B柱子放到C柱子上，A柱子作為中介
	}
}


int main()
{
	printf("請(qǐng)確認(rèn)A柱子上一共有多少個(gè)環(huán):\n");
	int n = 0;
	scanf("%d", &n);
	HanoiTower(n, 'A','B','C');//將n個(gè)環(huán)從A柱子放到C柱子上，B柱子作為中介
}