快捷導(dǎo)航

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

更新時間：2023年01月24日 11:58:16 作者：持續(xù)進化中

這篇文章主要介紹了C語言遞歸：漢諾塔問題分析的相關(guān)資料,需要的朋友可以參考下

問題背景

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

每次只能移動柱子最頂端的一個圓盤；每個柱子上，小圓盤永遠(yuǎn)要位于大圓盤之上；

游戲體驗

點擊開始體驗游戲：??漢諾塔游戲 (gitee.io)??

遞歸：漢諾塔問題_遞歸

漢諾塔移動次數(shù)規(guī)律

個數(shù)	移動次數(shù)f(n)	規(guī)律
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)的關(guān)系:

所以：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（經(jīng)過C）移到B

遞歸：漢諾塔問題_代碼實現(xiàn)_02

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

遞歸：漢諾塔問題_漢諾塔_03

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

遞歸：漢諾塔問題_算法_04

重點！?。?！

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

圖解：

階數(shù)	步驟
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
...	...
奇數(shù)	第一步A->C
偶數(shù)	第一步A->B

發(fā)現(xiàn)：

奇數(shù)個圓盤第一步永遠(yuǎn)為A–>C

偶數(shù)個圓盤第一步永遠(yuǎn)為A–>B

代碼實現(xiàn)1

僅打印移動次數(shù)

#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("請輸入層數(shù)：");
scanf("%d",&num);
ret=Tower(num);
printf("需要%d次完成\n",ret);
return 0;
}

關(guān)鍵步驟

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

遞歸：漢諾塔問題_遞歸_05

代碼實現(xiàn)2

打印移動的具體過程

#include <stdio.h>
void Move(char A,char C)
{
printf("%c --> %c\n",A,C);
}
void tower(int a,char A,char B,char C)//漢諾塔函數(shù)實施主體,A為初始柱,B為經(jīng)由柱,C為目的柱
{
if (a==1)
{
Move(A,C);
}
else
{
tower(a-1,A,C,B);//把n-1個圓盤從A（經(jīng)過C）移到B
Move(A,C);
tower(a-1,B,A,C);//把B桿上的（n-1）個圓盤（經(jīng)過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("請輸入層數(shù):");
scanf("%d",&a);
Num = Tower(a);
printf("%d層需要移動%d步\n", a, Num);
tower(a, 'A', 'B', 'C');//進入遞歸
return 0;
}

遞歸：漢諾塔問題_#include_06