読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

SICPの勉強 問題1.37

Clojure SICP

SICP1.3.3の問題1.37を解いてみる。

recursive process:

(defn cont-frac [n d k]
  (letfn [(rec [i]
    (if (= i k) 
      (/ (n i) (d i))
      (/ (n i) (+ (d i) (rec (inc i))))))]
    (rec 1)))

iterative process:

(defn cont-frac [n d k]
  (loop [i k result 0]
    (if (zero? i)
      result
      (recur (dec i) (/ (n i) (+ (d i) result))))))

idiomatic clojure:

(defn cont-frac [n d k]
  (->> (range k 0 -1)
       (map (juxt n d))
       (reduce (fn [F [N D]] (/ N (+ D F))) 0)))

recursive processのいいところは、元の式を見てすぐイメージする通りに、外から内に記述していけること。つまり、n1とd1についてまず考え、そして次にn2とd2...nkとdk再帰するたびに内側に潜っていく形になる。しかし、その分外側の処理をスタックに残していくのでメモリ効率は悪い。

内側から解決していけば、つまりi=kからはじめてi=1まで下がっていけば、後回しにする処理なしで再帰できる。あるいはreduceを使って直接再帰することすらなしに記述できる。そのイメージさえつかめてしまえばこのケースでは可読性も何ら劣っていないように思う。

これらを使って1/φの近似値を求めてみる(φは黄金比):

(cont-frac (constantly 1.0) (constantly 1.0) 10)

結果:

0.6179775280898876

1/φが0.618034あたりなのでk=10で小数点4桁まで正しい結果が出ている。