두 개의 긴 정수 값 최대값과 최소값이 있다고 가정합니다. min <=d <=max가 되는 공통 분수 n/d를 찾아야 합니다. 그리고 |n/d - 파이| 가장 작습니다. 여기서 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> 최대 - 최소인 경우
- 루프에서 나오다
- :=a + c
- 페어리 끝에 쌍(e, f) 삽입
- P <(e/f)의 값이면
- c :=e 및 d :=f
- 그렇지 않으면
- a :=e 및 b :=f
- p_min :=(P * 최소값)의 바닥
- 최소 <=최대, do
- c :=0, d :=0
- 페어리의 각 쌍(a, b)에 대해 다음을 수행합니다.
- 최소값 + 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