如何教會女友遞歸算法?

一到周末就開始放蕩自我,這不帶着女朋友去萬達電影院看電影(其實是由於整天呆在家敲代碼硬是

被女朋友強行拖拽去看電影,作為一個有理想的程序員,我想各位應該都能體諒我),一到電影院,

女朋友說要買爆米花和可樂,我當時二話沒說,臣本布衣躬耕於南陽,壤中羞澀,所以單買了爆米

花,買完都不帶回頭看老闆的那種,飲料喝多了不好,出門的時候我帶了白開水,還得虧我長得銷

魂,乍一看就能看出是個社會精神小伙,女朋友也沒多說什麼,只是對我微了微笑(我估計是被我的

顏值以及獨到的見解所折服),剛坐下沒多久,女朋友突然問我,咱們現在坐在第幾排啊?電影院里

面太黑了,看不清,沒法數,這個時候,如果是你現在你怎麼辦?別忘了你我是程序員,這個可難不

倒我,遞歸就開始排上用場了。於是我就問前面一排的人他是第幾排,你想只要在他的数字上加一,

就知道自己在哪一排了。但是,前面的人也看不清啊,所以他也問他前面的人。就這樣一排一排往前

問,直到問到第一排的人,說我在第一排,然後再這樣一排一排再把数字傳回來。直到你前面的人告

訴你他在哪一排,於是你就知道答案了。這就是一個非常標準的遞歸求解問題的分解過程,去的過程

叫“遞”,回來的過程叫“歸”。基本上,所有的遞歸問題都可以用遞推公式來表示。我們用遞推公式將

它表示出來就是這樣的

f ( n ) = f (n – 1) + 1 其中,f ( 1 ) = 1

f(n)表示你想知道自己在哪一排,f(n-1)表示前面一排所在的排數,f(1)=1表示第一排的人知道自己在

第一排。有了這個遞推公式,我們就可以很輕鬆地將它改為遞歸代碼,如下:

int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

女朋友不懂遞歸,於是我給她講遞歸需要滿足的三個條件:

1.一個問題的解可以分解為幾個子問題的解

何為子問題?子問題就是數據規模更小的問題。就好比,在電影院,你要知道,“自己在哪一排”的問

題,可以分解為“前一排的人在哪一排”這樣一個子問題。

2.這個問題與分解之後的子問題,除了數據規模不同,求解思路完全一樣

你求解“自己在哪一排”的思路,和前面一排人求解“自己在哪一排”的思路,是一模一樣的。

3.存在遞歸終止條件

把問題分解為子問題,把子問題再分解為子子問題,一層一層分解下去,不能存在無限循環,這就需

要有終止條件。就好比,第一排的人不需要再繼續詢問任何人,就知道自己在哪一排,也就是

f(1)=1,這就是遞歸的終止條件。

如何教女友敲遞歸代碼?

剛剛鋪墊了這麼多,現在我們來看,如何來教女友敲遞歸代碼?個人覺得,寫遞歸代碼最關鍵的是寫

出遞推公式,找到終止條件,剩下將遞推公式轉化為代碼就很簡單了。

你先記住這個理論。我舉一個例子,帶你一步一步實現一個遞歸代碼,幫你理解。

假如這裡有n個台階,每次你可以跨1個台階或者2個台階,請問走這n個台階有多少種走法?如果有7個台階,你可以2,2,2,1這樣子上去,也可以1,2,1,1,2這樣子上去,總之走法有很多,那如何用編程求得總共有多少種走法呢?

我們仔細想下,實際上,可以根據第一步的走法把所有走法分為兩類,第一類是第一步走了1個台

階,另一類是第一步走了2個台階。所以n個台階的走法就等於先走1階后,n-1個台階的走法 加上先

走2階后,n-2個台階的走法。用公式表示就是:

f ( n ) = f (n – 1) + f ( n – 2 )

有了遞推公式,遞歸代碼基本上就完成了一半。我們再來看下終止條件。當有一個台階時,我們不需

要再繼續遞歸,就只有一種走法。所以f(1)=1。這個遞歸終止條件足夠嗎?我們可以用n=2,n=3這樣

比較小的數試驗一下。

n=2時,f(2)=f(1)+f(0)。如果遞歸終止條件只有一個f(1)=1,那f(2)就無法求解了。所以除了f(1)=1這一

個遞歸終止條件外,還要有f(0)=1,表示走0個台階有一種走法,不過這樣子看起來就不符合正常的

邏輯思維了。所以,我們可以把f(2)=2作為一種終止條件,表示走2個台階,有兩種走法,一步走完

或者分兩步來走。

所以,遞歸終止條件就是f(1)=1,f(2)=2。這個時候,你可以再拿n=3,n=4來驗證一下,這個終止條

件是否足夠並且正確。

我們把遞歸終止條件和剛剛得到的遞推公式放到一起就是這樣的:

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

有了這個公式,我們轉化成遞歸代碼就簡單多了。最終的遞歸代碼是這樣的:

int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  return f(n-1) + f(n-2);
}

我總結一下,寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律,並且基於此寫出遞推公式,然後再推敲終止條件,最後將遞推公式和終止條件翻譯成代碼。

如果以後再遇到類似問題,A可以分解為若干子問題B、C、D情況,你可以假設子問題B、C、D已經

解決,在此基礎上思考如何解決問題A。而且,你只需要思考問題A與子問題B、C、D兩層之間的關

系即可,不需要一層一層往下思考子問題與子子問題,子子問題與子子子問題之間的關係。屏蔽掉遞

歸細節,這樣子理解起來就簡單多了。

因此,編寫遞歸代碼的關鍵是,只要遇到遞歸,我們就把它抽象成一個遞推公式,不用想一層層的調

用關係,不要試圖用人腦去分解遞歸的每個步驟

如何教女友玩轉漢羅塔

好了,講完了遞歸算法,再回到電影院,不說別的,我還真那麼做了,我真問了前面一排的人他是第

幾排如果不清楚並讓他跟我一樣問他的上一排,顯然,沒循環到第三人,我差點被認為是神經病,差

點沒被幾個社會精神小伙打si,座位事情暫時告一段落,話說這電影屬實夠無聊,於是我不知是趁熱

打鐵,還是心血來潮,非要給女朋友玩一個漢羅塔遊戲,我這暴脾氣,剛實踐遞歸算法被懟,是時候

挽回形象了,不秀一把遞歸算法我就不得勁。就是這個遊戲,至於遊戲規則,我覺得你體驗一兩把絕

對比我說的更加記憶深刻,,別看4399覺得有點弱zhi,再怎麼說也承

載着童年

果然,女朋友是個哈皮,剛過第三關就撲街了,這個時候,頭冒五丈光芒的我身披金甲挺身而出(貌

似有一點點小誇張,劇情需要嘛)一聲不吭地敲了幾行靚麗的代碼

public class TestHanoi {

    public static void main(String[] args) {
        hanoi(5,'A','B','C');  //可以理解為5個圈或者第5關
    }
    
    /**
     * @param n     共有N個圈
     * @param A    開始的柱子
     * @param B 中間的柱子
     * @param C 目標的柱子
     * 無論有多少個圈,都認為只有兩個。上面的所有圈和最下面一個圈。
     */
    public static void hanoi(int n,char A,char B,char C) {
        //只有一個圈。
        if(n==1) {
            System.out.println("第1個盤子從"+A+"移到"+C);
        //無論有多少個圈,都認為只有兩個。上面的所有圈和最下面一個圈。
        }else {
            //移動上面所有的圈到中間位置
            hanoi(n-1,A,C,B);
            //移動下面的圈
            System.out.println("第"+n+"個圈從"+A+"移到"+C);
            //把上面的所有圈從中間位置移到目標位置
            hanoi(n-1,B,A,C);
        }
    }

}

只要main方法一致行,對着結果移動即可,就跟開了掛一樣的,其實漢羅塔問題核心關鍵是無論有多少個圈,都認為只有兩個。上面的所有圈和最下面一個圈。

到這裏,教女友敲遞歸算法代碼,你學會了嗎?

哦豁,明天還是一個晴天~老天賜給宜春一個女朋友吧~畢竟我們程序員長得又帥敲代碼又好看,是吧哥幾個~~

如果本文對你有一點點幫助,那麼請點個讚唄,謝謝~

最後,若有不足或者不正之處,歡迎指正批評,感激不盡!如果有疑問歡迎留言,絕對第一時間回復!

歡迎各位關注我的公眾號,一起探討技術,嚮往技術,追求技術,說好了來了就是盆友喔…

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

您可能也會喜歡…