Project Euler Problem 2 #mitori_clj

problem_2.clj

(defn fib
  "Returns the nth Fibonacci number."
  ^long
  [n]
  (-> (* 0.5 (inc (Math/sqrt 5)))       ; golden ratio
      (Math/pow n)
      (/ (Math/sqrt 5))
      (+ 0.5)
      Math/floor
      long))

(loop [n 0 sum 0]
  (let [x (fib n)]
    (if (< x 4000000)
      (recur (+ n 3) (+ sum x))
      sum)))

https://gist.github.com/4239310 で議論のあった効率化をこの問題でもやってみます．実は (fib n) が偶数になるのは n が 3 の倍数のときだけなので，(fib n) < 4000000 なる全ての n について (fib n) を計算する必要はありません．

というわけで解答を更新してみました．even? も不要になりました．

一般項で解を求めることのメリットとデメリット

• メリット
  • オブジェクトを作らない = GC 走らない
  • 数列の全てを計算しなくてもよい（この問題の場合は 1/3）
• デメリット
  • コードが長くなる
  • 大学の課題で使うと点数をもらえない

大学の課題、フィボナッチ数求めるプログラムで一般項使ったら点数もらえなかった。

— ねこはる (@halcat0x15a) October 29, 2012

<script src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

(fn f [...] (cons ... (lazy-seq (f ... と (fn f [...] (lazy-seq (cons ... (f ... でどちらを使うかは, 自分の中で特に判断基準がなく, 若干多くみかける気がする前者を使ってましたが, 外から見て LazySeq であることが分かるからというのは, なるほど後者を選ぶ理由になりますね.

(fib n) が偶数になるのは n が 3 の倍数のときだけ

！？
Wikipedia/フィボナッチ数 を読んでみたら「性質」のところに載ってた. おどろき.
ちなみに, 5 の倍数になるのは 5 の倍数番目の項だけらしい...

一般項使ったら点数もらえなかった

その先生に「不可」をあげたい.

この解答が初学者向けおすすめ解答になると思うのですがいかがでしょうか > みなさま
初学者をどの辺と定義するかにもよりますが、「フィボナッチ数列を作る」の回答としていきなりこれを提示するのは、厳しいんじゃないでしょうか。 繰り返しで作る->再帰で作る->シーケンスで作るという流れで行き着くのが妥当かと。

lazy-seqの場所について考えてみたんですが、(cons x (lazy-seq ...)) がいいと思います。
この形であれば、「すでにxの値は確定してるけど、続きは必要だったら計算するよ」というのを明確に表現していると思うからです。 結果についても、 全体でなく、 next部がLazySeqになっているはず(未確認)なので、その情報が必要な場合はそのように捉えるべきかと。
逆に、(lazy-seq (cons ...)) のパターンだと、結果のfirst を取るのにコストがかかる可能性を考えなくてはいけないのでは？

@ypsilon-takai の書いた iterate 版は Programming Clojure の中でも紹介されている方法で、シンプルで Clojure らしいコードになっているので、すごく好きです。

Programming Clojure では、末尾再帰なし版、末尾再帰(loop recur)版、lazy-seq 版と紹介され、最後が iterate による遅延シーケンスを返す版だったと思います。