Re: [中學] 分數計算

[oldblackwang (老王)]

※ 引述《xx52002 (冰清影)》之銘言：
: 已知p, q均為整數，且 7/10 < p/q < 11/15，求q的最小值為何？
: Ans: 7
: 一開始直覺是通分換成21/30 < p/q < 22/30
: 該不會要這樣一直擴分下去找中間可以約分成分子分母最小的吧...@@
你的作法會有問題，舉個簡單的例子:
1/3 < p/q < 3/5
答案顯然是 1/2 ，但是你如果用通分方式，找不出來。

你可以用試的，從分母為 2 開始慢慢試所有的最簡分數，
看看哪個符合在 0.7 和 0.7333333...... 之間，
不過這樣很累，而且要是答案稍大，就要花很多時間。

通常是這樣算
取倒數 10/7 > q/p > 15/11
減去最大整數 3/7 > (q-p)/p > 4/11
再取倒數 7/3 < p/(q-p) < 11/4
減去最大整數 1/3 < (3p-2q)/(q-p) < 3/4
這時看出介於 1/3 和 3/4 之間分母最小的分數為 1/2
逆推回去得到 p/q 為 5/7

或是可以這樣
假設 p=7a+11b ， q=10a+15b  (其中 a,b 為正整數)
去猜如何選取 a,b 的值可以約去公因數。

題外話:
令 O(0,0)、A(10,7)、B(15,11)，由 Pick 公式可以算出在三角形 OAB
的內部有兩個格子點，經計算後知道是 (7,5) 和 (11,8)，
所以分母最小就是 q=7 的時候。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.162.98.84
推 xx52002     :感謝您 :)
推 JohnMash    :推
→ jewry2005   :這題p、q有可能是負的嗎?題目說整數
推 xx52002     :唔  我少打個正  是正整數  sorry @@
推 xx52002     :想請問題外話那邊的內部格點7,5 11,8如何算出來呢@@
就從分母 2,3,... 一直代進去找，所以先確定這裡面有格子點，
否則怕是作虛功。
→ jewry2005   :A、B和原點連起來的斜率就是7/10、11/15
※ 編輯: oldblackwang    來自: 1.162.85.12          (05/22 17:03)