กำหนดค่า maximum และ minimum เป็นจำนวนเต็มขนาดใหญ่ หาเศษส่วนร่วม n/d ที่ min <= d <= max และ |n/d - pi| น้อยที่สุด pi = 3.14159265... ถ้ามีหลายเศษส่วน ให้คืนเศษส่วนที่มีตัวส่วนน้อยที่สุด
เช่น minimum = 1, maximum = 10 ผลลัพธ์คือ 22/7
วิธีแก้ปัญหา
- P := เศษส่วน (5706674932067741 / 1816491048114374) - 3
- a := 0, b := 1, c := 1, d := 1
- farey := array ของคู่ เริ่มต้นมี (a,b) และ (c,d)
- ลูปไม่มีเงื่อนไข
- f := b + d
- ถ้า f > maximum - minimum: break
- e := a + c
- เพิ่มคู่ (e,f) ลง farey
- ถ้า P < e/f: c:=e, d:=f มิฉะนั้น a:=e, b:=f
- p_min := floor(P * minimum)
- while minimum <= maximum
- c := 0, d := 0
- สำหรับแต่ละคู่ (a,b) ใน farey
- ถ้า minimum + b > maximum: break
- ถ้า |(p_min+a)/(minimum+b) - P| < |p_min/minimum - P|: c:=a, d:=b; break
- ถ้า d == 0: break
- p_min := p_min + c
- minimum := minimum + d
- คืนค่าเศษส่วน (p_min + 3*minimum) / minimum
ตัวอย่างโค้ด
from fractions import Fraction
def solve(minimum, maximum):
P = Fraction(5706674932067741, 1816491048114374) - 3
a, b, c, d = 0, 1, 1, 1
farey = [(a,b),(c,d)]
while True:
f = b + d
if f > maximum - minimum:
break
e = a + c
farey.append((e, f))
if P < Fraction(e, f):
c, d = e, f
else:
a, b = e, f
p_min = int(P * minimum)
while minimum <= maximum:
c, d = 0, 0
for a, b in farey:
if minimum + b > maximum:
break
if abs(Fraction(p_min + a, minimum + b).real - P) < abs(Fraction(p_min, minimum).real - P):
c, d = a, b
break
if d == 0:
break
p_min += c
minimum += d
return ("{}/{}".format(p_min + 3 * minimum, minimum))
minimum = 1
maximum = 10
print(solve(minimum, maximum))Input
4, 27
Output
22/7
