漢諾塔——經典遞回問題（c語言實作）
問題背景
漢諾塔問題是一個經典的問題，漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次只能移動一個圓盤，問應該如何操作？
問題分析
思路：
1.使用的語言：C語言
2.使用的編譯器：vs2019
3.參考書籍：譚浩強第四版
4.主要使用的知識：函式的遞回
5.代碼實作的思路主要分為三步：
假設總共需要移動n個盤子
1.將A柱上的n-1個盤子借助C柱移向B柱
2.將A柱上僅剩的最后一個盤子移向C柱
3.將B柱上的n-1個盤子借助A柱移向C柱
代碼實作
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void move(int x, int y)
{
printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
if (n == 1)
{
move(a, c);
}
else
{
hanoi(n - 1, a, c, b);//將A座上的n-1個盤子借助C座移向B座
move(a, c);//將A座上最后一個盤子移向C座
hanoi(n - 1, b, a, c);//將B座上的n-1個盤子借助A座移向C座
}
}
//move中的實參與hanoi函式中的形參相對應，而hanoi函式中形參a，b，c所對應的值也是在有規律的變化
int main()
{
int n = 0;
scanf("%d", &n);
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，
按任意鍵關閉此視窗. . .
4
A->B
A->C
B->C
A->B
C->A
C->B
A->B
A->C
B->C
B->A
C->A
B->C
A->B
A->C
B->C
D:\c code\小題庫\漢諾塔問題\Debug\漢諾塔問題.exe (行程 19616)已退出，代碼為 0，
按任意鍵關閉此視窗. . .
代碼分析
圖解
核心演算法
if (n == 1)
{
move(a, c);
}
else
{
hanoi(n - 1, a, c, b);//將A座上的n-1個盤子借助C座移向B座
move(a, c);//將A座上最后一個盤子移向C座
hanoi(n - 1, b, a, c);//將B座上的n-1個盤子借助A座移向C座
}
判斷條件為n是否為1，當n=1時結束，再通過move函式將所需步驟列印即可，遞回的程序實在不好描述，只能靠自己理解了
個人研究
1.你會發現n個盤子所需的步數為2的n次方減一，并且最中間一步永遠為A–>C
2.為什么奇數個盤子時第一步永遠為A–>C，而偶數個時，第一步永遠為A–>B？
解釋：hanoi(n - 1, a, c, b)函式的實參a，b和c并不是總對應A盤，B盤和C盤并且在傳遞給形參后abc對應的值會發生變化，但是確是有規律的在變化，為什要了解這個呢?因為這個hanoi函式的形參對應的值會影響move函式的列印，規律為形參abc對應值為ACB，ABC回圈變化，再加上第一次呼叫hanoi函式形參abc對應ABC，這也就解釋了為什么奇數個盤子時第一步永遠為A–>C，而偶數個時，第一步永遠為A–>B
體會
好難，看了一下午才理解，也看了書上的解釋，看了其他人的解釋，上面的分析圖就是拷過來的（hhh），只能舉幾個實體，一遍遍實作代碼再一邊理解，找出規律，遞回問題都好抽象，很難想象出運行結果，可以做一些簡單的遞回題目加以理解，慢慢來啦，頭疼，哈哈哈
如有錯誤，還請指正，謝謝！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/272479.html
標籤：其他