4斐波那契数列斐波那契数列python实现实现
第第4篇篇 斐波那契数列斐波那契数列python实现实现
知识点:递归和循环
要求要求
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项。
n<=39
斐波那契数列的定义: F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
代码代码
版本1:
class Solution:
def Fibonacci(self, n):
# 定义: F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
if n == 0:
return 0
elif n == 1:
return 1
else:
return self.Fibonacci(n-1) + self.Fibonacci(n-2)
问题:效率太低,满足不了oj的效率要求。且有很多重复计算!
改进:可以从下往上计算,从0,1一直叠加到n,就像人工做计算那样,从而避免重复
class Solution:
def Fibonacci(self, n):
# 定义: F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
if n == 0:
return 0
elif n == 1:
return 1
else:
fib0 = 0
fib1 = 1
for _ in range(2, n+1):
fib0, fib1 = fib1, fib0 + fib1
return fib1
跳台阶跳台阶
要求要求
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路思路
青蛙某次可以是在之前跳了(n-1)级的基础上,再跳了1级到达第n级,也可以是在之前跳了(n-2)级的基础上,再跳了2级到达第
n级……依次类推,发现其实是一个斐波那契数列。
代码代码
class Solution:
def jumpFloor(self, number):
# 思路:斐波那契数列问题,从后往前看,f(n) = f(n-1) + f(n-2)
# f(1) = 1, f(2) = 2
if number <= 2:
评论5