无法在我的Haskell程序中找到错误(来自Project Euler的Puzzle#2)

Question

SPOILER ALERT:如果你试图自己解决Project Euler的问题#2,不要看这个问题.

我已经完成了Euler项目的问题#2(计算所有偶数Fibonacci(n)数小于或等于400万的总和) - 我正在使用这些问题练习我的C/Ada技能,重新审视我的Common Lisp和学习Haskell.

当我试图在Haskell中重新实现我的解决方案时,我遇到了一个问题.在古典时尚中,它正在计算错误的答案.但是,我认为我的Haskell实现类似于我的Common Lisp实现(它确实产生了正确的结果.)

该算法仅计算n的斐波那契数n % 3 == 0.这是因为

1. 我们只需求和偶数斐波纳契数F(n)<= 4M,和
2. (n%3 == 0)< - >(F(n)%2 == 0)

这是Haskell实现:

uber_bound      = 40000000  -- Upper bound (exclusive) for fibonacci values
expected        = 4613732   -- the correct answer

-- The implementation amenable for tail-recursion optimization
fibonacci :: Int -> Int
fibonacci n = __fibs (abs n) 0 1
  where
    -- The auxiliary, tail-recursive fibs function
    __fibs    :: Int -> Int -> Int -> Int
    __fibs 0 f1 f2 = f1 -- the stopping case
    __fibs n f1 f2 = __fibs (n - 1) f2 (f1 + f2)

-- NOT working. It computes 19544084 when it should compute 4613732
find_solution :: Int
find_solution = sum_fibs 0
  where
    sum_fibs :: Int -> Int
    sum_fibs n = 
      if fibs > uber_bound
        then
          0 -- stopping condition
        else
          -- remember, (n % 3 == 0) <--> (fib(n) % 2 == 0)
          -- so, seek the next even fibs by looking at the
          -- the next n = n@pre + 3
          fibs + sum_fibs (n + 3)
      where
        fibs = fibonacci n

actual = find_solution

problem_2 = (expected == actual)

19544084正确的答案是打印的东西4613732.我的Common Lisp解决方案(确实有效)如下所示.

我以为我的Haskell实现会像它一样,但我错过了一些东西.

(set `expected 4613732)  ;; the correct answer

;; tail-recursive fibonacci
(defun fibonacci (n)
  (labels 
    ( ;; define an auxiliary fibs for tail recursion optimization
      (__fibs (n f1 f2)
        (if (<= n 0)
          f1 ;; the stopping condition
          (__fibs 
            (- n 1) ;; decrement to ensure a stopping condition 
            f2 
            (+ f1 f2))))
    ) ;; end tail_rec_fibs auxiliary
   (__fibs n 0 1)
  );; end labels
) ;; end fibonacci

(defun sum_fibs(seed)
  (let*
    ((f (fibonacci seed)))
    (if (> f 4000000)
      0
    ;; else
      (+ f (sum_fibs (+ 3 seed)))
    );; end if
  );; end of let
);; end of sum-fibs

(defun solution () (sum_fibs 0))

(defun problem_2 ()
  (let
    (
     (actual (solution))
    )
    (format t "expected:~d actual:~d" expected actual)
    (= expected actual)
  )
) ;; end of problem_2 defun

我到底在做什么？假设我正在使用尼安德特人的方法来学习Haskell(我目前只是在Haskell上重新实现我的Lisp,而不是学习惯用的Haskell,这是一种与语言一致的编码/问题解决方法.)

我不是在寻找有人给我解决方案(这不是我可以使用的密码吗？).我看起来更多,但更多的是解释我在Haskell程序中缺少的东西.错误在哪里,或者我错过了一个非常具体的Haskell特性评估/模式匹配的东西？谢谢.

Answer 1

你有一个错字

uber_bound = 40000000

什么时候应该

uber_bound = 4000000

仅供参考,更惯用的解决方案是生成所有Fibonacci数字的列表(懒惰评估对此非常有用),然后使用takeWhile,filter和sum.

这也会更有效,因为尾递归在Haskell中很少有用(延迟评估会妨碍),并且由于列表的元素是共享的(如果列表是适当定义的),每个Fibonacci数只计算一次.