題目連結: https://leetcode.com/problems/fibonacci-number/
練習提問:
Q: n的range? Ans: 0 ~ 30
Note: 假設Int是64 bits,則fib(93)會大於Int64.max
Note: 假設Int是32 bits,則fib(47)會大於Int32.max
法ㄧ(Recursive version):
func fib(_ n: Int) -> Int {
if n == 0 { return 0 }
else if n == 1 { return 1 }
else {
return fib(n-1) + fib(n-2)
}
}
法二(Iterative version):
func fib(_ n: Int) -> Int {
if n == 0 { return 0 }
else if n == 1 { return 1 }
else {
var arr = Array(repeating: 0, count: n + 1)
arr[1] = 1
for i in 2 ... n {
arr[i] = arr[i-1] + arr[i-2]
}
return arr[n]
}
}