Skip to content

Instantly share code, notes, and snippets.

@tnoda
Created December 7, 2012 13:58
Show Gist options
  • Save tnoda/4233420 to your computer and use it in GitHub Desktop.
Save tnoda/4233420 to your computer and use it in GitHub Desktop.
Project Euler Problem 2 #mitori_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)))
@tnoda
Copy link
Author

tnoda commented Dec 11, 2012

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

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

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

— ねこはる (@halcat0x15a) October 29, 2012
<script src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

@kohyama
Copy link

kohyama commented Dec 12, 2012

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

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

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

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

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

@ypsilon-takai
Copy link

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

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

@bouzuya
Copy link

bouzuya commented Jan 13, 2013

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment