斐波纳契数列求和,本章我们将对斐波那契数列中取值不大于四百万且为偶数的项进行求和运算。斐波纳契数列是从0开始的一个整数序列,除了第一项和第二项是0和1之外,其余各项的取值都是该项之前的两项求和的结果。
也可以认为斐波那契数列的第一项为1,把0看作第零项并省略不写。
有关斐波那契数列的更多信息,请参阅维基百科页面 http://en.wikipedia.org/wiki/Fibonacci_number的相关介绍。
本章使用了一个基于黄金比例(golden ratio)的公式。黄金比例就是一个无理数,有着类似于π的独特属性。我们将用到sqrt
、log
、arange
、astype
和sum
函数。
具体步骤
首先需要计算黄金比例(http://en.wikipedia.org/wiki/Golden_ratio)。黄金比例也被称作黄金分割(golden section或golden mean)。
- 计算黄金比例。
我们将使用sqrt
函数计算5的平方根:
phi = (1 + numpy.sqrt(5))/2
print "Phi", phi
这样就得到了黄金分割数:
Phi 1.61803398875
- 确定小于四百万的项的最大索引值。
接下来,需要确定斐波那契数列中小于四百万的项的最大索引值。我们将用维基百科页面中给出的一个公式计算这个索引值。我们需要做的是使用log
函数,把对数的底数转换一下。不需要对计算的结果向下取整,本攻略的下一步骤将自动完成取整操作。
n = numpy.log(4 * 10 ** 6 * numpy.sqrt(5) + 0.5)/numpy.log(phi)
print n
n的计算结果是:
33.2629480359
- 创建一个从1到n的数组。
arange
函数是一个非常基本的函数,想必大家都熟悉。为了内容的完整性,我们这里还是专门提一下。
n = numpy.arange(1, n)
- 计算斐波那契数列。
有一个方便的公式,可以用来计算斐波那契数列。需要把黄金比例和上一步骤创建的数组作为该公式的输入参数。
为了检查计算的结果,把计算得到的斐波那契数列的前9个数打印出来:
fib = (phi**n - (-1/phi)**n)/numpy.sqrt(5)
print "First 9 Fibonacci Numbers", fib[:9]
单元测试用来测试一个小的代码单元(例如函数)的正确性。可以用单元测试代替打印语句,这个作为练习留给读者自己完成。
顺便注意一下,数列的第一项是1。上述代码生成了我们预期的数列:
First 9 Fibonacci Numbers [ 1. 1. 2. 3. 5. 8. 13. 21. 34.]
如果你愿意,可以把这个结果用在单元测试中。
- 转换为整数。
这个步骤是可选的,但我想最终结果最好还是转换为整数。实际上,我是想介绍astype
函数。
fib = fib.astype(int)
print "Integers", fib
上述代码生成如下结果(简洁起见,省略了部分内容):
Integers [ 1 1 2 3 5 8 13 21 34
... 省略 ... 省略 ...
317811 514229 832040 1346269 2178309 3524578]
- 选出数列中取值为偶数的项。
本攻略要求我们选出数列中取值为偶数的项。如果已经学习过了上一章中的布尔型索引,这应该不难实现。
eventerms = fib[fib % 2 == 0]
print eventerms
我们得到的是:
[ 2 8 34 144 610 2584 10946 46368 196418 832040 3524578]
本攻略的完整代码如下。
import numpy
#斐波那契数列中的每一新项都是由该项之前的两项相加得到的。
#如果第一项和第二项分别为1和2,数列的前十项如下:
#1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
#只考虑斐波那契数列中取值不超过四百万的项,
#对其中取值为偶数的项进行求和运算。
#1. 计算黄金比例phi
phi = (1 + numpy.sqrt(5))/2
print "Phi", phi
#2. 确定取值小于四百万的项的最大索引值
n = numpy.log(4 * 10 ** 6 * numpy.sqrt(5) + 0.5)/numpy.log(phi)
print n
#3. 创建一个从1到n的数组
n = numpy.arange(1, n)
print n
#4. 计算斐波那契数列
fib = (phi**n - (-1/phi)**n)/numpy.sqrt(5)
print "First 9 Fibonacci Numbers", fib[:9]
#5. 转换为整数
# 可选的步骤
fib = fib.astype(int)
print "Integers", fib
#6. 选出取值为偶数的项
eventerms = fib[fib % 2 == 0]
print eventerms
#7. 对选出的项求和
print eventerms.sum()
攻略小结
在本章中,我们用到了sqrt
、log
、arange
、astype
和sum
函数。它们的功能描述如下:
函数 | 功能描述 |
---|---|
sqrt |
计算数组元素的平方根 |
log |
计算数组元素的自然对数 |
arange |
生成一个指定范围的数组 |
astype |
把数组元素转换为指定的数据类型 |
sum |
计算数组元素之和 |