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

#INT104 #Python

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

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

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

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

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

1. 递归

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. 循环

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

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为结束值，不包含在内。

# 生成从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. 生成器

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，每次迭代都让a和b相加，然后把a的值yield出来，然后再把a和b的值交换，再相加，再yield出来……直到range(n)结束。

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

---

如有错误，请及时指出～评论发邮件均可，欧内盖！