最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

python代码实现递归和循环_斐波那契数列

XAMPP案例 admin 55浏览 0评论

【斐波那契数列】


题目描述

现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,n<=39)。


思路

从0开始,第0项为0,斐波那契数列可以写为[0、1、1、2、3、5、8、13、21、34、...],其中n=0、1的时候分别输出0、1,从n=2开始,数列该项的值等于前两项之和,即F(n)=F(n-1)+F(n-2)。以下使用两种方法实现本题:1. 采用递归的方法得到第n项;2. 非递归的方法得到第n项。


1. 递归的方法
# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        # write code here        if n ==0:            return 0        elif n ==1:            return 1        else:            return self.Fibonacci(n-2) + self.Fibonacci(n-1)

测试:

import time   #导入时间模块start=time.time()  #记录开始时间s=Solution()fib_39=s.Fibonacci(39)end=time.time()   #记录结束时间print('斐波那契数列的第39项为',fib_39)print('本次处理共耗时%.2f秒'%(end-start))# result:斐波那契数列的第39项为63245986本次处理共耗时162.03秒

采用递归的方法,递归深度过大,时间复杂度会很高为(O(2^n))。当n=39时,在jupyter中花费2~3分钟运行得到F(39),而在牛客网在线测试时程序未能在规定时间内运行结束而报错。


2. 非递归的方法
# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        # write code here            a=[0,1]            for i in range(2,n+1):                a.append(a[i-2]+a[i-1])            return a[n]

测试:

s=Solution()F=[s.Fibonacci(i) for i in range(39)]print(F)# result:[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]

非递归的方法的时间复杂度为O(n),以上可以快速得到斐波那契数列的前39项。

【斐波那契数列】


题目描述

现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0,n<=39)。


思路

从0开始,第0项为0,斐波那契数列可以写为[0、1、1、2、3、5、8、13、21、34、...],其中n=0、1的时候分别输出0、1,从n=2开始,数列该项的值等于前两项之和,即F(n)=F(n-1)+F(n-2)。以下使用两种方法实现本题:1. 采用递归的方法得到第n项;2. 非递归的方法得到第n项。


1. 递归的方法
# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        # write code here        if n ==0:            return 0        elif n ==1:            return 1        else:            return self.Fibonacci(n-2) + self.Fibonacci(n-1)

测试:

import time   #导入时间模块start=time.time()  #记录开始时间s=Solution()fib_39=s.Fibonacci(39)end=time.time()   #记录结束时间print('斐波那契数列的第39项为',fib_39)print('本次处理共耗时%.2f秒'%(end-start))# result:斐波那契数列的第39项为63245986本次处理共耗时162.03秒

采用递归的方法,递归深度过大,时间复杂度会很高为(O(2^n))。当n=39时,在jupyter中花费2~3分钟运行得到F(39),而在牛客网在线测试时程序未能在规定时间内运行结束而报错。


2. 非递归的方法
# -*- coding:utf-8 -*-class Solution:    def Fibonacci(self, n):        # write code here            a=[0,1]            for i in range(2,n+1):                a.append(a[i-2]+a[i-1])            return a[n]

测试:

s=Solution()F=[s.Fibonacci(i) for i in range(39)]print(F)# result:[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]

非递归的方法的时间复杂度为O(n),以上可以快速得到斐波那契数列的前39项。

转载请注明:XAMPP中文组官网 » python代码实现递归和循环_斐波那契数列