斐波纳契数的和 [英] Sum of Fibonacci numbers

问题描述

我对Haskell比较陌生。问题是要找到所有甚至不超过400万的斐波纳契数的总和。我无法使用列表。

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

  my_sum = sum $ filter（odd）$ takeWhile（< 4000000）fibs 
  

其中 fibs 是所有Fibonacci数字的列表。

不知何故，我觉得很难不以Haskell的名单来思考。任何人都可以指导我解决这个问题吗？

问候

编辑：

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

  findsum阈值= findsum'0 1 0阈值
 
 
 findsum'n1 n2 accu t 
 | n2> t = accu 
 |奇数n2 = findsum'n2 n3 accu t 
 |否则= findsum'n2 n3 accu2 t 
其中
 n3 = n2 + n1 
 accu2 = accu + n2 
  

解决方案

你可能会发现在excel中构建它比较容易，然后从那里找出代码。在excel中这样做很容易。只需将1放入第一个单元格中，并将1放在其下方。然后让每个单元格都加上它上面的两个单元格。 （即，单元格a3包含= A1 + A2）。使下一列仅包含偶数值即，如果（mod（a3,2）== 0，a3,0）。接下来，把你的跑步总和放在第三栏。基于此，您应该能够想出递归解决方案。

另一种方法是从问题开始。您只需要一个累计器的尖叫。

  sumFib :: Integer  - >整数
 sumFib阈值= sumFib'1 1 0阈值
 
 sumFib'::整数 - >整数 - >整数 - >整数 - >整数
 sumFib'n1 n2 acc阈值
  

您可以在上面看到我的函数的签名。我建立了一个漂亮的前端，需要一个门槛（400万）来决定何时停止建立斐波那契数字。然后我把这个加上前两个斐波纳契数和一个累加器加入到进行递归的工作函数sumFib中。 Voila ...答案是4613732，没有列表....

n1是n-1斐波纳契数，n2是n-2斐波纳契数。

希望有所帮助。

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

  sumFib :: Integer  - >整数
 sumFib阈值= sumFib'1 1 0阈值
 
 sumFib'::整数 - >整数 - >整数 - >整数 - >整数
 sumFib'n1 n2 acc阈值
 | n1>阈值= acc 
 |否则= sumFib'（n2 + n1）n1 newAcc阈值
其中newAcc =如果n1`mod` 2 == 0 
然后n1 + acc 
 else acc 
  

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

解决方案

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

这篇关于斐波纳契数的和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！