問題由來

漢諾塔:漢諾塔(又稱河內塔)問題是源于印度一個古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，————百度百科

漢諾塔問題可能有的人知道，有的人不知道，今天小科就來講解一下

漢諾塔問題是一道比較復雜的遞回問題，但是想到遞回的兩個必要條件：

每次遞回呼叫之后越來越接近這個限制條件

存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，

問題分解

我們將問題轉換為：

假設有n個圓盤，我們的目標是：將N個圓盤從第一個柱子移到第三個柱子，那么可以把問題分解為：
1.將n-1個圓盤從第一個柱子移到第二個柱子
2.將第n個圓盤從第一個柱子移到第三個柱子
3.將n-1個圓盤從第二個柱子移到第三個柱子

圖解：
在這里插入圖片描述
那么我們來分析一下：

n=3時，步驟：
A->C
A->B
C->B
A->C
B->A
B->C
A->C

原代碼

那我們來寫下代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void move(char X,char Y)
{
	printf("%c->%c",X,Y);
}
void hanoi(int n, char a, char b, char c)//表示n個盤子，a，b,c三根柱子
{
	if (n == 1)
	{
		move(a, c);
	}
	else
	{
		hanoi(n-1,a,c,b);//表示a柱上的n-1個盤子借助c柱移向b柱
		move(a,c);//表示a柱上第n個盤子移向c柱
		hanoi(n-1,b,a,c);//表示b柱上的n-1個盤子借助a柱移向c柱
	}
}
main()
{
	int n=0;
	printf("請輸入盤子的數量：");
	scanf("%d",&n);
	printf("盤子移動的程序：");
	hanoi(n,'A','B','C');//呼叫函式遞回求盤子移動軌跡
	
	return 0;
}

運行結果

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

D:\c code\小題庫\漢諾塔問題\Debug\漢諾塔問題.exe (行程 13928)已退出，代碼為 0，
按任意鍵關閉此視窗. . .

重要步驟

		hanoi(n-1,a,c,b);//表示a柱上的n-1個盤子借助c柱移向b柱
		move(a,c);//表示a柱上第n個盤子移向c柱
		hanoi(n-1,b,a,c);//表示b柱上的n-1個盤子借助a柱移向c柱

你會發現n個盤子所需的步數為2的n次方減一，并且為什么是a,c,b;b,c,a這兩個步驟？

這是因為第一步永遠從a柱拿出盤子，最后一步永遠是把盤子放到c柱
但是如果都是a,b,c這樣的順序，將不會有任何意義
同時 hanoi函式的形參對應的值會影響move函式的列印

這個問題不好描述，所以換成淺顯易懂的語言

感悟

其實我自己也看了不少文章，經過仔細推敲才搞懂這個順序
所以大家可以自己仔細推敲細節，爭取弄得透徹

如果有錯誤，希望各位看我文章的小伙伴提出來

各位的支持是我創作的全部動力，拜拜

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277716.html

標籤：其他

上一篇：漢諾塔問題決議（C語言）

下一篇：C++多型實作中的虛函式