Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 최솟값과 최댓값 사이에서 원주율에 가장 가까운 분수 찾기

문제 개요

두 개의 큰 정수 값 최댓값(maximum)과 최솟값(minimum)이 주어져 있다고 가정해 봅시다. 우리가 찾아야 하는 것은 다음 조건을 모두 만족하는 분수 n/d입니다.

  • 분모 d가 min ≤ d ≤ max 범위 안에 있어야 합니다.
  • |n/d − π|의 값이 최소가 되어야 합니다. (여기서 π = 3.14159265...)

조건을 만족하는 분수가 여러 개라면, 그중 분모가 가장 작은 분수를 반환해야 합니다.

예를 들어 minimum = 1, maximum = 10이 주어지면 결과는 22/7이 됩니다.

해결 접근 방법

이 문제는 파레이 수열(Farey Sequence)의 성질을 이용하면 효율적으로 풀 수 있습니다. 서로 인접한 두 분수 a/b와 c/d 사이에는 항상 중간분수(mediant)인 (a+c)/(b+d)가 존재하며, 이 성질을 반복적으로 적용하면 목표 값에 점점 가까워지는 유리수 근사를 만들어 낼 수 있습니다.

구체적인 해결 단계는 다음과 같습니다.

  1. π의 소수 부분을 P로 정의합니다. 즉, P := Fraction(5706674932067741 / 1816491048114374) − 3
  2. a := 0, b := 1, c := 1, d := 1로 초기화하고, (a, b)와 (c, d) 두 쌍을 담은 배열 farey를 생성합니다.
  3. 다음 과정을 무한히 반복합니다.
    • f := b + d
    • f가 maximum − minimum보다 크면 루프를 빠져나옵니다.
    • e := a + c를 계산하고, (e, f)를 farey의 끝에 추가합니다.
    • P < e/f이면 c := e, d := f로 갱신하고, 그렇지 않으면 a := e, b := f로 갱신합니다.
  4. p_min := ⌊P × minimum⌋로 설정합니다.
  5. minimum ≤ maximum인 동안 다음을 반복합니다.
    • c := 0, d := 0으로 초기화합니다.
    • farey의 각 쌍 (a, b)에 대해 다음을 검사합니다.
      • minimum + b > maximum이면 반복을 중단합니다.
      • |（p_min + a)/(minimum + b) − P| < |p_min/minimum − P|이면 c := a, d := b로 설정한 뒤 반복을 중단합니다.
    • d가 0이면 전체 루프를 종료합니다.
    • p_min += c, minimum += d로 갱신합니다.
  6. 최종 결과로 분수 (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))

입력 및 출력

입력: minimum = 1, maximum = 10

출력:

22/7

동작 원리 요약

이 알고리즘의 핵심은 다음 세 가지입니다.

  • 중간분수 생성: 인접한 두 분수의 분자와 분모를 각각 더해 새로운 후보 분수를 만듭니다. 이렇게 생성된 분수는 항상 원래 두 분수 사이에 위치하므로, 목표 값(π의 소수 부분)을 점차 좁혀 가며 접근할 수 있습니다.
  • 범위 제한: 분모가 maximum − minimum을 초과하지 않도록 관리하여, 실제로 사용 가능한 분모 범위 안에서만 후보를 생성합니다.
  • 탐욕적 개선: 현재 근사값보다 오차가 줄어드는 후보를 발견할 때마다 분자(p_min)와 분모(minimum)를 갱신해 최적의 분수로 수렴시킵니다.

그 결과, 주어진 분모 범위 안에서 π에 가장 가까우면서 분모가 가장 작은 분수인 22/7을 얻게 됩니다. 참고로 22/7은 고대부터 널리 알려진 π의 대표적인 근사값으로, 아르키메데스도 이 값을 활용했습니다.