最新消息:点击查看大S的省钱秘笈

POJ 1650 Integer Approximation C++版

POJ题解 Slyar 1635浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

暴力枚举

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

Slyar:求出在L范围内的两个数,使得它们相除后减去A的结果的绝对值最小。暴力枚举就好了,这题很恶心…

#include 
#include 

using namespace std;

int main()
{
    double a, min, temp;
    int i, j, l, n, d;
    
    cin >> a >> l;
    n = d = 1;
    min = 20;

    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;
        }
    }
    
    cout << n << " " << d << endl;
    
    //system("pause");
    return 0;
}

转载请注明:Slyar Home » POJ 1650 Integer Approximation C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址