2

私はLispでプロジェクトオイラーの質問2を解決しようとしています。この再帰的なソリューションは実行時にスタックを爆破しますが、Lisp（clispを使用）は末尾再帰を認識すると思いました。これはトップレベルに入力されています。

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"

   (if (> f2 4000000) sum)
   (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                (+ sum f2) 
                               sum))

私の実装は最適化のために正しく配置されていませんか？私が慣用的な再帰に頼ることができなければ、これは私のLisp教育をかなり妨げるだろうと思います。

4

4 に答える 4

9

再帰 (または反復) は必要ありません。

3 つおきのフィボナッチ数は偶数です。

1 1 2 3 5 8 13 21 34 55 89 144 ...

また、各偶数フィボナッチ数 (太字) は先行する 2 つの奇数フィボナッチ数の合計であるため、F n までの偶数フィボナッチ数の合計は、F nまでのすべてのフィボナッチ数の合計のちょうど半分です(F nはもちろん偶数です)。

ここで、最初のn 個のフィボナッチ数の合計は F n +2  − 1 です。これは帰納法によって簡単に確認できます。最初のn  + 1 個のフィボナッチ数の合計は F 1  + F 2  + ... + F n  +です。 F n +1、これは仮説によってF n +2  − 1 + F n +1に等しく 、フィボナッチ数の定義によってF n +3 − 1 に等しくなります。

したがって、F 3 N ≤ 4,000,000 となる最大のNを見つけることができれば、 求められる合計は (F 3 N +2  − 1) / 2 になります。

(残りの詳細はお任せしますが、ここからは簡単です。)

于 2010-12-04T11:03:23.540 に答える
4

1)コードの構文エラーを修正します。

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (if (> f2 4000000) 
       sum   ;; here was a closing bracket 
       (e2-problem f2 (+ f1 f2) (if (evenp f2) 
                                    (+ sum f2) 
                                    sum))))  ;; 2 more brackets here

2) SBCLを使用します。CLISP は、末尾再帰を検出するほど親切ではありません。

3) 利用可能な最高の最適化レベルを使用します。

(defun e2-problem (&optional (f1 1) (f2 1) (sum 0))  
   "Sum fibonacci sequence, even terms up to 4 million"
   (declare (optimize (debug 0)))  ;; optimization
   ...
于 2010-12-04T03:21:49.363 に答える
4

Lisp (clisp を使用) は末尾再帰を認識すると思いました

テール コールの削除を実装する環境は、Schemeでは必須ですが、Common Lisp などの他のほとんどの Lisp 方言では必須ではありません。

于 2010-12-03T22:54:49.683 に答える
2

あなたのコードは無限ループを実装しています。終了しません。

ループの使用:

(defun e2-problem-a (n)
  "Sum fibonacci sequence, even terms up to n"
  (loop for f1 = 1 then f2
        and f2 = 1 then (+ f1 f2)
        while (<= f2 n)
        when (evenp f2) sum f2))
于 2010-12-04T01:48:17.737 に答える