平方根の正則連分数展開のループの繰り返し数の問題です。
問題文にある通りに連分数展開をしていく処理を作りました。
連分数にする手順は、以下の通りです。
初めの数を以下の形にします。
最初は、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つめからと決っているようですから、それも利用します。
ということで実装したのがこれ。
- 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 コメント:
コメントを投稿