代码拉取完成,页面将自动刷新
同步操作将从 陌溪/LearningNotes 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
0 1 1 2 3 5 8 13
n = 0, num = 0
n = 1, num = 1
n = 2, num = 1
.....
当 n = k(n>1),f(k) = f(k-1) + f(k-2)
当 n = 1, f(1) = 1
当 n = 0, f(0) = 0
# 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0) n<=39
class Solution:
def Fibonacci(self, n):
if n == 0:
return 0;
if n == 1:
return 1;
if n > 0:
return self.Fibonacci(n - 1) + self.Fibonacci(n -2);
else:
return None
if __name__ == '__main__':
print(Solution().Fibonacci(10))
但是这样存在问题,随着n提升,时间复杂度不断增加
我们发现对于某个值,我们重复计算了很多遍
我们继续查看刚刚的规律
当 n = 2的时候, h = f(1) + f(0) = 1 + 0 = 1
当 n = 3的时候, h = f(2) + f(1) = 1 + 1 = 2
当 n = 4的时候, h = f(3) + f(2) = 3 + 1 = 4
我们可以从n = 2,一直循环,直到我们计算出我们输入的值为n的时候
我们只需要从最小的开始计算,每次保留中间结果,最后得出我们的第n个的结果。
# 大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0) n<=39
class Solution:
# 非递归实现
# 当 n = 2的时候, h = f(1) + f(0) = 1 + 0 = 1
# 当 n = 3的时候, h = f(2) + f(1) = 1 + 1 = 2
# 当 n = 4的时候, h = f(3) + f(2) = 3 + 1 = 4
def Fibonacci2(self, n):
if n == 0:
return 0;
if n == 1:
return 1;
ret = 0
a = 1
b = 0
for i in range(0, n-1):
ret = a + b
b = a
a = ret
return ret
if __name__ == '__main__':
print(Solution().Fibonacci2(10))
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。