第一个 Python 程序：对数级时间求 Fibonacci 数

#!/usr/bin/python
# Filename: fib.py

# increase [f(n), f(n+1)] to [f(n+1), f(n+2)]
def __fib_inc(fib_n):
    fib_n[1] += fib_n[0]
    fib_n[0] = fib_n[1] - fib_n[0]

# convert [f(n), f(n+1)] to [f(2*n), f(2*n+1)]
def __fib_n_2n(fib_n):
    a = fib_n[0]
    b = fib_n[1]
    fib_n[0] = 2 * a * b - a * a
    fib_n[1] = b * b + a * a

# get f(n) by recursion
def __fib(n, fib_n):
    if n == 1:
        return fib_n[0]
    else:
        __fib(n / 2, fib_n)
        __fib_n_2n(fib_n)
        if n % 2 == 1:
            __fib_inc(fib_n)

    return fib_n[0]

# get f(n)
def fib(n):
    if n <= 0:
        return 0
    else:
        return __fib(n, [1, 1])

for i in range(0, 21):
    print i, ":", fib(i)


Python 是一种简单的语言，PHP 似乎也是。享受动态语言的乐趣：）