文章目錄
- 背景
- 一、漢諾塔和遞回
- 二、代碼實作
- 總結
背景
漢諾塔（Tower of Hanoi），又稱河內塔，是一個源于印度古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，（源自百度百科）
一、漢諾塔和遞回
當我們想將64個圓盤從A柱移動到C柱上，我們可以將其分為三個步驟：
步驟1、通過一種符合要求的方式將A柱上63個圓盤從A移動到B（我們不要關心這個方式具體是什么）
步驟2、經過步驟1之后A柱上只剩下一個圓盤，我們將這個圓盤從A移動到C（我們所要關心的只有最后將1個圓盤從A移動到C）
步驟3、經過步驟1和步驟2之后，B柱上有了63個圓盤，C上有1個圓盤，我們再通過某種方式將B柱上63個圓盤從B移動到C（同樣也不要關心這個具體的方式是什么）
經過了步驟1、 2 、3之后，我們就將所有的圓盤從A移動到了C
但是問題又來了，在步驟1中，我們將63個圓盤從A移動到了B，那么我們如何移動呢？
步驟1又可以繼續拆分：
步驟1.1、將62個圓盤從A柱移動到C柱
步驟1.2、將1個圓盤從A柱移動到B柱
步驟1.3、將62個圓盤從C柱移動到B柱
步驟1.1又可以繼續拆分：
1.1.1、將61個圓盤從A柱移動到B柱
1.1.2、將1個圓盤從A柱移動到C柱
1.1.3、將61個圓盤從B柱移動到C柱
繼續向下拆分
.
.
.
經過63次拆分后，第64次只需要移動1個圓盤，只需要將1個圓盤移動到領一個圓盤上即可
我們設一個函式H（n）表示n個圓盤從A柱移動到C柱需要移動多少次
我們要先將（n-1）個圓盤從A移動到B柱，需要移動H（n-1）次
然后將1個圓盤從A移動到C柱，需要移動1次
再講（n-1）個圓盤從B柱移動到C柱，需要移動H（n-1）次
因此H（n） = 2*H（n-1） +1，H（1）= 1；
我們就得到了遞推公式
H（1） =1=2^1-1
H（2）=2（H（1））+1=2^2-1
H（3）=2（H（2））+1=2^3-1
H（4）=2（H（3））+1=2^4-1
.
.
.
H（n）=2^n-1，
所以64個圓盤需要移動2^64-1次，假設1秒移動可以移動1次，差不多需要5845.42億年以上，
對于最初的三個步驟，可能很多人還是比較迷糊，我們換一個說法，現在小明有一個任務，就是將64個 圓盤從A移動到C，但是他只會移動一個圓盤，于是他找到了小張幫忙，小張欣然接受 ，并保證完成任務，于是小張幫小明把上面的63個圓盤從A移動到B，然后小明再將第64個圓盤移動到C；等小明移動完第64塊圓盤之后，再讓小張把63個圓盤 從B移動到C，對于小明來說，他不用關心小張是如何做到將63個圓盤從A移動到B，再從B移動到C，他只需要等小張移動完63塊圓盤之后，完成第64塊圓盤的移動，而小張在進行移動的時候，他可以再找其他人幫助，這些小明都不用關心，同樣小張也不用關心他所找的人是如何進行的移動，
我覺得這就像是A公司有一個大專案，A公司將這個專案拆分成了2個部分，將最核心的部分留給自己公司處理，然后將剩下的部分外包給B公司，B公司同樣可以像A公司一樣，繼續往下外包，這樣一直下去，只要最后每個公司能保證屬于自己的部分完成，那么整個專案就可以順利的完成，
二、代碼實作
#include<stdio.h>
void Move_(char From, char Dest) //移動一個圓盤，將圓盤從來源移動到目的地 從From 移動到Dest
{
printf("將一個圓盤從%c柱子 -> %c柱子\n", From, Dest);
}
void Hanoi( char A,char B,char C,int n) //總共有n個圓盤，將這n個圓盤 借助 B 柱子 從 A 柱子移動到 C 柱子
{
if (n == 1) //當只有一個圓盤時，直接圓盤從 A 柱 移動到 C 柱
{
Move_(A, C);
}
else
{
Hanoi(A,C,B,n - 1); //當不只一個圓盤時，我們先將上面 （n -1）個圓盤 借助 C柱子 從 A 柱子移動到 B 柱子
Move_(A, C); //A柱剩余一個圓盤，將剩下的一個圓盤從 A 移動到 C
Hanoi(B, A, C, n - 1); //再將（n-1）個圓盤 借助 A柱子 從 B柱子 移動到 C柱子
}
}
int main()
{
int n = 0; //漢諾塔層數
char A = 'A'; //A柱子
char B = 'B'; //B柱子
char C = 'C'; //C柱子
scanf("%d", &n);
Hanoi(A,B,C,n); //將n個圓盤，借助于B柱子，從A柱子移動到C柱子
return 0;
}
運行結果:
n=3
n=5
n=20的時候，我的電腦運行了47秒的時間，根據上面的迭代公式，總共迭代了2^20-1次，≈ 2^ 20次，所以當n=30的時候需要迭代2^30次（減1忽略不計），大概需要
47* 2^10 =48128S，約等于13.37小時，當n=31的時候，大概需要13.37*2小時，約等于1天（我們大膽省略多出來的2個多小時）n=64的時候，需要迭代2^ 64次，大概需要2^33天，額，大概我是等不到那一天的，
總結
理解漢諾塔問題的關鍵就是要理解它的遞回思想，以及只關心自己的任務，分派出去的任務只用關心它最后的結果，至于程序則不要去過多地關注
我的博客中還有一篇關于函式遞回的問題：青蛙跳臺階如果有興趣也可以看看
最后感謝各位的閱讀，如果覺得有用，請幫忙點個贊吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277715.html
標籤：其他
上一篇：2021最適合Java程式員學習路線，面經和面試題1000道
下一篇：漢諾塔遞回問題（C語言）