1079.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
inline long d(long a){if(a<0)return -a;else return a;}
void main()
{long a,b,at,as2,bt,as,bs;int k=0;
double v;
while(1)
{
cin>>a;
if(cin.fail())break;
cin>>b;
v=double(a)/b;
bt=1;
at=(long)v,as2=(long)v+1;
if(k!=0)cout<<endl;
k++;
if(fabs(v-as2)<=fabs(v-at))at=as2;
cout<<at<<'/'<<'1'<<endl;
bs=1;

while(a*bt-at*b!=0)
{bs++;
as=(long)(v*bs),as2=(long)(v*bs)+1;
if(fabs(v*bs-as2)<=fabs(v*bs-as))as=as2;
if(d(a*bs*bt-as*b*bt)<d(at*b*bs-a*bs*bt)){cout<<as<<'/'<<bs<<endl;at=as;bt=bs;}
}

}
}