สมมติว่าเรามีค่าจำนวนเต็มยาวสองค่าสูงสุดและต่ำสุด เราต้องหาเศษส่วนร่วม n/d ให้ min <=d <=max และ |n/d - pi| มีขนาดเล็กที่สุด ที่นี่ pi =3.14159265... และหากมีเศษส่วนมากกว่าหนึ่งตัวที่มีเงื่อนไขนี้ ให้คืนค่าเศษส่วนที่มีตัวส่วนน้อยที่สุด
ดังนั้น หากอินพุตมีค่าต่ำสุด =1 สูงสุด =10 เอาต์พุตจะเป็น 22/7
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- P :=เศษส่วน (5706674932067741 / 1816491048114374) - 3
- a :=0, b :=1, c :=1, d :=1
- farey :=อาร์เรย์ของคู่ มีสองคู่เริ่มต้น (a, b) และ (c, d)
- วนซ้ำสิ่งต่อไปนี้โดยไม่มีเงื่อนไข -
- f :=b + d
- ถ้า f> สูงสุด - ต่ำสุด แล้ว
- ออกมาจากวงจร
- e :=a + c
- ใส่คู่ (e, f) ที่ท้ายแฟรี่
- ถ้า P <ค่าของ (e/f) แล้ว
- c :=e และ d :=f
- ถ้าอย่างนั้น
- a :=e และ b :=f
- p_min :=ชั้นของ (P * ต่ำสุด)
- ในขณะที่ขั้นต่ำ <=สูงสุด ทำ
- c :=0, d :=0
- สำหรับแต่ละคู่ (a, b) ใน farey ทำ
- ถ้าต่ำสุด + b> สูงสุด แล้ว
- ออกมาจากวงจร
- if |(p_min + a)/ (ขั้นต่ำ + b) - P| <|p_min / ขั้นต่ำ - P| แล้ว
- c :=a, d :=b
- ออกมาจากวงจร
- ถ้าต่ำสุด + b> สูงสุด แล้ว
- ถ้า d เหมือนกับ 0 แล้ว
- ออกมาจากวงจร
- p_min :=p_min + c
- o ขั้นต่ำ :=ขั้นต่ำ + d
- o เศษส่วนส่งคืน (p_min + 3 * ต่ำสุด) / ต่ำสุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
4, 27
ผลลัพธ์
22/7
