(給算法愛好者加星標,修煉編程內功)
來源:山大王wld
算法題儘量做到難易結合,在我們看一些難題的時候偶爾也可以看一些非常簡單又非常容易看懂的題,要不然算法題一直看不懂,容易打擊大家的興趣,今天來看一道非常簡單又非常常見的算法題,就是漢諾塔問題,這道題我想只要是學過編程的同學都應該知道的。
關於漢諾塔的傳說
漢諾塔:漢諾塔(又稱河內塔)問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。
漢諾塔還有另外一個版本
漢諾塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒( Pag)所支撐,開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤(Disc) ,並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子,則當盤子全數搬運完畢之時,此塔將毀損, 而也就是世界末日來臨之時
我們這裡不去追本溯源,追究他哪個版本是正確的,我們知道有這樣一道題就行,直接文字敘述可能不太直觀,我們畫個圖來分析一下
1,當只有一個的時候
2,當只有2個的時候
3,當只有3個的時候
當n等於3的時候移動的步數就比較多了,我們就不再畫圖了,我們來看一個動畫
4,當只有4個的時候
5,當有n個的時候
這裡主要還是考察對遞歸的理解,其實遞歸我們沒必要把每一步都推出來,我們只需要找到他的規律和邊界條件就行了,就像前面我們講356,青蛙跳臺階相關問題的時候,我們提到了斐波那契數列,我們只需要找到斐波那契的規律f(n)=f(n-1)+f(n-2),和他的邊界條件f(0)=f(1)=1我們就可以寫出代碼了,其他的我們就不用管了。
故事篇
這裡我來給大家講個故事吧,很久很久以前有一個人,名叫「孤獨求敗」,他和家人住在山下過著與世無爭的生活,就這樣每天日出而作日落而息。有一天他從山上砍柴回來,突然看到家人遇害,他悲痛欲絕,於是決定給家人報仇,但他武藝不行,而仇人的功夫很高,如果硬拼不但報不了仇,而且還會白白丟了性命,所以他決定先去習武。
那天他來到一座山上,看到一個老和尚,向他說明了緣由,老和尚聽聞之後怒火中燒,一腳把門前的一個千斤石獅踢開,想幫孤獨求敗報仇,但又怕得罪他的仇人導致引火燒身,所以他就對孤獨求敗說:「此仇只有你自己能報」。
孤獨求敗:「可我功夫不行,根本報不了仇」。
老和尚;「別急,請跟我來」。
於是老和尚帶他來到了一間很破舊的房子裡,指著裡面的一個滿是灰塵的破柜子說;「武功秘籍就鎖在這裡面,你拿到鑰匙打開它,把它拿回去自己修煉,等你功夫達到十級之後就可以找你的仇人報仇了」。
然後找來了他的大徒弟對孤獨求敗說,這是你的大師兄,鑰匙你找他要,我要回去睡覺了。然後大師兄說鑰匙鎖在我自己的小盒子裡了,我小盒子的鑰匙在二師兄拿著,你先去找二師兄把我這小盒子的鑰匙拿到,我把這個小盒子打開,就可以把鎖柜子的鑰匙給你了。
於是孤獨求敗又去找到了二師兄,然後二師兄說,大師兄的鑰匙被我鎖在了我自己的小盒子裡了,我自己的小盒子的鑰匙在三師兄拿著……
就這樣,孤獨求敗一直找下去,直到找到最小的100師兄拿到鑰匙,然後交給第99師兄,打開第99師兄的小盒子,拿到第98師兄的鑰匙,又交給第98師兄……一直到大師兄,然後大師兄拿到鑰匙打開自己的小盒子,把藏有武功秘籍的柜子鑰匙交給孤獨求敗,這樣孤獨求敗就拿到了武功秘籍,回家修煉去了……
孤獨求敗從大師兄開始到拿到武功秘籍的過程其實就是遞歸。
讀懂了上面的故事,再來看漢諾塔問題就容易多了,我們來看下代碼。
1//表示的是把n個圓盤成功的從A移動到C
2public static void hanoi(int n, char A, char B, char C) {
3 if (n == 1) {
4 //如果只有一個,直接從A移動到C即可
5 System.out.println("從" + A + "移動到" + C);
6 } else {
7 //表示先把n-1個圓盤成功從A移動到B
8 hanoi(n - 1, A, C, B);
9 //把第n個圓盤從A移動到C
10 System.out.println("從" + A + "移動到" + C);
11 //表示把n-1個圓盤再成功從B移動到C
12 hanoi(n - 1, B, A, C);
13 }
14}
我們還可以把每個柱子看作是一個棧,大的在下面,小的在上面,所以我們也可以使用棧來實現
1//stackA 源柱 stackB 藉助柱 stackC目的柱
2public static void move(Stack stackA, Stack stackB, Stack stackC, int n) {
3 if (n == 1) {
4 stackC.push(stackA.pop());
5 } else {
6 move(stackA, stackC, stackB, n - 1);
7 stackC.push(stackA.pop());
8 move(stackB, stackA, stackC, n - 1);
9 }
10}
如果想要統計總共移了多少次,可以使用公式(2^n)-1,代碼如下
1public static long hanoiCount(int n) {
2 return (1L << n) - 1;
3}
當n=63的時候,我們得到9223372036854775807,當n=64的時候就已經出現了數字溢出。
覺得本文有幫助?請分享給更多人
關注「算法愛好者」加星標,修煉編程內功
好文章,我在看❤️