python：算法竞赛入门之一

计算 斐波那契数列（Fibonacci sequence），不受长整型位数限制。

编写  fibonacci.py  如下

# -*- coding: utf-8 -*-
""" 计算 斐波那契数列（Fibonacci sequence）"""
import sys
from datetime import datetime# 递归函数定义
def fib(n):if n <=0: return 0if n ==1: return 1if n ==2: return 1return fib(n-1) + fib(n-2)# 将递归改为迭代可以把效能提升不少
def fib1(n):x,y = 0,1while n>0:x,y,n = y,x+y,n-1return x# 通过将计算结果保存到 dict中，后面计算时可以取用，称为备忘方式
known = {0:0, 1:1, 2:1}def fib2(n):if n <=0: return 0if n in known: return known[n]res = fib2(n-1) + fib2(n-2)known[n] = resreturn res# main()
if len(sys.argv) ==2:n = int(sys.argv[1])
else:print(' usage: python fibonacci.py n ')sys.exit(1)if n < 3:print(' input n >= 3 ')
else:print(datetime.now())print('fib1(%d)= %d' % (n, fib1(n)))print(datetime.now())print('fib2(%d)= %d' % (n, fib2(n)))print(datetime.now())

运行 python fibonacci.py 1000

结论：fib1(n) 执行速度比 fib2(n) 快，fib(n) 最慢。

编写  fibonacci.lua  如下

-- 计算 斐波那契数列（Fibonacci sequence）
function fibonacci(n, a, b)if n < 0 then return 0 endif n == 0 thenreturn aelsereturn fibonacci(n-1, b, a+b)end
endif #arg > 0 thenlocal n = tonumber(arg[1])if n > 2 thenlocal result = fibonacci(n, 0, 1)print("fib(n)=", result)elseprint(" must n > 2 ")end
elseprint(" usage: lua fibonacci.lua n ")
end

运行 lua54.exe fibonacci.lua 161

fib(n)= 9217463444206948445

运行  lua54.exe fibonacci.lua 162

fib(n)= -969573230286635304  这个结果溢出了