banner
NEWS LETTER

Python解决斐波那契数列的几个方法

Scroll down

#INT104 #Python

斐波那契数列是一个非常经典的数列,它的定义是:第0项为0,第1项为1,从第2项开始,每一项都等于前两项之和。

但是我们正常来说是不用第0项的,是从第一项开始。

所以他的形式是:[1, 1, 2, 3, 5, 8, 13, 21]。

在 INT104 的 Tutorial 3 上,我发现老师的解法,我的解法,copilot的解法,朋友的解法全都不尽相同。这就很有意思了,所以就想写一篇博客来汇总一下。

在此总结4种使用Python的解法:

1. 递归

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)


def generateFibonacciList(n):
numList = []
for i in range(1, n + 1):
numList.append(fibonacci(i))
return numList


print(generateFibonacciList(8))
# [1, 1, 2, 3, 5, 8, 13, 21]

首先,我们定义了一个递归函数 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. 循环

python
1
2
3
4
5
6
7
8
9
10
11
12
def fibonacci(n):
numList = []
while len(numList) < n:
if len(numList) < 2:
numList.append(1)
else:
numList.append(numList[-1] + numList[-2]) # -1表示最后一个元素,-2表示倒数第二个元素
return numList


print(fibonacci(8))
# [1, 1, 2, 3, 5, 8, 13, 21]

这个方法理论上应该是最容易想的,相对来说也是最好写的方法 —— 使用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

python
1
2
3
4
5
6
7
8
9
10
11
12
def fibonacci(num):
fib_list = [1, 1] # initialize the list with the first two fibonacci numbers
for i in range(2, num):
fib_list.append(fib_list[i - 1] + fib_list[i - 2]) # calculate the next fibonacci number
return fib_list[:num] # return the first 'num' fibonacci numbers


print(fibonacci(8))
# [1, 1, 2, 3, 5, 8, 13, 21]

print(fibonacci(1))
# [1]

这个是我本人最喜欢的一个解法:巧妙的使用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为结束值,不包含在内。
python
1
2
3
4
5
6
7
8
# 生成从0到9的整数序列
range(10)

# 生成从1到5的整数序列
range(1, 5)

# 生成从2到10,步长为2的整数序列
range(2, 10, 2)
  • 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. 生成器

python
1
2
3
4
5
6
7
8
9
def fibonacci(n):
a, b = 1, 1
for _ in range(n):
yield a
a, b = b, a + b


print(list(fibonacci(8)))
# [1, 1, 2, 3, 5, 8, 13, 21]

这个方法就更“Python”了:我们使用了生成器yield

  • yield是什么?

- yield是一个类似return的关键字,只是这个函数返回的是一个生成器。生成器是一个特殊的迭代器,它的值是在运行时生成的。生成器的好处是它不会一次性把所有的值都生成出来,而是在需要的时候才生成,可以节省内存。

使用yield,每次迭代都让ab相加,然后把a的值yield出来,然后再把ab的值交换,再相加,再yield出来……直到range(n)结束。

同样值得一提的是,如果我们在这个方法里让 n = 1,我们就只会yield一个a = 1,最后list(1),同样可以只得到一个[1]。十分的巧妙,十分的Python。


如有错误,请及时指出~评论发邮件均可,欧内盖!

Other Articles
Nickname
Email
Website
0/500
0 comments
Article table of contents TOP
  1. 1. 1. 递归
  2. 2. 2. 循环
  3. 3. 3. for + range
  4. 4. 4. 生成器
Please enter keywords to search