C語言遞迴：漢諾塔問題分析

2023-01-24 14:00:14

問題背景

漢諾塔問題源自印度一個古老的傳說，印度教的“創造之神”梵天創造世界時做了 3 根金剛石柱，其中的一根柱子上按照從小到大的順序摞著 64 個黃金圓盤。梵天命令一個叫婆羅門的門徒將所有的圓盤移動到另一個柱子上，移動過程中必須遵守以下規則：

每次只能移動柱子最頂端的一個圓盤；每個柱子上，小圓盤永遠要位於大圓盤之上；

遊戲體驗

漢諾塔移動次數規律

個數	移動次數f(n)	規律
1	1	2^1-1
2	3	2^2-1
3	7	2^3-164-1
4	15	2
...	...	...
n	2^n-1	2^n-1

由上述分析可以得到f(n)與f(n-1)的關係:

所以：f(n)=2^n-1 ; f(n-1)=2^(n-1)-1

f(n)=2^n-1=2^1*(2^(n-1)-1)+1=2*f(n-1)+1

移動過程的深層解讀

漢諾塔問題的三步過程歸納

（我們是把n-1個圓盤看成一個整體去分析的）

一.把n-1個圓盤從A（經過C）移到B

二. 把A上第n個圓盤移到C

三: 把B上的（n-1）個圓盤（經過A）移到C

重點！！！！

中間的一步是把最大的一個盤子由A移到C上去；A->C
（1）中間一步之前可以看成把A上n-1個盤子通過藉助C塔移到了B上，A->B
（2）中間一步之後可以看成把B上n-1個盤子通過藉助A塔移到了C上；B->C

圖解：

階數	步驟
1	A->C
2	A->B，A->C，B->C
3	A->C，A->B，C->B，A->C，B->A，B->C，A->C
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
...	...
奇數	第一步A->C
偶數	第一步A->B

發現：

奇數個圓盤第一步永遠為A–>C

偶數個圓盤第一步永遠為A–>B

程式碼實現1

僅列印移動次數

#include<stdio.h>
int Tower(int num)
{
if(num==1)
return 1;
else
return 2*Tower(num-1)+1;
}
int main()
{
int num=0;
int ret=0;
printf("請輸入層數：");
scanf("%d",&num);
ret=Tower(num);
printf("需要%d次完成n",ret);
return 0;
}

關鍵步驟

if(num==1)
return 1;
else
return 2*Tower(num-1)+1;

程式碼實現2

列印移動的具體過程

#include <stdio.h>
void Move(char A,char C)
{
printf("%c --> %cn",A,C);
}
void tower(int a,char A,char B,char C)//漢諾塔函數實施主體,A為初始柱,B為經由柱,C為目的柱
{
if (a==1)
{
Move(A,C);
}
else
{
tower(a-1,A,C,B);//把n-1個圓盤從A（經過C）移到B
Move(A,C);
tower(a-1,B,A,C);//把B杆上的（n-1）個圓盤（經過A）移到C
}
}
int Tower(int num)
{
if (num==1)
return 1;
else
return 2*Tower(num-1)+1;
}
int main()
{
int a = 0;
int Num=0;
printf("請輸入層數:");
scanf("%d",&a);
Num = Tower(a);
printf("%d層需要移動%d步n", a, Num);
tower(a, 'A', 'B', 'C');//進入遞迴
return 0;
}