20

我对斐波那契数的迭代算法感兴趣，所以我在 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))

输出

0
无
1
1
1
1
1
1

4

13 回答 13

63

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

要解决这个问题，只需移动return y循环的外部。

替代实施

按照 KebertX 的示例，这是我个人用 Python 制作的解决方案。当然，如果您要处理许多斐波那契值，您甚至可能希望将这两种解决方案结合起来，并为这些数字创建一个缓存。

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a
于 2013-02-23T23:56:53.823 回答
5

您正在循环中返回一个值，因此该函数在 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 个斐波那契数。

于 2013-02-24T00:36:02.797 回答
1

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

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

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

y = 1
return y

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

y = 1
return y

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

这是另一个用户提出的一个很好的解决方案： How to write the Fibonacci Sequence in Python

于 2013-02-23T23:58:13.670 回答
0 
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

打印纤维(4)

于 2015-07-23T03:48:34.463 回答
0

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

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
于 2016-08-31T05:33:05.770 回答
0

这项工作（直观地）

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
于 2017-01-05T07:31:40.510 回答
0

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

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 次加法。

于 2017-01-06T17:56:51.247 回答
0 
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
于 2017-03-24T19:11:00.433 回答
0

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]

于 2017-04-10T10:35:12.617 回答
0

另一种可能的方法：

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))
于 2019-08-19T21:30:27.950 回答
-1

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

F(0) = 0;

F(1) = 1;

F(2) = 1；

F(3) = 2

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

F(N) = F(N-1) + F(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; 
}
于 2014-08-21T07:53:20.433 回答
-1

可能的解决方案：

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=0
while len(d)<n:
    temp=a+b
    d.append(temp)
    a=temp
    b=d[i+1]
    i+=1
print("Fibonacci series of {} is {}".format(n,d))
于 2019-08-19T21:15:32.247 回答
-3 
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()

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

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

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

于 2015-08-23T08:54:25.073 回答