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

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

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

當A只有一個環(huán)的時候：

A->C

當A只有兩個環(huán)的時候：

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

當A只有三個環(huán)的時候：

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

思路：

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

當n=1時：

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

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

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

當n=2時：

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

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

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

當n=3時：

1、將2個環(huán)先放到B柱子上：使用遞歸將2個環(huán)放到B上，因為A柱子的最后一個環(huán)是最大的因此可以先不理會，遞歸重復當n=2時的步驟，不過是從將2個環(huán)從A放到C上改為將2個環(huán)從A放到B上了

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

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

當n=4時：

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

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

3、將3個環(huán)從B柱子移動到C柱子上:遞歸重復當n=3的步驟，不過是從將3個環(huán)從A放到C上改為將3個環(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個環(huán)從A柱子放到B柱子上，C柱子作為中介
		move(A, C);//將A柱子上的最后一個環(huán)移動到C柱子上
		HanoiTower(n - 1, B, A, C);//將n-1個環(huán)從B柱子放到C柱子上，A柱子作為中介
	}
}


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

運行截圖

總結(jié)

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

最新評論