小數轉分數程式討論

給定有理數 x，設 x = p/q，其中 p，q 是互質整數，用輾轉相除法，得:

容易找書看到定理:

p, q 互質當且僅當有 n 使做到第 n 次輾轉相除後，R_n = 1

(事實上，R_n 是 p， q 的 H.C.F.)

另一方面，考慮 x 和 1 的輾轉相除 :

容易看到 m_i = M_i 和 q r_i = R_i ( i = 0, 1, 2, ..., n)。

特別是 q r_n = R_n = 1，因此我們有 q = 1/r_n 。

只要不斷地計出 r_i 的倒數，測試它是否 q 就 可以了。(用 "x>0" 鍵構成迴圈)

找到 q 後，乘 x 便計出 p 。