如何在Python中编写斐波那契数列

我原本错误地编写了这个程序。 而不是返回一个范围之间的斐波纳契数字（即startNumber 1，endNumber 20 should =只有那些数字在1和20之间），我已经写了程序显示范围之间的所有斐波纳契数字（即。startNumber 1，endNumber 20显示=前20个斐波纳契数字）。 我以为我有一个确定的代码。 我也不明白为什么会这样。

startNumber = int(raw_input("Enter the start number here ")) endNumber = int(raw_input("Enter the end number here ")) def fib(n): if n < 2: return n return fib(n-2) + fib(n-1) print map(fib, range(startNumber, endNumber)) 

有人在我的第二部分（这是closures作为重复 – https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ）指出，我需要通过使用while循环的生成器来传递startNumber和endNumber。 有人可以指出我如何做到这一点？ 任何帮助是受欢迎的。

---

我是一个学习程序员，我遇到了一些混乱。 我被要求写一个程序，计算并显示斐波那契数列由用户input的起始号码和结束号码（即startNumber = 20 endNumber = 100，它将只显示该范围之间的数字）。 诀窍是使用它包含（我不知道如何在Python中做 – 我假设这意味着使用包容性范围？）。

我到目前为止没有实际的编码，而是：

• 将Fib序列公式写成无穷大
• 仅从Fib序列显示startNumber到endNumber。

我不知道从哪里开始，我正在问如何写这个想法或见解。 我也试图写Fib序列论坛，但我也迷失了。

Answer 1

斐波那契数列有很多关于wikipedia和wolfram的信息 。 比你可能需要的要多得多。 无论如何，学习如何使用这些资源（如果可能，尽快）find你需要的东西是一件好事。

将Fib序列公式写成无穷大

在math中，它是以recursion的forms给出的：

在编程中， 无限不存在。 您可以使用recursionforms直接用您的语言翻译mathforms，例如在Python中，它会变成：

 def F(n): if n == 0: return 0 elif n == 1: return 1 else: return F(n-1)+F(n-2) 

尝试用你最喜欢的语言，看看这个forms需要很多时间，因为n变大了。 事实上，这是O（2 ⁿ ）。

在我链接到你的网站上，将会看到这个（在wolfram上 ）：

这个在Python中很容易实现，计算速度非常快，

 from math import sqrt def F(n): return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5)) 

另一种方法是遵循定义（来自维基百科 ）：

序列的第一个数字是0，第二个数字是1，每个后续数字等于序列本身的前两个数字的总和，产生序列0,1,1,2,3,5,8等等

如果你的语言支持迭代器，你可以这样做：

 def F(): a,b = 0,1 while True: yield a a, b = b, a + b 

仅从Fib序列显示startNumber到endNumber。

一旦你知道如何生成斐波纳契数，你只需要循环数字，并检查他们是否validation给定的条件。

假设现在你写了af（n）返回斐波那契数列的第n项（就像sqrt（5）的那个）

在大多数语言中，您可以执行以下操作：

 def SubFib(startNumber, endNumber): n = 0 cur = f(n) while cur <= endNumber: if startNumber <= cur: print cur n += 1 cur = f(n) 

在Python中我会使用迭代器的forms，并去：

 def SubFib(startNumber, endNumber): for cur in F(): if cur > endNumber: return if cur >= startNumber: yield cur for i in SubFib(10, 200): print i 

我的提示是要学会阅读你所需要的东西。 欧拉项目（谷歌为它）将训练你这样做：P祝你好运，玩得开心！

Answer 2

Fibonacci序列的高效Pythonic生成器

我在试图获得这个序列的最短Pythonic代时发现了这个问题（后来认识到我在Python Enhancement Proposal中看到了类似的代码 ），而且我还没有注意到有人提出了我的具体解决scheme（尽pipe最佳答案接近，但还不够优雅），所以在这里，有了评论，描述了第一次迭代，因为我认为这可以帮助读者理解：

 def fib(): a, b = 0, 1 while True: # First iteration: yield a # yield 0 to start with and then a, b = b, a + b # a will now be 1, and b will also be 1, (0 + 1) 

和用法：

 for index, fibonacci_number in enumerate(fib()): print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number)) if index == 10: break 

打印：

  0: 0 1: 1 2: 1 3: 2 4: 3 5: 5 6: 8 7: 13 8: 21 9: 34 10: 55 

（出于归因的目的，我最近注意到在模块上的Python文档中有一个类似的实现 ，即使使用variablesa和b ，我现在回想在写这个答案之前已经看到了这个variables，但是我认为这个答案表明了更好地使用该语言。

recursion定义的实现

整数序列的在线百科全书将Fibonacci序列recursion地定义为

当F（0）= 0且F（1）= 1时，F（n）= F（n-1）+ F

在Python中recursion地简单地定义这个可以做如下：

 def rec_fib(n): '''inefficient recursive function as defined, returns Fibonacci number''' if n > 1: return rec_fib(n-1) + rec_fib(n-2) return n 

但是这个math定义的确切expression式对于远远超过30的数字是非常低效的，因为计算的每个数字也必须为其下面的每个数字计算。 您可以通过使用以下内容来演示其速度有多慢：

 for i in range(40): print i, rec_fib(i) 

记忆recursion提高效率

它可以被记忆以提高速度（这个例子利用了每次调用函数时默认的关键字参数是同一个对象的事实，但是正因为这个原因，通常你不会使用可变的默认参数）：

 def mem_fib(n, _cache={}): '''efficiently memoized recursive function, returns a Fibonacci number''' if n in _cache: return _cache[n] elif n > 1: return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2)) return n 

你会发现备忘录的版本要快得多，并且在你甚至想起床喝咖啡之前，会很快超过你的最大recursion深度。 你可以看到这样做的速度是多快：

 for i in range(40): print i, mem_fib(i) 

（看起来好像我们可以做下面的事情，但实际上并没有让我们利用caching，因为它在调用setdefault之前调用自己。）

 def mem_fib(n, _cache={}): '''don't do this''' if n > 1: return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2)) return n 

Answer 3

斐波那契数列背后的思想如下Python代码所示：

 def fib(n): if n == 1: return 1 elif n == 0: return 0 else: return fib(n-1) + fib(n-2) 

这意味着fib是一种可以做三件事情之一的function。 它将fib（1）== 1，fib（0）== 0和fib（n）定义为：

fib（n-1）+ fib（n-2）

其中n是任意整数。 这意味着fib（2）例如展开为以下算术：

 fib(2) = fib(1) + fib(0) fib(1) = 1 fib(0) = 0 # Therefore by substitution: fib(2) = 1 + 0 fib(2) = 1 

我们可以用下面的algorithm计算fib（3）：

 fib(3) = fib(2) + fib(1) fib(2) = fib(1) + fib(0) fib(2) = 1 fib(1) = 1 fib(0) = 0 # Therefore by substitution: fib(3) = 1 + 1 + 0 

这里要实现的重要一点是，如果不计算fib（2），通过了解fib（1）和fib（0）的定义，就可以计算出fib（3）。 有一个函数调用自己像斐波那契函数一样被称为recursion，这是编程中的一个重要话题。

这听起来像一个家庭作业，所以我不打算为你做开始/结束部分。 对于这个Python来说Python是一个非常有performance力的语言，所以如果你理解math，这应该是有意义的，并且希望能够教会你recursion。 祝你好运！

编辑：我的代码的一个潜在的批评是，它不使用超级方便的Python函数yield，这使得fib（n）函数更短。 我的例子是更通用一些，因为没有很多Python以外的语言实际上有收益率。

Answer 4

为什么不只是简单地做到以下几点？

 x = [1,1] for i in xrange(10): x.append(x[-1] + x[-2]) print ', '.join(str(y) for y in x) 

Answer 5

时间复杂度：

通过消除斐波那契数列的recursion树中的重复，高速caching特征减less了从O（2 ^ n）到O（n）计算斐波纳契数列的正常方法：

代码：

 import sys table = [0]*1000 def FastFib(n): if n<=1: return n else: if(table[n-1]==0): table[n-1] = FastFib(n-1) if(table[n-2]==0): table[n-2] = FastFib(n-2) table[n] = table[n-1] + table[n-2] return table[n] def main(): print('Enter a number : ') num = int(sys.stdin.readline()) print(FastFib(num)) if __name__=='__main__': main() 

Answer 6

Canonical Python代码打印Fibonacci序列：

 a,b=1,1 while(True): print a, a,b=b,a+b # Could also use b=a+b;a=ba 

对于“打印长度超过1000个数字的第一个斐波纳契数字”的问题：

 a,b=1,1 i=1 while(len(str(a))<=1000): i=i+1 a,b=b,a+b print i,len(str(a)),a 

Answer 7

这是非常有效的，使用O（log n）的基本算术运算。

 def fib(n): return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n) 

这个使用O（1）基本的算术运算，但是中间结果的大小很大，所以效率不高。

 def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) 

这个计算多项式环Z [X] /（X ^ 2 – X – 1）中的X ^ n使用指数乘以平方。 该计算的结果是多项式Fib（n）X + Fib（n-1），从中可以读取第n个斐波纳契数。

这又一次使用O（log n）算术运算，效率很高。

 def mul(a, b): return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1] def fib(n): x, r = (1, 0), (0, 1) while n: if n & 1: r = mul(r, x) x = mul(x, x) n >>= 1 return r[0] 

Answer 8

使用for循环并打印结果

 def fib(n:'upto n number')->int: if n==0: return 0 elif n==1: return 1 a=0 b=1 for i in range(0,n-1): b=a+b a=ba return b 

结果

 >>>fib(50) 12586269025 >>>> >>> fib(100) 354224848179261915075 >>> 

打印包含所有数字的list

 def fib(n:'upto n number')->int: l=[0,1] if n==0: return l[0] elif n==1: return l a=0 b=1 for i in range(0,n-1): b=a+b a=ba l.append(b) return l 

结果

 >>> fib(10) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

Answer 9

 def fib(): a,b = 1,1 num=eval(input("Please input what Fib number you want to be calculated: ")) num_int=int(num-2) for i in range (num_int): a,b=b,a+b print(b) 

Answer 10

这些都看起来比他们需要更复杂一点。 我的代码非常简单快捷：

 def fibonacci(x): List = [] f = 1 List.append(f) List.append(f) #because the fibonacci sequence has two 1's at first while f<=x: f = List[-1] + List[-2] #says that f = the sum of the last two f's in the series List.append(f) else: List.remove(List[-1]) #because the code lists the fibonacci number one past x. Not necessary, but defines the code better for i in range(0, len(List)): print List[i] #prints it in series form instead of list form. Also not necessary 

Answer 11

OK ..在厌倦了提到所有冗长的答案之后，现在find下面那种在python中实现Fibonacci的sorting方式。 您可以通过获取参数或获取用户input以您想要的方式进行增强…或者将限制从10000更改。

 def fibonacci(): start = 0 i = 1 lt = [] lt.append(start) while start < 10000: start += i lt.append(start) i = sum(lt[-2:]) lt.append(i) print "The Fibonaccii series: ", lt 

这种方法也performance良好。 find下面的运行分析

 In [10]: %timeit fibonacci 10000000 loops, best of 3: 26.3 ns per loop 

Answer 12

另一种方法：

 a,n=[0,1],10 map(lambda i: reduce(lambda x,y: a.append(x+y),a[-2:]),range(n-2)) 

将列表分配给'a'，将整数赋值给'n'Map和Reduce是Python中三个最强大的函数中的两个。 这里的map只用来迭代“n-2”次。 一个[-2：]将得到数组的最后两个元素。 a.append（x + y）将添加最后两个元素，并将追加到数组

Answer 13

从Ruby基本翻译：

 def fib(n): a = 0 b = 1 for i in range(1,n+1): c = a + b print c a = b b = c 

…

Answer 14

 def fib(lowerbound, upperbound): x = 0 y = 1 while x <= upperbound: if (x >= lowerbound): yield x x, y = y, x + y startNumber = 10 endNumber = 100 for fib_sequence in fib(startNumber, endNumber): print "And the next number is... %d!" % fib_sequence 

Answer 15

recursion增加了时间。 要消除循环，首先要import math 。 然后在函数中使用math.sqrt和黄金比例：

 #!/usr/bin/env python3 import math def fib(n): gr = (1 + math.sqrt(5)) / 2 fib_first = (gr**n - (1 - gr)**n) / math.sqrt(5) return int(round(fib_first)) fib_final = fib(100) print(fib_final) 

参考： 在Python中的斐波那契数字

Answer 16

这是马修亨利的答案的一个改进：

 def fib(n): a = 0 b = 1 for i in range(1,n+1): c = a + b print b a = b b = c 

代码应该打印b而不是打印c

输出：1,1,2,3,5 ….

Answer 17

有一个非常简单的方法来实现！

你可以通过使用http://www.learnpython.org/免费在线代码;

 # Set the variable brian on line 3! def fib(n): """This is documentation string for function. It'll be available by fib.__doc__() Return a list containing the Fibonacci series up to n.""" result = [] a = 0 b = 1 while a < n: result.append(a) # 0 1 1 2 3 5 8 (13) break tmp_var = b # 1 1 2 3 5 8 13 b = a + b # 1 2 3 5 8 13 21 a = tmp_var # 1 1 2 3 5 8 13 # print(a) return result print(fib(10)) # result should be this: [0, 1, 1, 2, 3, 5, 8] 

Answer 18

 import time start_time = time.time() #recursive solution def fib(x, y, upperLimit): return [x] + fib(y, (x+y), upperLimit) if x < upperLimit else [x] #To test : print(fib(0,1,40000000000000)) print("run time: " + str(time.time() - start_time)) 

结果

[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,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049。 ，12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6657470319842,10610209857723,17167680177565,277777890035288,44945570212853]，其中，

运行时间： 0.04298138618469238

Answer 19

这是在斐波那契数列python中最简单的一个，但通过append（）在输出数组中调整[0]以产生结果列表第二个variablesresult.append(second)

 def fibo(num): first = 0 second = 1 result = [0] print('Fibonacci series is') for i in range(0,num): third = first + second #print(second) result.append(second) first = second second = third print(result) return fibo(7) 

OUTPUT

 Fibonacci series is [0, 1, 1, 2, 3, 5, 8, 13] 

Answer 20

从阅读好的Python书开始。 其中一本书是“如何像电脑科学家一样思考”，特别是第五章。

Answer 21

去找出如何将recursion问题转换为迭代问题。 应该可以从那里计算。

这可能是他们试图让你学习的原则，特别是如果这是一个algorithm课程。

Answer 22

在学习Python时使用了15分钟的教程，它要求读者编写一个程序，根据3个input数字（第一个斐波那契数，第二个数以及停止序列的次数）来计算斐波那契数列。 该教程只覆盖variables，如果/ thens，并循环到这一点。 没有function。 我想出了以下代码：

 sum = 0 endingnumber = 1 print "\n.:Fibonacci sequence:.\n" firstnumber = input("Enter the first number: ") secondnumber = input("Enter the second number: ") endingnumber = input("Enter the number to stop at: ") if secondnumber < firstnumber: print "\nSecond number must be bigger than the first number!!!\n" else: while sum <= endingnumber: print firstnumber if secondnumber > endingnumber: break else: print secondnumber sum = firstnumber + secondnumber firstnumber = sum secondnumber = secondnumber + sum 

正如你所看到的那样，效率确实很低，但它确实有效。

Answer 23

使用recursion：

 def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) x=input('which fibonnaci do you want?') print fib(x) 

Answer 24

只要通过http://projecteuler.net/problem=2这是我的承担;

 # Even Fibonacci numbers # Problem 2 def get_fibonacci(size): numbers = [1,2] while size > len(numbers): next_fibonacci = numbers[-1]+numbers[-2] numbers.append(next_fibonacci) print numbers get_fibonacci(20) 

Answer 25

 def fib(x, y, n): if n < 1: return x, y, n else: return fib(y, x + y, n - 1) print fib(0, 1, 4) (3, 5, 0) # def fib(x, y, n): if n > 1: for item in fib(y, x + y, n - 1): yield item yield x, y, n f = fib(0, 1, 12) f.next() (89, 144, 1) f.next()[0] 55 

Answer 26

这是我在Khan Academy的“Python程序devise”上看到的一个练习任务： https : //www.khanacademy.org/science/computer-science-subject/computer-science/v/exercise—write-a-fibonacci-function

他可能不是第一个把这个工作分配的人。 但你自己搞清楚真是太棒了。 我从中学到了很多，实际上是一场爆炸。

我build议你在尝试复制其他人的作业代码之前，自己弄明白。

在上面的video中，教练萨尔展示了斐波纳契数字背后的全部理论，考虑到这一点，你应该能够弄明白。

我花了大约10分钟，这是我做的代码（我从3天前开始学习Python，这是我学习的第一个编程语言）。 如果不是以前的教程的video，我将无法编写代码： https ： //www.khanacademy.org/science/computer-science-subject/computer-science/v/comparing-iterative-和recursion – 阶乘函数 ，给出了一个萨尔做recursion阶乘方程的例子，并给出了解决这个问题的思路。

这是我的代码：

 def fibonacci(num): if num <= 1: #base case return num else: return fibonacci(num-1) + fibonacci(num-2) 

你可以看到，如果数字是1或0，那么你只是返回数字。

我发现这比干净的说如果数字是1返回1，如果数字是0返回0。

Answer 27

也许这会有所帮助

 def fibo(n): result = [] a, b = 0, 1 while b < n: result.append(b) a, b = b, b + a return result 

Answer 28

尝试这个：

 def nth_fib(n): if n == 0: return 1 elif n == 1: return 0 else: return nth_fib(n - 1) + nth_fib(n - 2) 

Answer 29

基于经典的斐波纳契序列，只是为了单线

如果你只是需要指数的数量，你可以使用减less（即使减less它不是最适合这个，它可以是一个很好的练习）

 def fibonacci(index): return reduce(lambda r,v: r.append(r[-1]+r[-2]) or (r.pop(0) and 0) or r , xrange(index), [0, 1])[1] 

并得到完整的数组只是删除or（r.pop（0）和0）

 reduce(lambda r,v: r.append(r[-1]+r[-2]) or r , xrange(last_index), [0, 1]) 

Answer 30

这个怎么样？ 我想这不像其他build议那样花哨，因为它要求对以前的结果进行初始规定以产生预期的输出，但是我觉得是一个非常可读的选项，即它只是将结果和以前的结果提供给recursion。

 #count the number of recursions num_rec = 0 def fibonacci(num, prev, num_rec, cycles): num_rec = num_rec + 1 if num == 0 and prev == 0: result = 0; num = 1; else: result = num + prev print(result) if num_rec == cycles: print("done") else: fibonacci(result, num, num_rec, cycles) #Run the fibonacci function 10 times fibonacci(0, 0, num_rec, 10) 

这是输出：

 0 1 1 2 3 5 8 13 21 34 done