斐波那契数列之和

Question

我对Haskell还比较陌生。问题是找到不大于400万的所有偶斐波那契数之和。我不能使用列表。

如果我理解正确，下面的解决方案是错误的，因为它使用了列表：

my_sum = sum $ filter (odd) $ takeWhile (< 4000000) fibs

其中fibs是所有斐波那契数的列表。

不知何故，我很难不用Haskell的列表思考。有人能指导我解决这个问题吗？

问候

编辑：

如果有人感兴趣，我已经解决了这个问题。这是代码（看起来很笨拙，但仍然有效）：

findsum threshold = findsum' 0 1 0 threshold


findsum' n1 n2 accu t 
| n2 > t    = accu
| odd n2    = findsum' n2 n3 accu t 
| otherwise = findsum' n2 n3 accu2 t
where
    n3 = n2 + n1
    accu2 = accu + n2

- Rafal

---

这是作业吗？你已经尝试过什么了吗？ - Michael Boggess

不是作业 - 欧拉计划。我几天前也刚做了这个问题。 - Corey

为什么不能使用列表？ - clahey

@mjboggess：我写了一个基于列表的解决方案。我正在寻求如何在没有列表的情况下实现该解决方案的建议。 - Rafal

@Rafal - 但为什么呢？在 Haskell 中，如果使用适当的 fibs 定义，即使有一个列表，它也是惰性的。你最好让所有这些精美的机制来完成它们的工作，并直接表达解决方案。如果 fibs 被正确定义，那么实际上不会在内存中存在任何列表！ - MtnViewMark

Answer 1

你可能会发现在Excel中构建这个模型更容易，并从中找到代码的线索。在Excel中，这个操作非常简单。只需在第一个单元格中输入1，在其下方再次输入1。然后使每个下面的单元格加上它上面的两个值。(例如，单元格a3包含=A1+A2)。让下一列仅包含偶数值"即，如果(mod(a3,2)==0,a3,0)"。接下来，在第三列中放置你的运行总和。基于此，您应该能够得出递归解决方案。

另一种方法是从问题入手。你只需要一个总数，这就需要累加器。

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold

你可以在上面看到我的函数签名。我建立了一个漂亮的前端，它使用一个阈值（4,000,000）来决定何时停止生成斐波那契数列。然后我将这个阈值加上前两个斐波那契数和一个累加器传递给工作函数“sumFib”，该函数进行递归。哇...答案是“4613732”，没有列表...

n1是第n-1个斐波那契数，n2是第n-2个斐波那契数。

希望对你有所帮助。

编辑：这是我的完整解决方案：

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold
     | n1 > threshold = acc
     | otherwise = sumFib' (n2+n1) n1 newAcc threshold
            where newAcc = if n1 `mod` 2 == 0
                               then n1 + acc
                               else acc

- Tim Perry

---

很高兴能帮忙！这是一个有趣的休息，远离编写Java :) - Tim Perry

Answer 2

你可以使用延续传递风格的递归解决方案，而无需列表。

顺便说一下，遍历所有斐波那契数并过滤出奇数是解决这个问题的慢速方式。

- Nathan Hughes

Answer 3

再次举例说明计算机的实用性：

你可以不用计算机完成这个任务！

第一个观察结果：每三个斐波那契数中有一个是偶数，第一个偶数斐波那契数是F_3=2。

确实：奇数+奇数=偶数；奇数+偶数=奇数；偶数+奇数=奇数，这已经形成了一个循环。

第二个观察结果：F_3 + F_6 + F_9 + ... + F_{3k} = 1/2 (F_{3k+2} - 1)。

归纳法证明：F_3 = 2 = 1/2 (5 - 1) = 1/2 (F_5 - 1)。

F_3 + F_6 + ... + F_{3k+3} = 1/2 (F_{3k+2} - 1) + F_{3k+3} = 1/2 (F_{3k+2} + 2F_{3k+3} -1) = 1/2 (F_{3k+4} + F_{3k+3} -1) = 1/2 (F_{3k+5} -1)。

第三个观察结果：总和将有1333333个加数，最后一个加数是第3999999个斐波那契数。

第四个观察结果：F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)。

Wikipedia的证明

现在，我们可以把这些部分组合起来：

F_3 + F_6 + ... + F_3999999 = 1/2 (F_4000001 - 1) = 1/2 1/sqrt(5) (phi^4000001 - (1-phi)^4000001) - 1/2 = int(1/2 1/sqrt(5) phi^4000001)

这里的int是整数部分。最后一步有效，因为-1 < 1-phi < 0，所以(1-phi)^4000001几乎为零。你可能需要使用计算器得到数值。

- do_the_math