haskell - 斐波那契数的总和

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

Answer 1

您可能会发现在 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