2628.cpp

ZJU ACM 2506 最佳有理逼近算法. ZOJ排名第一的算法.

#include <stdio.h>

struct fraction {
  int p,q;
  fraction(){};
  fraction(int pp, int qq) : p(pp),q(qq) {};
  fraction  operator+ (const fraction& a) { return fraction(p+a.p,q+a.q); }
  fraction& operator+=(const fraction& a) { p+=a.p,q+=a.q; return *this; }
  fraction  operator* (int d) { return fraction(p*d,q*d); }
  operator double() { return (double)p/q; }
  bool valid() { return q!=0; }
  int Euclid() { int r=p%q,d=p/q; p=q; q=r; return d; }
  void output() { printf("%d/%d\n",p,q); }
  double input() { scanf("%d/%d",&q,&p); return (double)q/p; }
  fraction operator()(int l);
};

fraction A;
double dd;

fraction fraction::operator()(int l) {
  fraction R0(1,0), R(0,1), R1;
  bool f=1;
  while (A.valid()) {
    f=!f;
    if ((R1=R*A.Euclid()+R0).q>l) {
      R0+=R*((l-R0.q)/R.q);
      return (f^(double)R+(double)R0<dd)?R0:R;
    }
    R0=R; R=R1;
  }
  return R;
}

int main() {
  int t, l;
  scanf("%d",&t);
  while (t--) { dd=2*A.input(); scanf("%d",&l); A(l).output(); }
  return 0;
}