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

BenBear

                                               
               
                #!/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 似乎也是。享受动态语言的乐趣：）
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/24581/showart_265237.html