DAY 11
0
Software Development

# 費氏數列(Fibonacci numbers)

Example

``````fib(10) -> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

fib(6) -> [0, 1, 1, 2, 3, 5, 8]

``````

## JavaScript 解法

### js 迴圈解

``````function fib(n) {
const result = [0, 1];

for (let index = 2; index <= n; index++) {
// 倒數第一個數
const a = result[index - 1]; // or result[result.length -1]

// 倒數第二個數
const b = result[index - 2];

result.push(a + b);
}
console.log('full array: ' + result)
console.log('last number: ' + result[result.length -1])
return result[result.length -1];
}
``````

### js 遞迴解(Recursion)

``````function fib(n) {
if (n < 2) {
return n;
}

return fib(n - 1) + fib(n - 2);
}
``````

``````fib(5) 會去做 fib(4)與 fib(3)

fib(4) -> fib(3) -> fib(2) -> fib(1), fib(0) -> 1
-> fib(1) -> 1

-> fib(2) -> fib(1), fib(0) -> 1

fib(3) -> fib(2) -> fib(1), fib(0) -> 1
-> fib(1) -> 1

``````

## Java 解法

### Java 迴圈解

``````private static int fib1(int n) {
int theLastTwo = 0, theLastNum = 1, temp;

if (n == 0)
return theLastTwo;

for (int index = 2; index <= n; index++) {
temp = theLastTwo + theLastNum;
theLastTwo = theLastNum;
theLastNum = temp;
}

System.out.println("the Last Two " + theLastTwo);
System.out.println("the Last Number " + theLastNum);
return theLastNum;
}
``````

### Java 遞迴解

``````public class FibonacciEx1 {

static private int fib(int n) {
if (n <= 1)
return n;

return fib(n - 1) + fib(n - 2);
}

public static void main(String[] args) {
System.out.println(fib(5));
}

}
``````