Euler : Problem 64

Posted by TAKAIY On 2011年11月26日土曜日 0 コメント
平方根の正則連分数展開のループの繰り返し数の問題です。

問題文にある通りに連分数展開をしていく処理を作りました。





連分数にする手順は、以下の通りです。
初めの数を以下の形にします。

 √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
が再び現れれば、その後は同じものになるのは自明なので、これをつかまえることにします。

また、繰り返しの開始場所は、平方根の場合は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 と 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 コメント:

コメントを投稿