資訊專欄INFORMATION COLUMN
摘要：由此可知在前柱是中轉(zhuǎn)柱在之后也有兩種情況只有上有圓盤。并且我們的游戲目標(biāo)從一開始的把上所有圓盤移到柱變成了把上所有圓盤移到柱上而在這時中轉(zhuǎn)柱是柱?，F(xiàn)在將步驟分為三個小步驟將上個圓盤全部移到柱上中轉(zhuǎn)柱柱。
? 漢諾塔是一種古印度游戲，該游戲的實質(zhì)就是在一塊木板上有三根固定的柱子
而在左邊的柱子上有著n個大小不同的圓盤，我們需要做就是把左邊所有的盤子全部移到右邊的柱子上。操作規(guī)則：1.圓盤在柱子上必須按照從大到?。ù髨A盤在下）依次排列。2.每次只能移動圓柱最上面的圓盤。
問題分析：先假設(shè)三根柱子分別為“A”"B""C",A柱有著所有的初始盤，我們的目的就是把A柱上的所有盤子全部移到C柱上。
n=1時，直接把圓盤從A柱移動到C柱就可。
n=2時，A-->B,A-->C,B-->C。（在這操作中B為中轉(zhuǎn)柱）
n=3時，A-->C,A-->B,C-->B,①A-->C,B-->A,B-->C,A-->C。對n=3這種情況進(jìn)行分析：在①之前圓盤所在圓柱的情況有兩種：
1.是所有圓盤在A,B,C三個圓柱中都有一個圓盤。
2.是A，C上有圓盤而B上沒有圓盤。
由此可知在①前B柱是中轉(zhuǎn)柱；在①之后也有兩種情況：
1.只有B,C上有圓盤。
2.A,B,C上都有一個圓盤。
并且我們的游戲目標(biāo)從一開始的把A上所有圓盤移到C柱（A-->C）,變成了把B上所有圓盤移到C柱上（B-->C）,而在這時中轉(zhuǎn)柱是A柱。
......
直到A上有n個圓盤時,現(xiàn)在對n這種情況進(jìn)行分析：想要把n個圓盤從A柱移到C柱上有三大步驟：
①將A上n-1個圓柱全部移到C柱上（中轉(zhuǎn)柱B柱）。
②將A上的一個圓盤移到C柱上。
③將B上n-1個圓盤全部移到C柱上（中轉(zhuǎn)柱A柱）。
在這要穿插一下遞歸的主要思想就是大事化小。現(xiàn)在將①步驟分為三個小步驟：
①將A上n-2個圓盤全部移到C柱上（中轉(zhuǎn)柱B柱）。
②將A上第n-1個圓盤移到B柱上。
③將C上n-2個圓盤移到A柱上（中轉(zhuǎn)柱A柱）。
然后將第二個①化為更小的三個步驟......就這樣一步步大事化小。
代碼實現(xiàn)：
#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級臺階有多少種跳法？（實質(zhì)就是斐波那契數(shù)列的變種）
問題分析：
我們不妨列舉一下n比較少的情況時的跳法：
①n=1時，1種跳法。????????? ②n=2時，有2種跳法。
③n=3時，有3種跳法。????? ④n=4時，有5種跳法。
⑤n=5時，有8種跳法。
......
很明顯，同過觀察上面列舉的情況可以發(fā)現(xiàn)：
n=3時所有的跳法等于n=1時和n=2時的所有跳法之和；
n=4時的所有跳法等于n=2和n=3時的所有跳法之和；
......
以此類推可以得出f(n)=f(n-1)+f(n-2) (n>2)。（f(n)為跳法數(shù)量）
?
代碼實現(xià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;} 文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/123073.html
摘要：程序員小吳打算使用動畫的形式來幫助理解遞歸，然后通過遞歸的概念延伸至理解動態(tài)規(guī)劃算法思想。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。難點就在于找出動態(tài)規(guī)劃中的這三個概念。 在學(xué)習(xí)「數(shù)據(jù)結(jié)構(gòu)和算法」的過程中，因為人習(xí)慣了平鋪直敘的思維方式，所以「遞歸」與「動態(tài)規(guī)劃」這種帶循環(huán)概念（繞來繞去）的往往是相對比較難以理解的兩個抽象知識點。...
摘要：漢諾塔問題有三根柱子，源桿，暫存桿，目的桿上有層盤子，由小到大向下排列，現(xiàn)需要將桿的盤子移到桿中要求大的盤在下面，小的盤在上面一次只能移動一個盤子個人思路先分析問題，用數(shù)學(xué)的歸納法當(dāng)只有一個盤時，直接移動當(dāng)有兩個盤時，先將小的移到暫存桿，再 漢諾塔問題： 有三根柱子，源桿A，暫存桿temp，目的桿C A上有n層盤子，由小到大向下排列，現(xiàn)需要將A桿的盤子移到C桿中 ...
摘要：一個小青蛙可以一次跳兩節(jié)樓梯也可以一次跳一節(jié)樓梯請問他如果要跳節(jié)樓梯一共有幾種跳法方案問題的描述很簡單看到這個題目的時候我首先想到的就是舉例分析一波比如當(dāng)?shù)臅r候有幾種方案當(dāng)?shù)臅r候有幾種方案等等我們首先分析一波當(dāng)?shù)臅r候這個時候小青蛙只有一種跳 一個小青蛙,可以一次跳兩節(jié)樓梯,也可以一次跳一節(jié)樓梯,請問他如果要跳101節(jié)樓梯,一共有幾種跳法方案? 問題的描述很簡單,看到這個題目的時候,我首...
摘要：學(xué)編程，學(xué)，算法也是必不可缺的，這一次給大家?guī)硪粋€經(jīng)典的遞歸算法題，漢諾塔。當(dāng)我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠(yuǎn)是目標(biāo)柱，我們不需要去移動它。 學(xué)編程，學(xué)IT，算法也是必不可缺的，這一次給大家?guī)硪粋€經(jīng)典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程 什么是漢諾塔？ 我這里直接拉來一個圖解釋一下（掛了請聯(lián)系我）sho...
閱讀 2849·2021-11-19 09:40
閱讀 3709·2021-11-15 18:10
閱讀 3290·2021-11-11 16:55
閱讀 1246·2021-09-28 09:36
閱讀 1663·2021-09-22 15:52
閱讀 3376·2019-08-30 14:06
閱讀 1171·2019-08-29 13:29
閱讀 2318·2019-08-26 17:04
