Problem 71 - のてすきあ　− 完全独習非プログラマー −

分母が1,000,000までの既約分数を小さい順に並べた時に、3/7の1つ前に来る分数（3/7より小さく、3/7に最も近い数）はなにか

　まず思いつくのは、全ての分数を列挙してsortして…というナイーブな手法だが、恐らくその方法では時間が掛かり過ぎる。もう少し論理的にアプローチできないか。そこで以下のように考えた。

求めるべき分数を $\displaystyle \frac{q}{p}$ とすると、問題は

$\displaystyle \delta = \frac{3}{7} - \frac{q}{p}$ を最小にする $p, q$ を求めることと同義である。 $p$ を固定したときの $q$ には以下の制約が課せられる。

$\displaystyle \frac{q}{p} \lt \frac{3}{7} \lt \frac {q + 1}{p}$

ここから

$\displaystyle 0 \lt \left(\frac{3}{7} - \frac{q}{p} \right) = \delta \lt \frac{1}{p}$

このことを利用して、3/7 - 1/1000000, 3/7 - 1/999999, 3/7 - 1/999998, ... と3/7 - 1/p の候補を小さい順番に評価していき、約分の結果一番最初に分母が1,000,000より小さくなる数を探し出した。数学的な正当性はもっと厳密に示す必要があるが、正解に辿り着くのは間違いない。

割と良いアイデアだったのではないか☆