0905 minimal distance to pi

원문: https://www.hackerrank.com/challenges/minimal-distance-to-pi
참조한 블로그 : www.libragold.com

임의의 무리수에 가장 근접한 유리수를 찾는 문제.
단, 유리수를 \(\frac{p}{q}\)로 나타냈을 때, \(q\)가 가질 수 있는 범위를 한정한다.

일단, Farey sequence[1]를 알면 좋다.
위키피디아에 들어가서 보면 정렬된 그림이 있는데, 이해하기 좋다.
Farey sequence는 수열을 얻는 과정이 쉽고, 근사하는 속도가 매우 빠르다.

본 문제는 \(\pi-3\)에 근사하는 유리수를 찾지만, 임의의 수(\(\in \Q\))에 적용 가능하다.
일단 \(r(q)\)를 ‘\(\pi-3\)에 가장 근접하는 유리수 중 분모가 q이하인 것’을 뜻한다고 하자. 아래는 예시.
\(r(4) = 1/4 \)
\(r(8) = 1/7\) (\(\because 1/7\)이 \(1/8\)보다 \(\pi-3\)에 더 가깝다. \(8/57\) 이전까지 \(1/7\)의 오차가 가장 작다. )
\(r\)의 argument로 (inclusive) range를 허용하면 위는 \(r(1,4), r(1,8)\)이 된다.
구하려고 하는 것은 임의의 \(a\lt b \in \N\)에서 \(r(a,b)\)이다.

#cont.