推 oldblackwang:長知識了~~ 05/22 18:54
→ Sfly :數論上稱為 Farey Sequence 05/22 18:56
※ 引述《xx52002 (冰清影)》之銘言：
: 已知p, q均為整數，且 7/10 < p/q < 11/15，求q的最小值為何？
: Ans: 7
: 一開始直覺是通分換成21/30 < p/q < 22/30
: 該不會要這樣一直擴分下去找中間可以約分成分子分母最小的吧...@@
其實可以用stern-brocot tree去做
就用0/1 ,1/1 開始作Mediant
然後看這個新分數是不是介於7/10與11/15
如果是 這個分數就是答案
如果這個分數 一個是 parent 一個是child
則答案為 原本的兩個分數的Mediant
這時就可以從 連分數來看
7/10 = [0;1,2,3]
11/15 = [0;1,2,1,3]
所以我們找 [0;1,2,2] = 5/7 -->答案
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.240.128.87