斐波纳契(Fibonacci)數列是一个非常简单的递归数列,除第一个和第二个数外,任意一个数都可由前两个数相加得到。
当n = 0, fib(n) = 1;当n = 1, fib(n) = 1;当n > 1, fib(n) = fib(n-1) + fib(n-2)
解法1:
直接根据数列描述,由递归的方式解决。
1 def fib(a):
2 assert a >=0
3 if a in [0, 1]:
4 return 1
5 else:
6 return fab(a-1) + fab(a-2)
运行即可正确得出结果。但是细心的你会发现,如果求一个稍微大一点的数字的fib, 则系统会卡死。比如fib(100)。这是因为使用递归的方式计算时,会出现多次重复计算的过程,而这些重复计算消耗了大量的计算资源。
于是最直接能想到的解决方法就是将之前的计算结果缓存起来,于是得到如下解决方案——
解法2:
1 dcache = {0:1, 1:1}
2 def fib2(a):
3 global dcache
4 if a in dcache.keys():
5 return dcache[a]
6 else:
7 dcache[a] = fab3(a-1) + fab3(a-2)
8 return dcache[a]
这样做是一个典型的以空间换取时间的做法,但是如果数字再大一点,使得dcache中存储的内容超过系统内存时,又会出现卡死的现象了。那么,还有没有更优化一点的方法呢?
解法3:
1 def fib3(a):
2 fa, fb = 0, 1
3 for i in xrange(a):
4 fa, fb = fb, fa + fb
5 return fb
显然,第三种解法以递归的方式计算,既避免了迭代所导致的重复计算,又取消了全局缓存,使得计算效率更高。
普及:
一台4G内存的电脑,stack size设置为8192 (ulimit -a), 则最大可以跑512个线程(4G/8M)
相关推荐
java斐波那契数列编程,是运用数组来创建的文档,输出一系列数.
编写一个Java程序,用于输出Fibonacci数列的前20项。
【C++】斐波那契数列应用的一个实例。这是关于斐波那契数列的一个例子,用C++语言实现
使用C++语言编程解决斐波那契数列问题,一共使用了三种方法:递归函数法、动态数组法、非递归函数法
斐波那契数列,又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)在现代物理、准晶体结构、...
用java语言实现斐波那契数列,编程平台是eclipse
用递推算法 迭代算法 公式法计算求第N个Fibonacci数,计算机能算出最大Fibonacci时N的值,计算1分钟内能计算几个Fibonacci,用公式法计算Fibonacci,当出现错误时,N为多少。
斐波那契数列是一个常见的数学序列,在计算机科学和编程中经常用到。本教程将向您展示如何使用Java编写代码来计算斐波那契数列的第 n 个数字。我们将涵盖循环和递归两种不同的方法,以帮助您理解常用的编程知识点,...
线程池编程的示例。 // 线程执行长时间的 Fibonacci(N) 计算提供了一个接口。 // N 是为 Fibonacci 构造函数提供的,此外还提供了 // 操作完成时对象发出的事件信号。 // 然后,可以使用 FibOfN 属性来检索结果。
raptor编程软件数组实现斐波那契数列。
少儿编程之斐波那契数列
斐波那契数列python求解代码
斐波那契数列c 斐波那契数列是一个充满魅力的数学序列,...通过本文的介绍,我们了解了斐波那契数列的C++实现方法以及其在不同领域的应用。希望这些内容能够帮助你更深入地理解斐波那契数列,并在实际编程中灵活运用。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...return fibonacci(num - 1) + fibona
Python编程题--斐波那契数列
斐波那契(Fibonacci)数列的定义是这样的: F(1)=1 F(2)=1 F(N)=F(N-1)+F(N-2) (N>=3) 请计算第N项斐波那契的值. 输入描述 输入数据只包含一个正整数N(1); 输出描述 请根据要求计算输出F(N)的结果,为方便计算,...
资源类型:编程题 难度:简单 覆盖范围:Java基础、数组和循环 使用建议: 1.掌握Java基础语法,包括变量定义、数据类型、运算符等 2.熟悉数组的使用和循环的结构 3.练习编写递归函数 题目描述: 编写一个函数,根据...
用柔性数组方式实现斐波那契数列,里面运用c语言进行编程,一个c文件,大家相互学习
斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368…….. 这个数列从第3项开始,每一项都等于前两项之和。 F0=...
这份资源提供了使用Python语言和算法设计思想解决斐波那契数列问题的实验指南。斐波那契数列在计算机科学中是一个经典的数列问题,具有很高的研究和应用价值。 在这份资源中,您将学习到斐波那契数列的定义和性质,...