lua, python, JavaScript實現斐波拉菲求解

前端時間看到了一段lua代碼:

-- fibonacci function with cache

-- very inefficient fibonacci function
function fib(n)
    N=N+1
    if n<2 then
        return n
     else
        return fib(n-1)+fib(n-2)
    end
end

fib2 = function(n)
    N=N+1
    if n<2 then
        return n
    else
        return fib(n-1)+fib(n-2)
    end
end

-- a general-purpose value cache
function cache(f)
    local c={}
    return function (x)
        local y=c[x]
        if not y then
            y=f(x)
            c[x]=y
        end
        return y
    end
end

-- run and time it
function test(s,f)
    N=0
    local c=os.clock()
    local v=f(n)
    local t=os.clock()-c
    print(s,n,v,t,N)
end

n=arg[1] or 24        -- for other values, do lua fib.lua XX
n=tonumber(n)
print("","n","value","time","evals")
test("plain",fib)
fib=cache(fib)
test("cached",fib)

此前一直沒有看懂. 今天QQ群里的朋友"天接水"告訴我, function cache(f) 采用了動態規劃的算法.
經這一點撥, 我才明白.

下面這段是我用 python 寫的.

# 遵守BSD協議.


def cache(func):
    c = {0:0, 1:1, 2:1}
    def result(*args,**dic):
        if c.has_key(args[0]):
            y = c[args[0]]
        else:
            y = func(*args,**dic)
            c[args[0]] = y
        return y
    return result


@cache
def fib(n):
    if n > 2:
        return fib(n-1)+fib(n-2)
    elif n in (1, 2):
        return 1
    else:
        return 0
#求fib 200
fib(200)

下面這段程序中, fibonacci函數是由 琳琳的小狗 提供

<script language="JavaScript">
<!--
/**
 * QQ昵稱 :琳琳的小狗 提供.


 * 謝謝 QQ昵稱為"琳琳的小狗"朋友 (來自 QQ群: python 愛好者)


*/
var fibonacci = function ( ) {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fib(n - 1) + fib(n - 2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
}( );
document.write(fibonacci(1000))
//-->

</script>

謝謝天接水, 謝謝琳琳的小狗