101北一女中 資訊選手培訓營 遞迴、河內塔與merge sort 2012.07.01 Nan
遞迴,原來是這麼回事 讓我們從函數執行來了解遞迴的真義
你一定聽過一種說法…… 「函數,就像一個黑盒子, 你給他input,他就給你output。」 但你知道實際上程式在呼叫與執行函數時是怎麼回事嗎?
讓我們用費伯納基數列來舉例說明……
這是一個可以計算出費伯納基數的函數
他的input是一個數n,代表我們要的是第n項的費伯納基數
而這就是黑盒子裡面做的事情:遞迴呼叫和處理邊界情況
直到輸入為0或1時(邊界情況),結束遞迴 N=n-1 N-1 N-2 … n - 1 n - 2 … M=n-2 M-1 M-2 … …
放到真實的code中來看 每次呼叫實際上是新產生一段會照著這段code的步驟一一執行的CPU指令, 並給他參數n,讓他可以套進這段code所產生的CPU指令裡面。 n = 1 fib(3) fib(3) = 2 回傳值=1 n = 2 回傳值=1 + 0 = 1 n = 0 n = 3 回傳值=0 回傳值=1 + 1 = 2 n = 1 回傳值=1
搬完就世界末日的塔 經典遞迴問題: 河內塔
河內塔的故事與規則 一次只能動一個盤子 小的不能在大的下面 目標是把所有盤子移到第三根柱子 “河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒(Pag)所支撐,開始時神在第一根棒上放置64個由上至下依由小 至大排列的金盤(Disc),並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子,則當 盤子全數搬運完畢之時,此塔將毀損,而也就是世界末日來臨之時。” -- http://caterpillar.onlyfun.net/Gossip/AlgorithmGossip/HanoiTower.htm 一次只能動一個盤子 小的不能在大的下面 目標是把所有盤子移到第三根柱子
http://notepad.yehyeh.net/Content/DS/CH02/4.php
先從基礎的2個盤子開始看 A B C AB A B C A B C A B C AC BC
“把上面的大盤子從A移到B和從B移到C的這件事, 如果是三個以上…… A B C 就把除了最後一個盤子之外的所有盤子看成一個盤子→ AB A B C A B C A B C AC BC “把上面的大盤子從A移到B和從B移到C的這件事, 正是另一個河內塔問題。”
Pseudo Code
講了這麼多, 到底什麼時候會用到遞迴呢? 分而治之 “Divide and Conquer” “大的問題可以切成小的問題來做, 做完再湊出大的問題的解答”
遞迴與分而治之 (Divide and Conquer) 合併排序 Merge Sort 遞迴與分而治之 (Divide and Conquer)
排序問題 “給你一堆數字,請你把他按照大小順序排好。” 之前你可能有學過泡泡排序(bubble sort) 它的worst case複雜度是O(n2),有更好的做法嗎?
有!我們有合併排序(merge sort)! 合併排序的特點: 採用遞迴—分而治之 O(nlogn),排序問題的最佳解之一 用空間換取時間
請準備一副撲克牌,拿出其中一個花色的七張牌, 讓我們來實際操作一下吧! 請準備一副撲克牌,拿出其中一個花色的七張牌, 隨意洗牌,再把它攤在桌上排一排
Pseudo Code