1218.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
int main(){
  //ifstream cin("in.txt");
  long double a,b,r,p;
  int i,j,u,c=0;
  while(cin>>a>>b){
	if(c++>0) cout<<endl;
    r=a/b; p=1; u=int(b);
	for(i=1;i<=u;i++){
       a=r*i;
	   a=(int)a;
	   b=(int)a+1;
	   if(fabs(b/i-r)<=fabs(a/i-r)){
		   if(fabs(b/i-r)<p){
              j=int(b);
			  cout<<j<<"/"<<i<<endl;
			  p=fabs(b/i-r);
		   }
	   }
	   else{
		   if(fabs(a/i-r)<p){
              j=int(a);
			  cout<<j<<"/"<<i<<endl;
			  p=fabs(a/i-r);
		   }
	   }
	   if(p==0) break;
	}
	//cout<<endl;
  }
}