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

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

即將A柱子上全部的環(huán)通過中間柱子B（B柱子作為中介）移動到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)移動到C柱子上
3、將n-1個(gè)環(huán)從B柱子移動到C柱子上

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

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

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

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

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

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

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

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

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

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

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

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

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

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

見代碼

#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)移動到C柱子上
		HanoiTower(n - 1, B, A, C);//將n-1個(gè)環(huán)從B柱子放到C柱子上，A柱子作為中介
	}
}


int main()
{
	printf("請確認(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柱子作為中介
}

運(yùn)行截圖

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論