3

SPOILER ALERT：如果你试图自己解决 Project Euler 的问题 #2 而不看答案，请不要看这个。

我已经完成了 Project Euler 的第 2 题（计算小于或等于 400 万的所有偶数 Fibonacci(n) 数的总和） ——我正在使用这些问题来练习我的 C/Ada 技能，重新审视我的 Common Lisp 和学习 Haskell。

当我试图在 Haskell 中重新实现我的解决方案时，我遇到了问题。以经典方式，它正在计算错误的答案。但是，我认为我的 Haskell 实现类似于我的 Common Lisp 实现（它确实产生了正确的结果。）

该算法仅计算 n where 的斐波那契数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，这是一种与语言一起使用的编码/问题解决方法。）

我不是在找人来给我解决方案（这不是我可以破坏 codez 吗？）。我正在寻找更多，但更多是为了解释我在 Haskell 程序中缺少的内容。错误在哪里，或者我错过了一个非常具体的 Haskell 特质评估/模式匹配的东西？谢谢。

4

2 回答 2

7

你有一个错字

uber_bound = 40000000

什么时候应该

uber_bound = 4000000

仅供参考，更惯用的解决方案是生成所有斐波那契数列的列表（惰性求值对此非常有用），然后使用takeWhile,filter和sum.

这也将更有效率，因为尾递归在 Haskell 中很少有帮助（延迟评估会妨碍），并且由于列表的元素是共享的（如果列表定义得当）每个斐波那契数只计算一次。

于 2012-07-13T03:21:18.000 回答
1

已删，不宜剧透。dbaupp 的建议很好。使用 zipWith 有一个众所周知的表达式，但我认为它太聪明了——还有更直接的方法。

于 2012-07-13T09:11:46.590 回答