Euler : Problem 71

Posted by YpsilonTAKAI On 2011年12月9日金曜日 2 コメント


ファレイ数列の問題です。

Wikipediaの解説を見たら、解きかたは一瞬でわかります。





この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。

ということは、問題の場合、2/5と3/8 について、
 - 中間数Mを求める。
 - 中間数Mの分母が1000000を超えたら、1つまえのものが答
 - そうでなければ、Mと3/8について同様のことを続ける。

この通りの実装でございます。



※ この計算で分数を分数のまま扱うか、別形式を使うか悩んだのですが、別形式にしました。
  特に意味はありません。 [<分子> <分母>]です。

- my-numerator
- my-denominator
 整数でも値が出るようにしたnumeratorとdenominator

- frac-reduce
 この計算では、中間数を約分する必要があるのですが、clojureは分数が使えて約分もしてくれるので、これを使って約分した値を作っています。

- pe-71
 上に書いたとおりの実装です。

2 コメント:

sina さんのコメント...

この問題の私の解法
ファレイ数列の性質よりコードはProlog言語で
X is (1000*1000-5)//7,Ans is X*3+2.
Ansが答えです。
isはほかの言語でいうところのX=式
という意味です。

YpsilonTAKAI さんのコメント...

コメントありがとうございます。 レスが遅くなってすみません。
残念ながら僕にはどうしてこの方法で答えがでるのかわかりませんでした。

clojureだと
(+ 2 (* 3 (quot (- (* 1000 1000) 5) 7)))
こんな感じですかね。

コメントを投稿