平方根の正則連分数展開のループの繰り返し数の問題です。
問題文にある通りに連分数展開をしていく処理を作りました。
連分数にする手順は、以下の通りです。
初めの数を以下の形にします。
最初は、M=0、N=1になります。
これを帯分数にします。
になります。真分数の部分を連分数にするために逆数にします。
分母にある分数を有理化します。
しかし、上記の手順の
- int-floor
foorの整数版
以下2つは
√X + M
-------
N
- inverse-rationalize
逆数を取って有理化する関数。 計算したものを
√X + new-M
------------
new-N
問題文にある通りに連分数展開をしていく処理を作りました。
連分数にする手順は、以下の通りです。
初めの数を以下の形にします。
√X + M
--------
N
最初は、M=0、N=1になります。
これを帯分数にします。
√X + M'
a + ---------
N
になります。真分数の部分を連分数にするために逆数にします。
1
a + -----------
N
---------
√X + M'
分母にある分数を有理化します。
1
a + ----------
√X + O
--------
P
これで、1段階終了です。そして、この、分母にある
√X + O
--------
P
を初めの手順に戻して計算を進めることで、連分数に展開していくことができます。
帯分数にして、整数部分を取り出す -> 残りの部分の逆数を採って有理化する
という操作を繰り返すという手順になります。
この手順で出てくるaを並べたものが [4;1,3,1,8,.....] という数列になります。
これで、数列を取り出すことができるのですが、数列を作ってしまっては、問題を解くのが困難です。 たとえば、1,2,1,2 という列が出たときに、このまま1,2が交互に現れるのか、1,2,1,2,3 の繰り返しになるのかはわかりません。
しかし、上記の手順の
√X + M
--------
N
--------
N
が再び現れれば、その後は同じものになるのは自明なので、これをつかまえることにします。
また、繰り返しの開始場所は、平方根の場合は2つめからと決っているようですから、それも利用します。
ということで実装したのがこれ。
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 64 : 2011/11/25 | |
| ;; "Elapsed time: 755.433163 msecs" | |
| ;; (sqrt X)+M | |
| ;; ----------- | |
| ;; N | |
| (defn int-floor [n] | |
| (Math/round (Math/floor n))) | |
| (defn inverse-rationalize [X M N] | |
| (let [new-N (/ (- X (* M M)) N) | |
| new-M (- M)] | |
| [new-M new-N])) | |
| (defn make-proper [X M N] | |
| (let [numerator (+ (Math/sqrt X) M) | |
| a (int-floor (/ numerator N)) | |
| new-M (- M (* a N))] | |
| [a new-M])) | |
| ;; not used | |
| (defn get-continued-fraction-list | |
| "Get continued fraction list of Sqrt X" | |
| ([X] (get-continued-fraction-list X 0 1)) | |
| ([X M N] | |
| (let [[a prop-M] (make-proper X M N) | |
| [new-M new-N] (inverse-rationalize X prop-M N)] | |
| (lazy-seq | |
| (cons a | |
| (get-continued-fraction-list X new-M new-N)))))) | |
| (defn get-continued-fraction-args | |
| "Get continued fraction parms of Sqrt X" | |
| ([X] (get-continued-fraction-args X 0 1)) | |
| ([X M N] | |
| (let [[a prop-M] (make-proper X M N) | |
| [new-M new-N] (inverse-rationalize X prop-M N)] | |
| (lazy-seq | |
| (cons [new-M new-N] | |
| (get-continued-fraction-args X new-M new-N)))))) | |
| (defn count-continued-flaction-loop [X] | |
| (let [continued-flaction-args (drop 1 (get-continued-fraction-args X)) | |
| key (first continued-flaction-args)] | |
| (loop [n 1 | |
| cfa (next continued-flaction-args)] | |
| (if (= (first cfa) key) | |
| n | |
| (recur (inc n) (next cfa)))))) | |
| (defn pe-64 [n] | |
| (count | |
| (filter odd? | |
| (map count-continued-flaction-loop | |
| (filter (complement square?) (range 1 (inc n))))))) |
- int-floor
foorの整数版
以下2つは
√X + M
-------
N
の形の数についての操作関数
- inverse-rationalize
逆数を取って有理化する関数。 計算したものを
√X + new-M
------------
new-N
としたときの new-M と new-N を返します。
- make-proper
帯分数します。 帯分数を
√X + new-M
a + ------------
N
a + ------------
N
としたときの、a と new-M を返します。
- get-continued-fraction-list
引数の平方根を連分数にしたときのaのリストを返します。
2 を与えると、 (1 2 2 2 2 2 ....) が得られます。
解答には使ってません。
- get-continued-fraction-args
引数の平方根を連分数にしたときのMとNのリストを返します。
23 を与えると、([0 1][4 7][3 2][3 7][4 1][4 7]....) が得られます。
- count-continued-flaction-loop
引数の平方根の繰り返しの数を数えます。
get-continued-fraction-args で作ったリストの2番目のペアが再び表われるまでの数を
数えています。 それだけなのに、仰々しくて美しくないですね。 だめだな。
- pe-64
範囲の中の平方数(square?)でない数について、平方数の繰り返しの数を数えて、
奇数のものだけ取り出して数えています。
基本の関数2つの理屈を考えるのに時間が掛ってしまった。
問題の例を見てそのまま作ろうとしてしまったのが敗因。 ちゃんと紙に書いたらすぐできた。
0 コメント:
コメントを投稿