斐波纳契数的和(Sum of Fibonacci numbers)

斐波纳契数的和(Sum of Fibonacci numbers)

我对Haskell比较陌生。 问题是找到所有偶数Fibonacci数不超过4百万的总和。 我无法使用列表。

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

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

I'm rather new to Haskell. The problem is to find the sum of all even Fibonacci numbers not greater than 4 million. I can't use lists.

If I understand correctly, the below solution is wrong, because it uses lists:

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

Where fibs is the list of all Fibonacci numbers.

Somehow, I find it difficult not to think in Haskell in terms of lists. Could anyone guide me to a solution to this problem?

Regards

EDIT:

If anyone is interested, I've solved this problem. Here is the code (very clumsy-looking, but works nevertheless):

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

最满意答案

你可能会发现在excel中构建它比较容易，然后从那里找出代码。 在excel中这样做很容易。 只需将1放入第一个单元格中，并将1放在其下方。 然后让下面的每个单元格添加上面的两个单元格。 （即，单元格a3包含= A1 + A2）。 使下一列仅包含偶数值“ie，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

You might find it easier to build this in excel and then figure the code out from there. It is pretty easy to do this in excel. Just put 1 in the first cell and put 1 just below it. Then make every cell below that add the two above it. (ie, cell a3 contains =A1+A2). Make the next column contain only even values "ie, if(mod(a3,2)==0,a3,0)". Next, put your running sum in the third column. Based on that you should be able to come up with the recursive solution.

Another way is to start with the problem. You only want a total which screams for an accumulator.

sumFib :: Integer -> Integer sumFib threshold = sumFib' 1 1 0 threshold sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer sumFib' n1 n2 acc threshold

You can see the signatures of my functions above. I built a pretty front end that takes a threshold (4,000,000) to decide when to quit building fibonacci numbers. Then I pass this plus the first 2 fibonacci numbers and an accumulator into the worker function "sumFib" which does the recursion. Voila...the answer, "4613732", without a list....

n1 is the n-1 fibonacci number and n2 is the n-2 fibonacci number.

Hope that helps.

EDIT: here is my full solution:

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