快捷導(dǎo)航

C語(yǔ)言遞歸：漢諾塔問(wèn)題分析

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

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

問(wèn)題背景

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

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

游戲體驗(yàn)

點(diǎn)擊開始體驗(yàn)游戲：??漢諾塔游戲 (gitee.io)??

遞歸：漢諾塔問(wèn)題_遞歸

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

個(gè)數(shù)	移動(dòng)次數(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

移動(dòng)過(guò)程的深層解讀

漢諾塔問(wèn)題的三步過(guò)程歸納

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

一.把n-1個(gè)圓盤從A（經(jīng)過(guò)C）移到B

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

二. 把A上第n個(gè)圓盤移到C

遞歸：漢諾塔問(wèn)題_漢諾塔_03

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

遞歸：漢諾塔問(wèn)題_算法_04

重點(diǎn)?。。?！

中間的一步是把最大的一個(gè)盤子由A移到C上去；A->C
（1）中間一步之前可以看成把A上n-1個(gè)盤子通過(guò)借助C塔移到了B上，A->B
（2）中間一步之后可以看成把B上n-1個(gè)盤子通過(guò)借助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ù)個(gè)圓盤第一步永遠(yuǎn)為A–>C

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

代碼實(shí)現(xiàn)1

僅打印移動(dòng)次數(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("請(qǐng)輸入層數(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;

遞歸：漢諾塔問(wèn)題_遞歸_05

代碼實(shí)現(xiàn)2

打印移動(dòng)的具體過(guò)程

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

遞歸：漢諾塔問(wèn)題_#include_06