[計算機概論] 第十講、Algorithms
斐波那契數列的解法有兩種寫法
一種是寫 for 迴圈
func fib(n int) int {
if n == 0 {
return 0
}
pre, post := 0, 1
f := pre + post
for i := 0; i < n-2; i++ {
pre = post
post = f
f = pre + post
}
return f
}
一種是遞迴函數呼叫
func fib(n int) int {
if n == 0 {
return 0
} else if n == 1 {
return 1
}
return fib(n-1) + fib(n-2)
}
用過遞迴的人都知道，他的威利相當大，(function call)
但是遞迴呼叫相當浪費時間，而且會重複計算，暫存、暫存，也很耗記憶體。
看 LeetCode 跑的結果就知道
 |
| for 迴圈 |
 |
| 遞迴 |
計概于老師說了一個性向測驗，滿有趣的，分享給大家：
問題一、假設今天有一鍋冷湯，放在椅子上，旁邊有一個火爐，
你要把湯加熱，你會怎麼做？
受試者們：把椅子上的湯拿去火爐加熱
恭喜受試者們通過第一個問題，代表你有基本智商:))
問題二、假設天今天有一鍋湯，放在桌子上，旁邊有一張椅子跟一個火爐，
你要把湯加熱，你會怎麼做？
A1: 把湯拿去火爐加熱 -->你適合念 工程系
A2: 把湯放到椅子上，如此我們就可以回到問題一，用題一的解法 --> 你適合念 Computer Science
A3: 這是一個很有趣的問題 —> 你適合念 哲學系
回答把湯放到椅子上的，其實就是遞迴
寫過 OO (object oriented programming) 的人就知道，有些寫過的 code 會想要復用，可以，但要注意效率
Comments
Post a Comment