AOJ2131 Pi is Three

問題リンク Pi is Three

• 概要

実数Rが与えられる。"整数/整数"の形で、円周率πとの誤差がR以下となるような最小の分母とその分子を求めよ。条件を満たす分子が複数ある場合はより誤差の小さいものを答えよ。
0 < R <= 1 (精度は小数点以下7位)

• 解法

分母Dと分子Nをそれぞれ1とし、1ステップ毎にいずれかに+1することでπの値に近付けていきます。
具体的には、N/Dがπより大きかったらDを+1, そうでなければNを+1します。

※誤差がR以下かどうかの判定で
if( ERROR < R + EPS )
というコードを書くと思いますが、EPSの値を10^(-10)程度に小さくとらないとWrong Answerになります。少なくともEPSを10^(-8)にしたらWrong Answerを貰いました。Rの精度が10^(-7)なのでまぁ当然かなと思いました。

• ソース

import java.util.Scanner;

//Pi is Three
public class AOJ2131 {

	void run(){
		Scanner sc = new Scanner(System.in);
		double EPS = 1e-10;
		for(;;){
			double R = sc.nextDouble();
			if(R==0)break;
			int n = 1, d = 1;
			double min = 1<<29;
			int an = 0, ad = 1<<29;
			while(d<=ad){
				double r = Math.PI-n*1.0/d;
				double e = Math.abs(r);
				if(e<R+EPS&&e<min){
					min = e; an = n; ad = d;
				}
				if(r<0)d++;
				else n++;
			}
			System.out.println(an+"/"+ad);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2131().run();
	}
}