POJ 1650 -- Integer Approximation

POJ 1650 -- Integer Approximation

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

http://lolita-angel.diandian.com/post/2012-09-23/40039962086

/*

    题目大意：

        读入两个数A(小数位数最大为15位) ，l，在《=l的范围内找到两个整数n,d，使

        abs(a-n*d)最小。

    分析：

        1、普通做法：二分加枚举  O(nlogn)

        2、神奇的追赶法：思路上很好理解

             追赶法实际上那个就是对n和d逐个累加，始终保持着给定的

             关系。。。。（只可意会不可言传什么的）

   */

        

//追赶法：

#include<stdio.h>

#include<math.h>

#define inf 99999999

                     

int main()

{

    int l,n,d,ansn,ansd;

    double a,min,now,kk;

    while(scanf("%lf%d",&a,&l)!=EOF)

    {

        n=1,d=1,min=99999999;

        while(n<=l&&d<=l)

        {

            kk=a-(double)n/d;

            now=fabs(kk);

            if(now<min)

            {

                min=now;

                ansn=n;

                ansd=d;

            }

            if(kk<=0)

                d++;

            else

                n++;

        }

        printf("%d %d\n",ansn,ansd);

    }

    return 0;

}

/*

//二分法

#include<stdio.h>

#include<math.h>

double A;

double Temp,min;

int L,N,D;

int main()

{

    //freopen("1.txt","r",stdin);

    //freopen("3.txt","w",stdout);

    int i,j;

    min=10.0;

    scanf("%lf%d",&A,&L);

    for(i=1;i<=L;i++)

    {

                         

        j=(int)(i/A);

        if(j>L)

            continue;

        Temp=fabs(A-(double)i/(double)j);

        if(Temp<min)

        {

            min=Temp;

            N=i;

            D=j;

        }

        j++;

        if(j>L)

            continue;

        Temp=fabs(A-(double)i/(double)j);

        if(Temp<min)

        {

            min=Temp;

            N=i;

            D=j;

        }

    }

    printf("%d %d\n",N,D);

    return 0;

}

*/

Read full article from 1650 -- Integer Approximation