これもファレイ数列の問題です。
数えるだけなので、他にいい方法もありそうですが、70の方法で正面から解いてます。
ところが、初めに作ったものは再帰で実装して作ったデータを全部持っていたため。OutOfMemoryになってしまった
で、今ちょうど読んでいる、Joy of Clojureで、遅延評価のクイックソートのことが出ていたので、それを使ったらできた。
ついでにJoCに出ていた、名前付き引数を使ってデータ定義をしなくてもいいようにしてみたけれど、あまりよくないかな。
結局、ファレイ数列を生成する関数を作ればいいのです。ある2つの分数があったとき、その間のすべての対象を求めるわけです。
こんな感じ。
1)分数をa/bとc/dでa/b < c/dとします。
2)空の結果リストと待ちスタックを作ります。
3)中間数Xを求めます。
(a+c)/(b+d)
4)求めたXと分母の最大値を比べて
4-1) Xの分母が分母の最大値より大きい場合、a/bの右にはc/dしか無いので、a/bを結果リストに入れて、待ちスタックの最初の数Yを取り出し、c/dとYで3)に戻ります。
4-1-1) 待ちスタックが空だったら、c/dを結果リストに入れて、結果リストを返す。
4-2) Xの分母が分母の最大値以下の場合、c/dを待ちスタックに入れて、a/bとXで3)に戻ります。
この手順で分母が4以下のファレイ数列を作ってみます。
0/1と1/1で始めます。
a/b c/d X 結果 待ち
0/1 1/1 1/2 4-2パターン
1/1
0/1 1/2 1/3 4-2パターン
1/2 1/1
0/1 1/3 1/4 4-2パターン
1/3 1/2 1/1
0/1 1/4 1/5 4-1パターン
0/1 1/2 1/1
1/4 1/3 2/7 4-1パターン
0/1 1/4 1/1
1/3 1/2 2/5 4-1パターン
0/1 1/5 1/3
1/2 1/1 2/3 4-2パターン
0/1 1/5 1/3 1/1
1/2 2/3 3/5 4-1パターン
0/1 1/5 1/3 1/2
2/3 1/1 3/4 4-2パターン
0/1 1/5 1/3 1/2 1/1
2/3 3/4 5/7 4-1パターン
0/1 1/5 1/3 1/2 2/3
3/4 1/1 4/5 4-1パターン
0/1 1/5 1/3 1/2 2/3 3/4
=> 0/1 1/5 1/3 1/2 2/3 3/4 1/1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ;; Problem 71 : 2011/12/13 | |
| ;; "Elapsed time: 54026.250264 msecs" | |
| (defn my-numerator [n] | |
| (if (integer? n) | |
| n | |
| (numerator (rationalize n)))) | |
| (defn my-denominator [n] | |
| (if (integer? n) | |
| 1 | |
| (denominator (rationalize n)))) | |
| (defn frac-reduce [n d] | |
| (let [frac (/ n d)] | |
| [(my-numerator frac) (my-denominator frac)])) | |
| (defn farey-mediant [left-f right-f] | |
| (let [[l-n l-d] left-f | |
| [r-n r-d] right-f] | |
| (frac-reduce (+ l-n r-n) (+ l-d r-d)))) | |
| ;; [<left-tgt> <right-tgt> <right-list>] | |
| (def farey-list [[1 3] [1 2] nil]) | |
| (defn pe-73 [f-list lmt] | |
| (let [[l-f r-f r-list] f-list] | |
| (if (empty? r-f) | |
| (list l-f) | |
| (lazy-seq | |
| (let [next-tgt (farey-mediant l-f r-f)] | |
| (if (> (last next-tgt) lmt) | |
| (cons l-f (pe-73 [r-f (first r-list) (next r-list)] lmt)) | |
| (pe-73 [l-f next-tgt (cons r-f r-list)] lmt))))))) | |
| ;; named arg version. no good. | |
| ;; "Elapsed time: 70448.462305 msecs" | |
| (defn farey-seq [lmt & {:keys [start end tail] | |
| :or {start [0 1] | |
| end [1 1] | |
| tail nil}}] | |
| (if (empty? end) | |
| (list start) | |
| (lazy-seq | |
| (let [new-f (farey-mediant start end)] | |
| (if (> (last new-f) lmt) | |
| (cons start (farey-seq lmt | |
| :start end | |
| :end (first tail) | |
| :tail (next tail))) | |
| (farey-seq lmt | |
| :start start | |
| :end new-f | |
| :tail (cons end tail))))))) | |
| (defn pe-73 [] | |
| (+ -2 | |
| (count | |
| (farey-seq 12000 | |
| :start [1 3] | |
| :end [1 2])))) |
- my-numerator
- my-denominator
- frac-reduce
- farey-mediant
前の問題などで使った関数
遅延評価のやつ。
- farey-list
計算用のデータの定義。
[a/b] [c/d] [待ちスタック]
[[0 1] [1 1] nil] にすると、ファレイ数列が全部出ます。
- pe-73
ロジックを実装したもの。ただ、遅延評価になっているので、結果リストは吐き出されるだけで、データとしては保持していない。
遅延評価なので、1000000でも、10こくらいならすぐに答が返ります。
user> (take 10 (farey-seq 1000000))
([0 1] [1 1000000] [1 999999] [1 999998] [1 999997] [1 999996] [1 999995] [1 999994] [1 999993] [1 999992])
名前付き引数のやつ
- farey-seq
ロジックは同じ。
引数に最大値だけ与えると、ファレイ数列を返します。
user> (farey-seq 5)両端を与えると、その間だけ返します。
([0 1] [1 5] [1 4] [1 3] [2 5] [1 2] [3 5] [2 3] [3 4] [4 5] [1 1])
user> (farey-seq 5 :start [1 3] :end [1 2])へんなところだとできませんけど
([1 3] [2 5] [1 2])
user> (farey-seq 5 :start [1 3] :end [3 4])- pe-73
([1 3] [3 4])
farey-seqを使って解く関数
0 コメント:
コメントを投稿