#INT104 #Python
斐波那契数列是一个非常经典的数列,它的定义是:第0项为0,第1项为1,从第2项开始,每一项都等于前两项之和。
但是我们正常来说是不用第0项的,是从第一项开始。
所以他的形式是:[1, 1, 2, 3, 5, 8, 13, 21]。
在 INT104 的 Tutorial 3 上,我发现老师的解法,我的解法,copilot的解法,朋友的解法全都不尽相同。这就很有意思了,所以就想写一篇博客来汇总一下。
在此总结4种使用Python的解法:
1. 递归
1 | def fibonacci(n): |
首先,我们定义了一个递归函数 fibonacci
,它接受一个参数 n
,如果 n
小于等于1,就返回 n
,否则返回 fibonacci(n - 1) + fibonacci(n - 2)
,利用递归,让前两位数字相加,来生成后一位数。这个n
就是指生成的数列的第n项。
然后我们定义了一个函数 generateFibonacciList
,用来把函数fibonacci
生成的数字加入到数组numList
里,并在最后得以返回这个数组。在调用时,我们传入 8
,就会返回 [1, 1, 2, 3, 5, 8, 13, 21]
,一个长度为8的斐波那契数列。
2. 循环
1 | def fibonacci(n): |
这个方法理论上应该是最容易想的,相对来说也是最好写的方法 —— 使用while
循环来生成斐波那契数列:定义一个函数 fibonacci
,它接受一个参数 n
,在numList
长度不够n
时,执行循环,而在数列前两位一定是[1, 1],所以在这两位直接numList.append(1)
;在大于两位后的位置,我们再使用斐波那契数列的原理 —— 这个位的数字等于前两个位的数相加。最后返回一个长度为 n
的斐波那契数列。在调用时,我们传入 8
,就会返回 [1, 1, 2, 3, 5, 8, 13, 21]
,一个长度为8的斐波那契数列。
值得一提的是,在Python中,numList[-1]
表示该数列的最后一位,numList[-2]
表示倒数第二位。
3. for + range
1 | def fibonacci(num): |
这个是我本人最喜欢的一个解法:巧妙的使用range
。
首先,我们定义一个初始的斐波那契数列:fib_list = [1, 1]
,然后在此基础上我们在后面利用for
循环添加下一位数即可。
那么,你可能会有疑问:如果我 num = 1 呢?range
里面岂不是range(2, 1)
了,而且数列初始值就已经有2个数字了,他怎么可能会给我[1]
呢?
这就要提到Python里面的一些独特的小东西了:
range(a, b)
:用于生成一个从a开始到b结束(不包括b)的整数序列。步长默认为1,即从a开始,每次加1,直到b-1,最后返回一个从a开始到b结束(不包括b)的整数序列。参数a为起始值,默认为0;b为结束值,不包含在内。
1 | # 生成从0到9的整数序列 |
list[:num]
:这个是Python里面的切片操作,list
是一个列表,list[:num]
表示从列表的第一个元素开始,到第num
个元素结束,不包括第num
个元素。那么有意思的来了,如果我们把
num
的值设为1,即range(2, 1)
,会发生什么呢?
- 会生成一个从 2 开始,到 1 结束(不包括 1)的整数序列。但是,由于 2 大于 1,因此这个序列是空的。空序列的长度为 0,因此for
循环体不会执行任何代码,也就是fib_list
仍然是[1,1]
。
- 那我们为什么没有返回一个
[1,1]
呢?
- 因为我们在最后使用了fib_list[:num]
,它会返回一个从列表的第一个元素开始,到第num
个元素结束,不包括第num
个元素。所以,当num
为1时,它只会返回该数列的第0位,即[1]
。
4. 生成器
1 | def fibonacci(n): |
这个方法就更“Python”了:我们使用了生成器yield
。
yield
是什么?
- yield
是一个类似return
的关键字,只是这个函数返回的是一个生成器。生成器是一个特殊的迭代器,它的值是在运行时生成的。生成器的好处是它不会一次性把所有的值都生成出来,而是在需要的时候才生成,可以节省内存。
使用yield
,每次迭代都让a
和b
相加,然后把a
的值yield
出来,然后再把a
和b
的值交换,再相加,再yield
出来……直到range(n)
结束。
同样值得一提的是,如果我们在这个方法里让 n = 1
,我们就只会yield
一个a = 1
,最后list(1)
,同样可以只得到一个[1]
。十分的巧妙,十分的Python。
如有错误,请及时指出~评论发邮件均可,欧内盖!