求解一道Python编程题

Question

斐波那契数列计算
形如1，1，2，3，5，8......的数列，被称之为斐波那契数列。这个数列的特点是从第三个数字开始，每个数字都等于前两个数字之和。

请用程序实现
用函数实现，计算斐波那契数列某项的值，并将计算结果返回。

函数定义
def fbi (num):
pass
参数说明
num是一个整数，表示斐波那契数列的项数。

返回值说明
函数返回一个整数，该整数为斐波那契数列第 num 项的值。

示例 1
参数
4
返回
3
示例 2
参数
6
返回
8
任务与要求
选做
10 分

Answer 1

斐波那契数列自第三个数开始，每个数均为之前两个数的和。

至少有两种方法来实现它。

最常见的利用迭代的方法，其核心思路是

fib(n) = fib(n-1) + fib(n-2)

而在n<2时直接，没有n-2，因此直接返回1:

def fib(num): return 1 if n<2 else fib(num-1) + fib(num-2)

这是一种很简单的实现。在阶梯数不大时，它很好用。当阶梯数很大时，因为二次手迭代，会比较慢。因此，可以在计算中保存中间值(1至n-1的阶梯数)来减少计算量：

这种方式在计算阶梯数10000时就可以保持不错的性能。如果需要多次计算该数列,则可以利用对象来保持这个中间值列表，下列代码中,Fibonaci实例只计算未曾计算的阶梯数，在重复调用时它更具优势：

class Fibonaci(object):

....history=[1, 1]

....def cacl(self, num):

........while len(self.history) <= num:

............self.history.append(self.history[-1] + self.history[-2])

........return self.history[num]

if __name__ == '__main__':

....fib = Fibonaci()

....print(fib.calc(100))

....print(fib.calc(32))

....print(fib.calc(10000))

Answer 2

你好！

注：题目没有提到过输入参数小于1的情况，所以并未做处理。

希望对你有帮助！

Answer 3

def fbi(num):
if num<2 :
return 1
else:
return fbi(num-1)+fbi(num-2)