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)))

横から解説

数値計算では,

long fib(long n) {
  retuern (long)floor(pow(0.5 * (1 + sqrt(5.0)), n) / sqrt(5.0) + 0.5);
}

と書くところを, 計算のパーツを分離したいけど, 変数は沢山使いたくないので,

long fib(long n) {
  double v;

  v = 0.5 * (1 + sqrt(5.0));
  v = pow(v, n); 
  v /= sqrt(5.0);
  v += 0.5;
  v = floor(v);
  return (long)v;
}

と書きたいような場面が割とあるんですね.

この場面を何度か見たことがあると, tnoda さんの -> を見て,「なるほどこりゃ便利」となる訳です.

@kohyama

lazy-seq のお手本のような使い方だと思いました．今まで lazy-seq を使った遅延シーケンスの作り方を説明するときの例に困っていたのですが，今後，このコードを有り難く使わせてもらいます．正直言うと，この問題で lazy-seq を使って解いてくるパターンは想定していませんでした．

重箱の隅をつつくと，私は，

(defn fibs [a b] (cons a (lazy-seq (fibs b (+ a b)))))

よりも，

(defn fibs' [a b] (lazy-seq (cons a (fibs b (+ a b)))))

と，lazy-seq を cons の前に出す形のほうをよく書きます．というのも，

user> (type (fibs 0 1))
clojure.lang.Cons

user> (type (fibs' 0 1))
clojure.lang.LazySeq

のように，cons を前に出すと遅延シーケンスなのに type が clojure.lang.Cons になってしまうからです．

---

もう一つ，「数値計算あるある」もありがとうございます．数値計算していると本当によくありますよね > 一つの変数を更新していくスタイル．

実をいうと，数式で -> を使うのは，自分では何となく読み易いと思っていたのですが，なぜ，-> が読み易いのか，よく分かっていないところがありました．言われてみれば自分も @kohyama が例示している書き方を何度も見たり書いたりしたことがあり，それで -> に違和感が無いんだと納得できました．とても参考になりました．

@ypsilon-takai iterate を使った別解ありがとうございます．この解答が初学者向けおすすめ解答になると思うのですがいかがでしょうか > みなさま

ところで，シーケンスを使えば immutable な値に対してプログラミングする Clojure でも状態を表現でき，iterate はその状態遷移を表現するのにとても便利です．そういう意味で，初学者に iterate の最初の例として (iterate inc 1) を見せるのは誤解のもとだと考えており，どうせなら，@ypsilon-takai の解答のほうが良いと思います．

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 による遅延シーケンスを返す版だったと思います。