迭代算法求解斐波那契数列

Question

我对斐波那契数列的迭代算法很感兴趣，因此在维基百科上找到了公式...看起来很简单，所以我用Python尝试了一下...编译没有问题，公式也看起来正确...不确定为什么输出结果错误...是我没有正确实现吗？

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

输出

0
None
1
1
1
1
1
1

- Ris

---

如果你对斐波那契数列的算法复杂度感兴趣，可以查看这篇帖子。 - RBT

Answer 1

问题在于你的 return y 在函数的循环内部。因此，在第一次迭代之后，它将停止并返回第一个值：1。除非 n 为 0，在这种情况下，该函数将被设置为返回 0 本身；如果 n 为 1，则 for 循环甚至不会迭代一次，并且没有执行 return（因此返回值为 None）。

要解决此问题，只需将 return y 移到循环外面即可。

替代实现方法

以下是我个人在 Python 中制作的解决方案，跟随 KebertX 的示例。当然，如果您要处理许多斐波那契数值，甚至可能希望结合这两个解决方案并为数字创建缓存。

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

- poke

---

@Adelin 这是什么语言？这是一个 Python 问题，而那不是 Python 代码。考虑创建一个新的问题，或者在 codereview.SE 上请求您代码的审查。话虽如此，当 limit=1 时，您的数组大小是错误的，这将导致索引异常。 - poke

在脚本的结尾返回a是计算f(n-1)而不是f(n)。你应该返回b以便返回f(n)。 - eton_ceb

@eton_ceb 这取决于你对Fibonacci数列的定义。我通常以0和1开始数列，而不是以1和1开始。 - poke

你可以忽略 i，只需写成 for _ in range(n)。 - Florimond

我会做两个更改：**(1)：我们可以用return b代替return a，这样我们可以少循环一次并得到答案。(2)**：使用for i in range(2, n+1):代替for i in range(0, n):，这样i将表示fib(b)的实际斐波那契计算。最后，缓存是不必要的，因为每轮我们都在做O(1)时间复杂度的操作。干杯！ - Ng Sek Long

Answer 2

您在循环内返回了一个值，因此该函数在y的值仅为1时就退出了。

如果我可以提供一些更短、更具Python风格的建议：

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

这将与您的算法完全相同，但它不是创建三个临时变量，而是将它们添加到一个列表中，并通过索引返回第n个斐波那契数。

- KebertX

---

这将需要更多的内存，因为它需要将它们全部保存在列表中（对于非常大的 n，您会注意到这一点）。此外，我认为这不是解决此问题的最佳 Pythonic 解决方案。我认为在简单的 for 循环中使用元组（解包）会更好（请参见我的答案编辑）。 - poke

我会更进一步地说，尽管这个解决方案是迭代的，但它与递归解决方案具有相同的缺点，即它不能在恒定的空间中运行。你只是用列表元素替换了堆栈帧。 - rbp

@KebertX，我知道这个帖子很旧了，但是为什么在for循环内部写a,b = b,a+b可以工作，而像这样写a=b和b=a+b就不行呢？我的意思是a,b = b,a+b 只是a=b和b=a+b的简写形式，对吗？ - Halcyon Abraham Ramirez

@HalcyonAbrahamRamirez：元组赋值和按顺序将每个右侧表达式分别分配给其相应的“变量”_不是_相同的：使用元组赋值时，最后一个求值在第一次赋值之前完成 - 考虑交换：“a，b = b，a” - greybeard

这是一个递归解决方案，原问题需要寻找迭代解决方案。 - Maksood

Answer 3

在 fib(0) 中，你返回 0 是因为：

if (n == 0) {
    return 0;
}

在 fib(1) 中，你返回 1 是因为：

y = 1
return y

在图2中，你返回1是因为：

y = 1
return y

...等等。只要return y在循环内，函数每次都在第一次迭代时结束。

这里有一个好的解决方案，是另一个用户想出来的： 如何在Python中编写斐波那契数列

- John Hornsby

---

（这些花括号是从哪里来的... from __future__ import braces? :P） - poke

Answer 4

我在另一个帖子上发现了这个，它比我尝试过的任何其他方法都要快得多，并且不会因为大量数据而超时。这里是数学链接。

def fib(n):
    v1, v2, v3 = 1, 1, 0  
    for rec in bin(n)[3:]: 
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2

- user3464678

Answer 5

def fibiter(n):
    f1=1
    f2=1
    tmp=int()
    for i in range(1,int(n)-1):
        tmp = f1+f2
        f1=f2
        f2=tmp
    return f2

或者使用并行赋值：

def fibiter(n):
    f1=1
    f2=1
    for i in range(1,int(n)-1):
        f1,f2=f2,f1+f2
    return f2

打印 fibiter(4)

- Andrei Volokitin

Answer 6

另一个可能的方法：

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=2
while i<n:
    e=d[-1]+d[-2]
    d.append(e)
    i+=1
print("Fibonacci series of {} is {}".format(n,d))

- Loki

---

虽然这段代码可以运行，但它似乎解决的问题与提问者所问的不同。你正在计算斐波那契数列中前 n 个值的列表，而他们的函数只计算第 n 个值。没有必要为此使用 O(n) 的内存。我真的不明白为什么你会回答两次，每次都有非常相似的代码。如果你认为有多个有用的算法，可以在同一个答案中发布它们。 - Blckknght

Answer 7

这项工作（直观地）

def fib(n):
    if n < 2:
        return n
    o,i = 0,1
    while n > 1:
        g = i
        i = o + i
        o = g
        n -= 1
    return i

- MsO

---

这是否回答了“我没有正确实现吗？”（我发现poke的代码很直观，“手动递减n”很烦人。） - greybeard

@老者谁在问“我没有实现得对吗？”？（倒数有什么问题，Python 允许它，为什么不使用呢？！） - MsO

谁在问... [用户：Ris] 是这个问题的最后一句话。在我看来，倒计时没有什么问题 - 我在评论中强调了手动（使用显式表达式、赋值、条件...），我不认为它是Python风格/Pythonic的。它是可以避免的冗长。 - greybeard

我理解你的意思，但我不是 Python 这个人，那只是一个想法（算法），只是用 Python 表达出来而已（仅此而已），-在阅读 SICP 的时候... - MsO

Answer 8

这个简单但最快的方法怎么样？（我刚刚发现！）

def fib(n):
    x = [0,1]
    for i in range(n >> 1):
        x[0] += x[1]
        x[1] += x[0]
    return x[n % 2]

注意！因此，这个简单的算法只使用了1个赋值和1个加法，因为循环长度缩短为1/2，每个循环包括2个赋值和2个加法。

- digitect38

---

我没有看到比"a-b-公式"更好的改进。你所知道的最快的方法是使用_O(log_ n)迭代的方法吗？ - greybeard

正确的是，在其他a-b形式中，分配数量为3*n，因为有一个隐藏的分配包括（任何交换问题都无法避免这个序列：temp = a，a = a + b，b = temp）。所以我可以说我的建议是更快的方法。实际上，我测试并检查结果比其他a-b形式快2倍或3倍。你能否在斐波那契问题中提供任何O(log n)算法的建议？ - digitect38

Answer 9

Python中的非递归斐波那契数列

def fibs(n):
    f = []
    a = 0
    b = 1
    if n == 0 or n == 1:
        print n
    else:
        f.append(a)
        f.append(b)
        while len(f) != n:
            temp = a + b
            f.append(temp)
            a = b
            b = temp

    print f

fibs(10)

输出： [0，1，1，2，3，5，8，13，21，34]

- karuna

---

这个回答是否回答了“我没有正确实现吗？”的问题？ - greybeard

斐波那契数列的值：0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、17711，...... 请将输出值与此值进行比较。 - karuna

我没有输出。我碰巧知道OEIS A000045，并且尝试改进'17/1年的2013/2问题的表述。 - greybeard

Answer 10

fcount = 0 #a count recording the number of Fibonacci numbers generated
prev = 0
current = 0
next = 1
ll = 0 #lower limit
ul = 999 #upper limit

while ul < 100000:
    print("The following Fibonacci numbers make up the chunk between %d and %d." % (ll, ul))
    while next <= ul:
        print(next)
        prev = current
        current = next
        next = prev + current
        fcount += 1 #increments count

    print("Number of Fibonacci numbers between %d and %d is %d. \n" % (ll, ul, fcount))        
    ll = ul + 1 #current upper limit, plus 1, becomes new lower limit
    ul += 1000 #add 1000 for the new upper limit
    fcount = 0 #set count to zero for a new batch of 1000 numbers

- Jedi_Jezzi