ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2131 Pi is Three

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2131


・概要
実数R(0 < R <= 1)が与えられます。

π ー 分子(整数)/分母(整数) < R となる分子/分母を求める問題です。


・解法
上の概要が雑すぎてすみません。
英文がなかなか読めず、苦労しました。(自分の英語力の低さに絶望)

解法ですが、上の公式が成り立つような分子、分母を以下のように探索していきます。
分子D,分母Nとしてπ < N/D のときは D+1、π > N/D のときは N+1して、ループで回していきます。

誤差の判定ですが、きちんとEPSの値を決めないと通らないかもしれません。
ちなみに私は 1e-10 でACをいただきましたが、 その前に 1e-7でやったらWAでした。

あとJavaならMath.PIで円周率が定義されていますが、C++の場合は自分で用意しないといけません。
→ static const double PI = acos(-1.0);

○今更ながら英単語メモ
・numerator :分子
・denominator :分母


ソースコード

#include<iostream>
#include<cmath>
using namespace std;

static const double EPS = 1e-10;
static const double PI = acos(-1.0);

int main(){
   double R;
   while(cin >> R){
      if(R==0.0)break;

      double N = 1.0;
      double D = 1.0; 
      while(1){
	 if(fabs(PI - N/D) < R+EPS)break;
	 else if(PI - N/D > 0)N++;
	 else D++;
      }
      cout << (int)(N) << "/" << (int)(D) << endl;
   }
   return 0;
}