4

我对 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
4

3 回答 3

5

您可能会发现在 excel 中构建它然后从那里找出代码更容易。在excel中很容易做到这一点。只需将 1 放在第一个单元格中，然后将 1 放在其下方。然后使下面的每个单元格都添加上面的两个。（即，单元格 a3 包含 =A1+A2）。使下一列仅包含偶数值“即 if(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）来决定何时停止构建斐波那契数。然后我将这个加上前 2 个斐波那契数和一个累加器传递给执行递归的工作函数“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
于 2010-05-05T21:18:38.193 回答
3

您可以在没有列表的情况下使用递归解决方案来执行此操作，使用continuation-passing style。

顺便说一句，遍历所有斐波那契数并过滤掉奇数是解决此问题的缓慢方法。

于 2010-05-05T20:59:29.303 回答
3

再一次，一个非例子可以说明计算机有多有用：

你可以在没有电脑的情况下做到这一点！

第一个观察：每隔三个斐波纳奇数是偶数，第一个偶数斐波纳奇数是 F_3=2

确实：奇+奇=偶；奇数+偶数=奇数；even+odd=odd，这已经是闭合的圈子了

第二次观察：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 个斐波纳奇数。

第 4 次观察：F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)

维基百科的证明

现在，我们可以将这些部分放在一起： 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 几乎消失了。您可能想使用计算器来获取数值。

于 2010-05-14T20:24:12.697 回答