如何写斐波纳契数列？

问题描述 投票：132回答：43

我最初错误地编写了程序。我没有在一个范围（即startNumber 1，endNumber 20应该=只有1和20之间的数字）之间返回Fibonacci数，而是为程序编写了显示范围之间的所有Fibonacci数（即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))

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

我是一名学习程序员，而且我遇到了一些混乱。我被要求编写一个程序，用于通过用户输入的起始编号和结束编号来计算和显示斐波纳契序列（即startNumber = 20 endNumber = 100，它将仅显示该范围之间的数字）。诀窍是包含它（我不知道如何在Python中使用它？ - 我假设这意味着使用包含范围？）。

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

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

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

python fibonacci sequences
43个回答
243
投票

关于wikipedia和wolfram上的Fibonacci序列有很多信息。比你可能需要的要多得多。无论如何，学习如何使用这些资源来找到（如果可能的话）你需要的东西是一件好事。

将Fib序列公式写为无穷大

在数学中，它以递归形式给出：

在编程中，无限存在。您可以使用递归表单直接在您的语言中翻译数学表单，例如在Python中它变为：

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

用你最喜欢的语言尝试它，看看这个形式需要很多时间，因为n越来越大。实际上，这是O（2n）的时间。

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

Fibonacci Equation

在Python中，这个非常容易实现并且非常非常快速地计算：

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

另一种方法是遵循定义（来自wikipedia）：

序列的第一个数字是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。

一旦你知道如何生成Fibonacci数字，你只需要遍历数字并检查它们是否验证了给定的条件。

假设你现在写了一个返回斐波纳契数列第n项的f（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中我会使用迭代器形式并去：

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

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

2
投票
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)
2
投票

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

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
2
投票

另一种方式：

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'次。 a [-2：]将获得数组的最后两个元素。 a.append（x + y）将添加最后两个元素并将附加到数组

2
投票

好吧..在厌倦了所有冗长的答案后，现在找到以下排序和甜蜜，非常直接的方式在python中实现斐波那契。您可以通过获取参数或获取用户输入来以您想要的方式增强它...或者从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

这种方法也表现良好。在下面找到运行分析

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

斐波那契序列是：1, 1, 2, 3, 5, 8, ...。

那就是f(1) = 1，f(2) = 1，f(3) = 2，...，f(n) = f(n-1) + f(n-2)。

我最喜欢的实现（最简单但与其他实现相比实现了轻量级）是这样的：

def fibonacci(n):
    a, b = 0, 1
    for _ in range(1, n):
        a, b = b, a + b
    return b

测试

>>> [fibonacci(i) for i in range(1, 10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34]

timing

>>> %%time
>>> fibonacci(100**3)
CPU times: user 9.65 s, sys: 9.44 ms, total: 9.66 s
Wall time: 9.66 s

编辑：an example visualization用于此实现。

2
投票

这是对亨利亨利答案的改进：

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 ....

2
投票

使用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=b-a
    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=b-a
        l.append(b)
    return l

结果

>>> fib(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
2
投票
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, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853]

运行时间：0.04298138618469238

2
投票

有一种非常简单的方法可以实现！

您可以使用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]
1
投票

基本上从Ruby翻译：

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

...

56
投票

Efficient Pythonic generator of the Fibonacci sequence

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

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 zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

打印：

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

（出于归因目的，我最近在模块的Python文档中注意到similar implementation，甚至使用变量a和b，我现在回想起在写这个答案之前已经看过。但我认为这个答案证明了该语言的更好用法。）

Recursively defined implementation

Online Encyclopedia of Integer Sequences递归定义Fibonacci序列为

F（n）= F（n-1）+ F（n-2），F（0）= 0且F（1）= 1

在Python中以递归方式简洁地定义它可以如下完成：

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

但是，对于远大于30的数字，数学定义的这种精确表示非常低效，因为计算的每个数字也必须计算低于它的每个数字。您可以通过使用以下内容来演示它有多慢：

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

Memoized recursion for efficiency

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

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

您会发现记忆版本更快，并且在您甚至可以想到喝咖啡之前会快速超过最大递归深度。通过这样做，您可以看到它在视觉上的速度有多快：

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

（看起来我们可以只执行下面的操作，但它实际上不会让我们利用缓存，因为它在调用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

递归定义的生成器：

在我学习Haskell时，我在Haskell中遇到了这个实现：

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

我认为我现在最接近Python的是：

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

这证明了这一点：

[f for _, f in zip(range(999), fib())]

但它只能达到递归限制。通常，1000，而Haskell版本可以达到100万，尽管它使用笔记本电脑的所有8 GB内存来执行此操作：

> length $ take 100000000 fib 
100000000
1
投票
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
1
投票

递归增加了时间。要消除循环，首先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)

ref：Fibonacci Numbers in Python

1
投票

对于Fibonacci系列，这是python中最简单的一个，但是通过append（）在输出数组中调整[0]，得到结果列表第二个变量，即result.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]
1
投票

使用append函数生成前100个元素。

def generate():
    series = [0, 1]
    for i in range(0, 100):
        series.append(series[i] + series[i+1])

    return series


print(generate())
0
投票

在我学习Python时使用的教程15分钟后，它要求读者编写一个程序，该程序将根据3个输入数字（第一个Fibonacci数，第二个数和停止序列的数字）计算Fibonacci序列。该教程仅涵盖了变量，if / thens和循环到那一点。还没有功能。我想出了以下代码：

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

正如您所看到的，它效率非常低，但它确实有效。

0
投票

刚刚经过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)
0
投票
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
0
投票

也许这会有所帮助

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

试试这个：

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

基于经典的斐波那契序列，仅仅是为了单行

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

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])
24
投票

为什么不简单地执行以下操作？

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

这个怎么样？我想它并不像其他建议那样花哨，因为它需要先前结果的初始规范才能产生预期的输出，但我觉得这是一个非常易读的选项，即它所做的就是提供结果和之前的结果递归。

#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
20
投票

Fibonacci序列背后的想法显示在以下Python代码中：

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

这意味着fib是一个可以做三件事之一的函数。它将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

我们可以用下面的算法以相同的方式计算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（3），而fib（2）是通过知道fib（1）和fib（0）的定义来计算的。像fibonacci函数一样调用函数会被称为递归，它是编程中的一个重要主题。

这听起来像是家庭作业，所以我不打算为你做开始/结束部分。 Python虽然是一种非常富有表现力的语言，所以如果你理解数学，这应该是有意义的，并且希望教你递归。祝好运！

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

12
投票

时间复杂度：

通过消除Fibonacci系列递归树中的重复，缓存功能减少了计算Fibonacci级数从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()
8
投票

使用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个Fibonacci数。

同样，这使用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]
6
投票

Canonical Python代码打印Fibonacci序列：

a,b=1,1
while True:
  print a,
  a,b=b,a+b       # Could also use b=a+b;a=b-a

对于问题“打印长度大于1000位的第一个Fibonacci数”：

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
3
投票

使用递归：

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)
3
投票

我们知道

enter image description here

并且该矩阵的n次幂给了我们：

enter image description here

因此，我们可以实现一个简单地计算该矩阵对第n-1次幂的功率的函数。

因为我们都知道a ^ n等于的功率

enter image description here

所以最后斐波纳契函数将是O（n）......如果不是因为我们也知道x^n * x^n = x^2n和x^n的评估可以用复杂度O完成的事实，那么没有什么真正不同于更简单的实现（记录n）

这是我使用swift编程语言的fibonacci实现：

struct Mat {
    var m00: Int
    var m01: Int
    var m10: Int
    var m11: Int
}

func pow(m: Mat, n: Int) -> Mat {
    guard n > 1 else { return m }
    let temp = pow(m: m, n: n/2)

    var result = matMultiply(a: temp, b: temp)
    if n%2 != 0 {
        result = matMultiply(a: result, b: Mat(m00: 1, m01: 1, m10: 1, m11: 0))
    }
    return result
}

func matMultiply(a: Mat, b: Mat) -> Mat {
    let m00 = a.m00 * b.m00 + a.m01 * b.m10
    let m01 = a.m00 * b.m01 + a.m01 * b.m11
    let m10 = a.m10 * b.m00 + a.m11 * b.m10
    let m11 = a.m10 * b.m01 + a.m11 * b.m11

    return Mat(m00: m00, m01: m01, m10: m10, m11: m11)
}

func fibonacciFast(n: Int) -> Int {

    guard n > 0 else { return 0 }
    let m = Mat(m00: 1, m01: 1, m10: 1, m11: 0)

    return pow(m: m, n: n-1).m00
}

这具有复杂度O（log n）。我们用指数n-1计算Q的幂，然后我们得到元素m00，它是Fn + 1，在幂指数n-1处恰好是我们想要的第n个斐波纳契数。

一旦你有了快速的斐波纳契函数，你就可以从起始编号和结束编号迭代，得到你感兴趣的斐波纳契数列的部分。

let sequence = (start...end).map(fibonacciFast)

当然首先要对开始和结束进行一些检查，以确保它们能够形成有效范围。

我知道问题是8岁，但无论如何我都很乐意回答。 :)

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.