ネタバレ注意: プロジェクト オイラーの問題 #2 を答えを見ずに自分で解決しようとしている場合は、これを見ないでください。
プロジェクト オイラーの問題 2 (400 万以下のすべての偶数フィボナッチ数の合計を計算する)は既に完了しています。これらの問題を使用して、C/Ada のスキルを練習し、Common Lisp と Haskell を学ぶ。
Haskell でソリューションを再実装しようとすると、問題が発生します。古典的な方法では、間違った答えを計算しています。しかし、Haskell の実装は Common Lisp の実装に似ていると思います (正しい結果が得られます)。
このアルゴリズムは、n のフィボナッチ数のみを計算しn % 3 == 0ます。それの訳は
- 偶数値のフィボナッチ数 F(n) <= 4M のみを合計する必要があり、
- (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 を学習するのではなく、Haskell で自分の Lisp を再実装しているところです。これは、言語に付随するコーディング/問題解決のアプローチです)。
私は解決策を教えてくれる人を探しているわけではありません (これはcodez を使うことはできませんか? )。私はもっと探していますが、私の Haskell プログラムに何が欠けているかについての説明はもっとあります。バグはどこにあるのでしょうか、それとも非常に具体的な Haskell の特異な評価/パターン マッチングが欠けているのでしょうか? ありがとう。