小數轉分數程式討論

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

   

例如 x = 27/4,用輾轉相除法,得:

M0
p
q
M1
 
6
27
4
1
M0q
M1R1
 
24
3
--------------
--------------
 
-------------- --------------
M2
R1
R2
M3
 
3
3
1
M2R2
M3R3
 
3
--------------
--------------
 
--------------
--------------
...
R3
R4
...
 
0
...
...
         

容易找書看到定理:

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

(事實上Rn p q H.C.F.)

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

   

例如 x = 6.75 ( = 27/4),和 1 的輾轉相除:

m0
x
1
m1
 
6
6.75
1
1
m0q
m1r1
 
6
0.75
--------------
--------------
 
-------------- --------------
m2
r1
r2
m3
 
3
0.75
0.25
m2R2
m3R3
 
0.75
--------------
--------------
 
--------------
--------------
...
r3
r4
...
 
0
...
...
         

容易看到 mi = Mi q ri = Ri ( i = 0, 1, 2, ..., n)。

特別是 q rn = Rn = 1,因此我們有 q = 1/rn

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

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