引言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。
问题描述
斐波那契数列：又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
在数学上，斐波纳契数列以如下递归的方法定义：
计算这个数列中相邻两个数的商值，可以得到如表所示的结果。
1÷1 = 1.00000
2÷1 = 2.00000
3÷2 = 1.50000
5÷3 = 1.66667
8÷5 = 1.60000
13÷8 = 1.62500
21÷13 = 1.61538
34÷21 = 1.61905
55÷34 = 1.61765
89÷55 = 1.61818
可以看到，商值最终慢慢地趋近1.618.这就是有名的“黄金分割”的由来。
如下图所示，用斐波那契数列中的每个数除以数位上的数字之和。请继续例中的计算，求出后续5个最小的能整除的数。
2 → 2 ÷ 2
3 → 3 ÷ 3
5 → 5 ÷ 5
8 → 8 ÷ 8
21 → 21 ÷ 3 ... 2+1=3，因而除以3
144 → 144 ÷ 9 ...1+4+4=9，因而除以9
思路
我们先来定义一个函数，该函数有一个参数n，n为整数，表示整数n是否能被该整数数位上的数字之后整除。
def if_div(n):
length = len(str(n)) # 该整数共几位数
sum = 0
# 将各个位数上的数相加
for i in range(length):
sum = int(str(n)[i]) + sum
if(n % sum ==0): # 如果整除，返回True
return True
return False
不采用的方式
按照斐波那契数列的定义，我们可以写出斐波那契数列中第n个值的函数
def fib(n):
if n==0 or n==1:
return 1
else:
return fib(n-2) + fib(n-1)
如果我们直接按题意，依次遍历斐波那契数列，直到拿到我们所需要11个数为止，而数列中的每一个数都有函数fib(n)计算出来。即
import time
begin = time.time()
print("------计算开始-----")
count = 0
n = 2
while(count<8):
value = fib(n)
if if_div(value):
count = count + 1
print(str(count)+': '+ str(value))
n = n + 1
end = time.time()
print("------计算结束-----")
print("耗时"+str(float(end-begin)))
注意到，我只拿到符合题意的8个数，就已经耗时15秒了，第9个数，耗时就很长了，我曾经花了1天时间都没结果出来，第10个数就更不用说了。
这说明了一个什么问题？
递归可能更容易理解，但程序的性能上不具优势，尤其当递归层次深时。
优雅方式
往往可以用递归方式的，基本上有更优的方式。
a,b,c是斐波那契数列中的连续3个数，根据定义则有a+b=c, 下一个连续3个数依然是a,b,c，只不过这时的a是前一个的b，这时的b是前一个的a，而这时的c是这时的a+b的和，依次往下。
import time
begin = time.time()
print("------计算开始-----")
a = b = 1
count = 0
while(count < 11):
c = a + b
if if_div(c):
count = count + 1
print(str(count)+': '+ str(c))
a, b = b, c
end = time.time()
print("------计算结束-----")
print("耗时"+str(float(end-begin)))
非常快，2毫秒就给出答案了。
