推 anous :感謝各位...每次在這邊發問都能看到很神奇的方法 07/16 00:03
推 sckm160913 :之前有想過畫直線(座標) 找整數點 但方法太廢了XD 07/16 09:13
→ sckm160913 :沒想到還有這方法... 07/16 09:13
※ 引述《anous (阿文)》之銘言：
: 1. 求介於5/8和8/13之間，分母最小且分子分母互質的分數。
: 想請問這類型的問題有沒有比較有系統的處裡方法？
: 我是硬找，雖然最後有找到但覺得沒什麼效率
提供一個不用連分數的作法
Assume 8/13 < x/y < 5/8, and gcd(x,y) = 1
we have 13x - 8y > 0 and 8x - 5y < 0
since x and y is integer,
assume 13x - 8y = k_1 > 0 and 8x-5y = k_2 < 0
where k_1 and k_2 is integer
(13x - 8y)k_2 = k_1 k_2 = (8x - 5y)k_1
=> (13 k_2 - 8 k_1) x - (8 k_2 - 5 k_1) y = 0
=> x = (8 k_2 - 5 k_1), y = (13 k_2 - 8 k_1)
gcd(8 k_2 - 5 k_1, 13 k_2 - 8 k_1) =
gcd(8 k_2 - 5 k_1, 5 k_2 - 3 k_1) =
gcd(3 k_2 - 2 k_1, 5 k_2 - 3 k_1) =
gcd(3 k_2 - 2 k_1, 2 k_2 - 1 k_1) =
gcd(1 k_2 , 2 k_2 - 1 k_1) =
gcd(1 k_2 , 1 k_1) = gcd(x, y) = 1
since k_2 > 0, k_1 < 0, 13 k_2 - 8 k_1 has minimum value when
k_1 = -1, k_2 = 1, that is x/y = (8+5)/(13+8)=13/21
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.23.210