acm pku1650 Integer Approximation

Integer Approximation
Time Limit:1000MS  Memory Limit:65536K
Total Submit:1542 Accepted:427

Description
The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius R he suggests to use formula like R * R * 355 / 113, which is in fact surprisingly accurate. The value of 355 / 113 ≈ 3.141593 is approximating the value of PI with the absolute error of only about 2*10^-7. You are to find the best integer approximation of a given floating-point number A within a given integer limit L. That is, to find such two integers N and D (1 <= N, D <= L) that the value of absolute error |A - N / D| is minimal.

Input
The first line of input contains a floating-point number A (0.1 <= A < 10) with the precision of up to 15 decimal digits. The second line contains the integer limit L. (1 <= L <= 100000).

Output
Output file must contain two integers, N and D, separated by space.

Sample Input

3.14159265358979
10000

Sample Output

355 113

Source
, Far-Eastern Subregion

典型的迭代。。。想到用这方法，不太会表达。用同学的代码交上。。。

Memory:132K  Time:31MS

#include 
#include 
#define INF 1000000
using namespace std;

double A;
int L,N,D;

int main()
{
 cin>>A>>L;

 double front = 1.0,rear = 1.0;

 N = INF; D = 1;

 while(front <= L && rear <= L){
  if(fabs(A - front/rear) < fabs(A - N*1.0/D*1.0)){
   N = front; D = rear;
  }

  if(front/rear <= A)  front++;
  else if(front/rear >= A)rear++;
 }

 cout<