Python 斐波那契数列的迭代算法

An iterative algorithm for Fibonacci numbers

提问by Ris

I am interested in an iterative algorithm for Fibonacci numbers, so I found the formula on wiki...it looks straight forward so I tried it in Python...it doesn't have a problem compiling and formula looks right...not sure why its giving the wrong output...did I not implement it right ?

我对斐波那契数列的迭代算法很感兴趣，所以我在 wiki 上找到了这个公式……它看起来很直接，所以我在 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))

output

输出

0
None
1
1
1
1
1
1

0
无
1
1
1
1
1
1

采纳答案by poke

The problem is that your return yis within the loop of your function. So after the first iteration, it will already stop and return the first value: 1. Except when nis 0, in which case the function is made to return 0itself, and in case nis 1, when the for loop will not iterate even once, and no returnis being execute (hence the Nonereturn value).

问题是你return y在你的函数循环中。所以在第一次迭代之后，它已经停止并返回第一个值：1。除了whenn是0，在这种情况下，函数会返回0自己，如果n是1，当for循环甚至不会迭代一次，并且没有return正在执行（因此None返回值）。

To fix this, just move the return youtside of the loop.

要解决此问题，只需移动return y循环的外部即可。

Alternative implementation

替代实现

Following KebertX's example, here is a solution I would personally make in Python. Of course, if you were to process many Fibonacci values, you might even want to combine those two solutions and create a cache for the numbers.

按照 KebertX 的示例，这是我个人在 Python 中制作的解决方案。当然，如果您要处理许多 Fibonacci 值，您甚至可能想要组合这两种解决方案并为数字创建缓存。

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

回答by John Hornsby

On fib(0), you're returning 0 because:

在 fib(0) 上，您返回 0，因为：

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

On fib(1), you're returning 1 because:

在 fib(1) 上，您返回 1，因为：

y = 1
return y

On fig(2), you're returning 1 because:

在 fig(2) 上，您返回 1 是因为：

y = 1
return y

...and so on. As long as return yis inside your loop, the function is ending on the first iteration of your for loop every time.

...等等。只要return y在您的循环内，该函数每次都会在您的 for 循环的第一次迭代中结束。

Here's a good solution that another user came up with: How to write the Fibonacci Sequence in Python

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

回答by KebertX

You are returning a value within a loop, so the function is exiting before the value of y ever gets to be any more than 1.

您在循环中返回一个值，因此函数在 y 的值变得大于 1 之前退出。

If I may suggest something shorter, and much more pythonful:

如果我可以建议更短，更pythonful的东西：

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

This will do exactly the same thing as your algorithm, but instead of creating three temporary variables, it just adds them into a list, and returns the nth fibonacci number by index.

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

回答by yadriel

Assuming these values for the fibonacci sequence:

假设斐波那契数列的这些值：

F(0) = 0;

F(0) = 0;

F(1) = 1;

F(1) = 1;

F(2) = 1;

F(2) = 1;

F(3) = 2

F(3) = 2

For values of N > 2 we'll calculate the fibonacci value with this formula:

对于 N > 2 的值，我们将使用以下公式计算斐波那契值：

F(N) = F(N-1) + F(N-2)

F(N) = F(N-1) + F(N-2)

One iterative approach we can take on this is calculating fibonacci from N = 0 to N = Target_N, as we do so we can keep track of the previous results of fibonacci for N-1 and N-2

我们可以采用的一种迭代方法是计算从 N = 0 到 N = Target_N 的斐波那契，这样做我们可以跟踪 N-1 和 N-2 的斐波那契之前的结果

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}

回答by Andrei Volokitin

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

or with parallel assignment:

或并行分配：

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

print fibiter(4)

打印纤维(4)

回答by tony

import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

Disclaimer: I am currently on a mobile device and this may not be totally correct

免责声明：我目前使用的是移动设备，这可能不完全正确

This algorithm utilizes a gap in some other peoples' and now it is literally twice as fast. Instead of just setting bequal to aor vice versa and then setting ato a+b, I do it twice with only 2 more characters. I also added speed testing, based off of how my other iterative algorithm went. This should be able to go to about the 200,000th Fibonacci number in a second. It also returns the length of the number instead of the whole number, which would take forever.

该算法利用了其他一些人的差距，现在它的速度实际上是其两倍。而不是只是设置b等于a或反之亦然，然后设置a为a+b，我只用另外 2 个字符做了两次。我还根据我的其他迭代算法的运行情况添加了速度测试。这应该能够在一秒钟内达到大约第 200,000 个斐波那契数。它还返回数字的长度而不是整数，这将花费很长时间。

My other one could go to the second Fibonacci number, as indicated by the built in clock: in 10^-6 seconds. This one can do it in about 5^-6. I'm going to get some more advanced algorithms soon and refine them for utmost speed.

我的另一个可以转到第二个斐波那契数，如内置时钟所示：在 10^-6 秒内。这个可以在大约 5^-6 内完成。我将很快获得一些更高级的算法，并以最快的速度改进它们。

回答by user3464678

I came across this on another threadand it is significantly faster than anything else I have tried and wont time out on large numbers. Here is a linkto the math.

我在另一个线程上遇到了这个问题，它比我尝试过的任何其他方法都快得多，并且不会在大量数据上超时。这是数学的链接。

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

回答by MsO

This work (intuitively)

这项工作（直觉上）

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

回答by digitect38

How about this simple but fastest way... (I just discovered!)

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

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

Note! as a result, this simple algorithm only uses 1 assignment and 1 addition, since loop length is shorten as 1/2 and each loop includes 2 assignment and 2 additions.

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

回答by Jedi_Jezzi

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