问项目Euler #2 ( Fibonacci数之和在400万以下)的更有效解决方案

EN

我总是向人们提出这个问题的暗示。看一看序列的前几个数字--我用粗体将偶数设置为：

1，1，2，3，5，8，13，21，34，55，89,144

你能看到间隔上的图案吗？你能解释(理想情况下，证明)吗？

既然如此，你能想出一种直接生成斐波那契数的方法吗，而不是为它们过滤？(提示:从(1,2)开始，尝试一步生成(5,8)，然后(21，34)等，做一些代数，并想出如何同时应用生成规则的多次迭代。

无论如何，在用数字进行实际计算时，有更优雅的方法。我们可以编写一个生成器，而不是直接要求Python构建一个列表：

def even_fibonacci_up_to(n):
    a, b = 1, 2
    while b <= n:
        yield b # since 2 qualifies, after all.
        # Now calculate the next value.
        # math from the first step goes here when you figure it out!

注意yield关键字的使用。这允许我们将表达式even_fibonacci_up_to(4000000)看作是一种特殊的序列，其元素是按需生成的。与普通函数不同，普通函数只能return一次。)(在生成器中使用return将在到达yielding值时终止整个过程。)

我们可以使用内置的sum函数，而不是循环遍历这个序列来累加数字：

sum(even_fibonacci_up_to(4000000))

您的方法不错，尽管它可以被清理，我有一个更快、更直接的建议，比如使用一个简单的类。

• Knechtel的方法似乎创造了一个近乎无限的循环。
• Madison的递归方法超过输入40，达到"RuntimeError:最大递归深度超过“。但他们建议的第三种解决方案似乎没有错误地执行，但输出似乎不准确.我相信你只得到了最大的数字，达克。我的也一样。

我认为这是你最好的，最准确的，最简单的(也是最快的给出一个正确的解决方案)：

def fib(n):   # return Fibonacci series up to n
    result, a, b = list(), 0, 1 # set variables
    result.append(0) # Initial Fibonacci Zero
    while b < n:
        if b % 2 == 0:
            result.append(b)
        a, b = b, a+b
    return result

def fibSum(n):
    return sum(map(int, fib(n)))

print(fibSum(4000000))

希望这能有所帮助。祝好运!

此外，我建议在打印代码清洁时使用“\n”作为新行，没有必要使用几个打印语句，但我们都是从某个地方开始的，我自己只编写了大约一年的Python程序，但我的背景中也有其他语言，我读了很多书。几个关键注意事项: map允许您轻松地总结一个in /truple列表，您可以使用sum而不是在列表中递增并将其加起来，在“几乎”所有情况下，它应该更快(字符串是一个不同的故事)。再次祝你好运！

我保留了你的国防部2模数是你的朋友。修改内置的周边不是你的朋友，如果你必须这样做，很可能你做错了什么。只是思考的食粮。

基准：

你的守则：

产出: 4613732

运行总时间: 0.000175秒( Python )

总运行时间: 0.000069秒( Pypy )

我的建议：

产出: 4613732

运行总时间: 0.000131秒( Python )

总运行时间: 0.000053秒( Pypy )

编辑:或者，您可以只使用以下内容：

def fib2(n):
    result, a, b = 0, 0, 1
    while b < n:
        if b % 2 == 0:
            result += b
        a, b = b, a+b
    return result

print(fib2(4000000))

我个人更喜欢让Fibonacci自己来构建一个单一用途类，不管是出于什么原因。显然，它应该稍微快一点，但我还没有测试它。

Fibonacci序列是一个非常适合递归解决方案的问题。如果您还没有了解递归，我强烈推荐它，因为它提供了一种全新的方法来看待问题。

要找到第n个Fibonacci数，您可以使用如下所示的内容。

def fibonacci(n):
    if n < 2: return n
    return fibonacci(n-1)+fibonacci(n-2)

fibonacci(10) # returns 55

这个答案之所以如此清晰，是因为它的框架方式和斐波纳契序列是一样的。要找到一个斐波那契数，只需知道前两个。

尽管如此，递归确实引入了一些有趣的问题。要找到第100个斐波那契数，需要花费惊人的时间。这样的问题通常需要缓存才能提高递归的效率。

如果我们从相反的方向来处理这个问题呢？我们可以从底层开始，从上往上爬，而不是从上开始往下走。然后，状态存储在函数的参数中。

def fibonacci(a, b, n):
    if n < 3: return a + b
    return fibonacci(b, a+b, n-1)

fibonacci(0, 1, 10) # returns 55

我希望你喜欢这种递归的味道。如果有什么不清楚的话请告诉我，我很乐意帮忙把事情弄清楚。但是，如果效率是您的目标，那么Python的递归可能不是最好的。

如果递归不是您的问题，或者您打算计算非常大的fibonacci数，您可能需要一个迭代解决方案(实际上，您自己的解决方案非常好)。如果您在寻找小于n的最大fibonacci数，则迭代解决方案工作得特别好。

def fibonacci(n):
    # finds the largest fibonacci number less than n
    a, b = 0, 1
    while(a+b) < n:
        a, b = b, a+b
    return b