費氏數列(Fibonacci)

Fibonacci on wiki

使用遞回

/*
 * @parama n 第n項(n為正整數)
 * @return 第n項的值
 */
function fibonacci(n)
    if n <= 1
        return n
    return fibonacci(n-1) + fibonacci(n-1)
end

使用迭代

/*
 * @parama n 第n項(n為正整數)
 * @return 第n項的值
 */
function fibonacci(n)
    if n <= 1
        return n
    int a=0, b=1,t;
    for i = 2 to n do
        t = a+b
        a = b
        b = t
    end
    return b
end

使用cache優化遞回

/*
 * @parama n 第n項(n為正整數)
 * @return 第n項的值
 */
function fibonacci(n)
    static Array cache ||= {0,1}
    if cache[n] not null
        return cache[n]
    cache[n] = fibonacci(n-1) + fibonacci(n-1)
    return cache[n]
end

我在Github上使用Ruby的實作

Fork me on github