python 斐波拉契递归 尾递归 备忘录 动态规划 迭代

1 递归

#coding=utf-8 '''@author: 182 ''' from time import time def fab(n):if n==0:return 0if n==1:return 1if (n!=0 and n!=1):return fab(n-1)+fab(n-2)def main():start = time()print fab(100) stop = time()print(str(stop-start) + "秒")if __name__ == '__main__':main()

2 尾递归

#coding=utf-8'''@author: 182 '''from time import timedef weidigui(n,w1,w2):if n<2:return w1else:return weidigui(n-1,w2,w1+w2)def main(): start = time()print weidigui(99,1,1) stop = time()print(str(stop-start) + "秒") if __name__ == '__main__':main()

3 备忘录

#coding=utf-8'''@author: 182 '''import timelist=[] for i in range(0,1000):list.append(0)def beiwl(n):if list[n]>0:return list[n]if n==0:list[0]=0return list[0] if n==1:list[1]=1return list[1]if n>1:list[n]=(beiwl(n-1)+beiwl(n-2) ) return list[n] def main():start = time.time()print beiwl(99) end = time.time()elapsed = end - startprint "运行时间 ", elapsed, "秒"if __name__ == '__main__':main()

4  迭代

#coding=utf-8 '''@author: 182 ''' from time import time def diedai(n):if n==0:return 0else:f1=0f2=1f3=0for i in range(1,n-1):f3=f1+f2f1=f2f2=f3return f2 def main():start = time()print diedai(100) stop = time()print(str(stop-start) + "秒")if __name__ == '__main__':main()

5 动态规划

#coding=utf-8'''@author: 182 ''' from time import time def fabdp(n):list=[]list.append(0) list.append(1)for i in range(2,n):list.append(list[i-1]+list[i-2])return list[99] def main():start = time()print fabdp(100) stop = time()print(str(stop-start) + "秒")if __name__ == '__main__':main()

总结

以上是生活随笔为你收集整理的python 斐波拉契递归 尾递归 备忘录 动态规划 迭代的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。