ファレイ数列の問題です。
Wikipediaの解説を見たら、解きかたは一瞬でわかります。
この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。
ということは、問題の場合、2/5と3/8 について、
- 中間数Mを求める。
- 中間数Mの分母が1000000を超えたら、1つまえのものが答
- そうでなければ、Mと3/8について同様のことを続ける。
この通りの実装でございます。
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/8 | |
| ;; "Elapsed time: 151.987474 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 pe-71 [base left lmt] | |
| (let [[base-n base-d] base | |
| [left-n left-d] left] | |
| (loop [left-num left-n, left-den left-d] | |
| (let [[new-num new-den] (frac-reduce (+ base-n left-num) (+ base-d left-den))] | |
| (if (> new-den lmt) | |
| (/ left-num left-den) | |
| (recur new-num new-den)))))) | |
※ この計算で分数を分数のまま扱うか、別形式を使うか悩んだのですが、別形式にしました。
特に意味はありません。 [<分子> <分母>]です。
- my-numerator
- my-denominator
整数でも値が出るようにしたnumeratorとdenominator
- frac-reduce
この計算では、中間数を約分する必要があるのですが、clojureは分数が使えて約分もしてくれるので、これを使って約分した値を作っています。
- pe-71
上に書いたとおりの実装です。
2 コメント:
この問題の私の解法
ファレイ数列の性質よりコードはＰｒｏｌｏｇ言語で
X is (1000*1000-5)//7,Ans is X*3+2.
Ａｎｓが答えです。
isはほかの言語でいうところのＸ＝式
という意味です。
コメントありがとうございます。 レスが遅くなってすみません。
残念ながら僕にはどうしてこの方法で答えがでるのかわかりませんでした。
clojureだと
(+ 2 (* 3 (quot (- (* 1000 1000) 5) 7)))
こんな感じですかね。
コメントを投稿