小数を分数に変換(1)
前回までで、四則演算を含んだ文字列を数値(小数)に変換できた。 で、分数(割り算)で入力したものは分数で出力するのが自然じゃないかと考えた。 そこで、小数を分数に変換することを考える。 精度を保ったままということを考えたら連分数を用いるのがよさそうだ。 処理の流れ 0. x(0) = x、i = 0 1. x(i)を超えない整数をb(i)とし、x(i)-b(i)が0ならば終了 2. x(i+1) = 1/(x(i)-b(i))、i = i + 1 3. i≦100(※)ならば、1へ。でなければ終了 ※は仮の終了条件 これによって、 (1) x = b(0) + 1/(b(1) + 1/(b(2) + ...)) と変換でき、i = nまで計算した結果を X(n) = B(n)/A(n)とするとn≧2のとき以下の式が成り立つ。 (2a) A(0) = 1、A(1) = b(1)、A(n) = b(n)A(n-1) + A(n-2) (2b) B(0) = b(0)、B(1) = b(0)b(1) + 1、B(n) = b(n)B(n-1) + B(n-2) B(n)が十分大きくなったときにも計算を打ち切ることにする。