Fibonacci.java

package algorithm.basicMath;

import org.junit.Test;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class Fibonacci {

    /*
        TASK
        Fibonacci 를 계산하는 함수를 작성한다.
     */

    @Test
    public void test() {

        assertThat(calcFiboByFor(5), is(5));
        assertThat(calcFiboByFor(6), is(8));
        assertThat(calcFiboByFor(7), is(13));

        assertThat(calcFiboByRec(5), is(5));
        assertThat(calcFiboByRec(6), is(8));
        assertThat(calcFiboByRec(7), is(13));

        assertThat(fiboByDp(5), is(5));
        assertThat(fiboByDp(6), is(8));
        assertThat(fiboByDp(7), is(13));
    }

    // Iteration version
    public int calcFiboByFor(int num) {
        if (num < 0) return -1;

        int curValue = 0;
        int prevValue = 1;
        int prevPrevValue = 0;

        for (int i = 2; i <= num; i++) {
            curValue = prevValue +prevPrevValue;
            prevPrevValue = prevValue;
            prevValue = curValue;
        }
        return curValue;
    }

    // Recursion version
    public int calcFiboByRec(int num) {
        if (num < 0) return -1;
        if (num < 2) return num;
        return calcFiboByRec(num - 1) + calcFiboByRec(num - 2);
    }

    // Dynamic Programming version
    public int fiboByDp(int num) {
        return calcFibo(num, new int[num + 1]);
    }

    private int calcFibo(int num, int[] cache) {
        if (num < 2) return num;
        if (cache[num] != 0) return cache[num];//in java, int[] is initialized by 0.

        cache[num] = calcFibo(num - 1, cache) + calcFibo(num - 2, cache);
        return cache[num];
    }
}