0

我一直在努力将斐波那契数列中的每个数字写入文件，我知道我做错了什么，但我无法确定它。有没有更有效的方法？任何帮助表示赞赏。

import sys
import os
import time

known = {0:0, 1:1}

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

def fibonacci_fast(n):
    f = open('fib500.txt', 'w')
    if n in known:
        return known[n]
    res = fibonacci_fast(n-1) + fibonacci_fast(n-2)
    print res
    if fibonacci_fast:
        f.write(res)
    known[n] = res
    return res

def main():
    time_start = time.time()
    print fibonacci_slow(10)
    time_end = time.time()
    print "Time for slow fibonacci to complete ", time_end - time_start

    time_start = time.time()
    print fibonacci_fast(500)

    time_end = time.time()
    print "Time for fast fibonacci to complete ", time_end - time_start


if __name__ == '__main__':
    main()
4

2 回答 2

1

您需要从 fibonacci_fast 方法中写入文件。每次调用它时，它都会重新打开文件，并且由于您没有关闭它，因此无法保证它将被写入文件中。

至于速度，递归不适合您的计算。您不需要递归调用：

res = fibonacci_fast(n-1) + fibonacci_fast(n-2)

因为你可能已经想出了这些调用的返回值。最好从头开始工作，直到你得到你想要的值，而不用承受这种递归带来的开销。换句话说，采用迭代方法会更快。

正如您可能试图展示的那样，从速度/优化的角度来看，在斐波那契数列中生成第 n 个数并不是递归的好选择。

如果您将 fibonacci_fast 更改为以下内容：

def fibonacci_fast(n):
    known = [0, 1]
    count = 0
    for i in range(n):
        newNum = known[0] + known[1]
        known[0] = known[1]
        known[1] = newNum
    return known[0]

并运行您的测试脚本：

def main():
    time_start = time.time()
    print fibonacci_slow(20)
    time_end = time.time()
    print "Time for slow fibonacci to complete ", time_end - time_start

    time_start = time.time()
    print fibonacci_fast(20)
    time_end = time.time()
    print "Time for fast fibonacci to complete ", time_end - time_start

你得到：

6765
Time for slow fibonacci to complete  0.0043318271637
6765
Time for fast fibonacci to complete  0.00010085105896

并将其写入文件，您可以添加一个可以写入的文件参数：

def fibonacci_fast(n, f):
    known = [0, 1]
    for i in range(n):
        newNum = known[0] + known[1]
        known[0] = known[1]
        known[1] = newNum
        f.write(str(known[0]) + " ")
    return known[0]

并这样称呼它：

f = open("fib.txt", "w")
fibonacci_fast(20, f)
f.close()

或更“pythonic”的方式（更快一点）：

with open("fib.txt", "w") as f:
    fibonacci_fast(20, f)

如果您尝试生成序列中的第 500 个数字，您可以看到递归和迭代方法之间的巨大差异。完成递归函数需要几分钟（如果不是几小时，我还没有等到它），但执行迭代方法只需几分之一秒，即使将其写入文件也是如此。

有关斐波那契数列的更多信息，请参见此处。

于 2013-11-09T03:28:00.623 回答
0

您的递归有点笨拙，会多次重新计算每个数字。这是一个经典问题，这个迭代算法可以工作：

def fib2file(n, fname):
    with open(fname, 'w') as of:
        f1, f2, f3 = 0, 1, 0
        for _ in range(n):
            f1 = f2
            f2 = f3
            f3 = f1 + f2
            of.write('%d\n' % f3)
于 2013-11-09T03:28:44.790 回答