摘要:由此可知在前柱是中轉柱在之后也有兩種情況只有上有圓盤。并且我們的游戲目標從一開始的把上所有圓盤移到柱變成了把上所有圓盤移到柱上而在這時中轉柱是柱。現在將步驟分為三個小步驟將上個圓盤全部移到柱上中轉柱柱。
? 漢諾塔是一種古印度游戲,該游戲的實質就是在一塊木板上有三根固定的柱子
而在左邊的柱子上有著n個大小不同的圓盤,我們需要做就是把左邊所有的盤子全部移到右邊的柱子上。操作規則:1.圓盤在柱子上必須按照從大到?。ù髨A盤在下)依次排列。2.每次只能移動圓柱最上面的圓盤。
問題分析:先假設三根柱子分別為“A”"B""C",A柱有著所有的初始盤,我們的目的就是把A柱上的所有盤子全部移到C柱上。
n=1時,直接把圓盤從A柱移動到C柱就可。
n=2時,A-->B,A-->C,B-->C。(在這操作中B為中轉柱)
n=3時,A-->C,A-->B,C-->B,①A-->C,B-->A,B-->C,A-->C。對n=3這種情況進行分析:在①之前圓盤所在圓柱的情況有兩種:
1.是所有圓盤在A,B,C三個圓柱中都有一個圓盤。
2.是A,C上有圓盤而B上沒有圓盤。
由此可知在①前B柱是中轉柱;在①之后也有兩種情況:
1.只有B,C上有圓盤。
2.A,B,C上都有一個圓盤。
并且我們的游戲目標從一開始的把A上所有圓盤移到C柱(A-->C),變成了把B上所有圓盤移到C柱上(B-->C),而在這時中轉柱是A柱。
......
直到A上有n個圓盤時,現在對n這種情況進行分析:想要把n個圓盤從A柱移到C柱上有三大步驟:
①將A上n-1個圓柱全部移到C柱上(中轉柱B柱)。
②將A上的一個圓盤移到C柱上。
③將B上n-1個圓盤全部移到C柱上(中轉柱A柱)。
在這要穿插一下遞歸的主要思想就是大事化小?,F在將①步驟分為三個小步驟:
①將A上n-2個圓盤全部移到C柱上(中轉柱B柱)。
②將A上第n-1個圓盤移到B柱上。
③將C上n-2個圓盤移到A柱上(中轉柱A柱)。
然后將第二個①化為更小的三個步驟......就這樣一步步大事化小。
代碼實現:
#includevoid hanoi(int n, char post_1, char post_2, char post_3){ if (n == 1) { printf("%c --> %c/n", post_1, post_3); } else { hanoi(n - 1, post_1, post_3, post_2); printf("%c --> %c/n", post_1, post_3); hanoi(n - 1, post_2, post_1, post_3); }}int main(){ int n = 0; char a = "A", b = "B", c = "C"; scanf("%d", &n); hanoi(n, a, b, c); return 0;}
? 一只青蛙一次可以跳上1級臺階,也可以跳上2級臺階。求該青蛙跳上一個n級臺階有多少種跳法?(實質就是斐波那契數列的變種)
問題分析:
我們不妨列舉一下n比較少的情況時的跳法:
①n=1時,1種跳法。????????? ②n=2時,有2種跳法。
③n=3時,有3種跳法。????? ④n=4時,有5種跳法。
⑤n=5時,有8種跳法。
......
很明顯,同過觀察上面列舉的情況可以發現:
n=3時所有的跳法等于n=1時和n=2時的所有跳法之和;
n=4時的所有跳法等于n=2和n=3時的所有跳法之和;
......
以此類推可以得出f(n)=f(n-1)+f(n-2) (n>2)。(f(n)為跳法數量)
?
代碼實現:
#includeint frogjump(int n){ if (n == 1) { return 1; } else if (n == 2) { return 2; } else { return frogjump(n - 1) + frogjump(n - 2); }}int main(){ int n = 0; scanf("%d", &n); printf("%d", frogjump(n)); return 0;}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/123073.html
摘要:程序員小吳打算使用動畫的形式來幫助理解遞歸,然后通過遞歸的概念延伸至理解動態規劃算法思想。因此,分治策略一般用來解決子問題相互對立的問題,稱為標準分治,而動態規劃用來解決子問題重疊的問題。難點就在于找出動態規劃中的這三個概念。 在學習「數據結構和算法」的過程中,因為人習慣了平鋪直敘的思維方式,所以「遞歸」與「動態規劃」這種帶循環概念(繞來繞去)的往往是相對比較難以理解的兩個抽象知識點。...
摘要:漢諾塔問題有三根柱子,源桿,暫存桿,目的桿上有層盤子,由小到大向下排列,現需要將桿的盤子移到桿中要求大的盤在下面,小的盤在上面一次只能移動一個盤子個人思路先分析問題,用數學的歸納法當只有一個盤時,直接移動當有兩個盤時,先將小的移到暫存桿,再 漢諾塔問題: 有三根柱子,源桿A,暫存桿temp,目的桿C A上有n層盤子,由小到大向下排列,現需要將A桿的盤子移到C桿中 ...
摘要:一個小青蛙可以一次跳兩節樓梯也可以一次跳一節樓梯請問他如果要跳節樓梯一共有幾種跳法方案問題的描述很簡單看到這個題目的時候我首先想到的就是舉例分析一波比如當的時候有幾種方案當的時候有幾種方案等等我們首先分析一波當的時候這個時候小青蛙只有一種跳 一個小青蛙,可以一次跳兩節樓梯,也可以一次跳一節樓梯,請問他如果要跳101節樓梯,一共有幾種跳法方案? 問題的描述很簡單,看到這個題目的時候,我首...
閱讀 2836·2021-11-19 09:40
閱讀 3695·2021-11-15 18:10
閱讀 3281·2021-11-11 16:55
閱讀 1231·2021-09-28 09:36
閱讀 1647·2021-09-22 15:52
閱讀 3367·2019-08-30 14:06
閱讀 1160·2019-08-29 13:29
閱讀 2307·2019-08-26 17:04