小数的分数逼近，题目的思路是挺简单的，假设A=N/D，那么N=[D*A]或者N=[D*A]+1，按照这个公式对D进行枚举，不断更新最佳值即可。下面是我的WA的代码：

#include <stdio.h>
#include <math.h>

int main(int argc, char *argv[])
{
    double A;
    int L;
    int N, D;
    double delta;
    double min;
    
    while (scanf("%lf%d", &A, &L) != EOF)
    {
        min = 10 * L;

        int i;
        
        for (i = 0; i * A <= L && i <= L; ++i)
        {
            int temp_D = i;
            int N1 = (int) i * A;
            double delta1 = fabs(A - (double) N1 / i);

            int N2 = (int) i * A + 1;
            double delta2 = fabs(A - (double)N2 / i);

            if (delta1 < delta2 && delta1 < min)
            {
                D = temp_D;
                N = N1;
                min = delta1;
            }
            else if(delta1 > delta2 && delta2 < min)
            {
                D = temp_D;
                N = N2;
                min = delta2;
            }
        }

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

由于没有测试数据，所以也不知道这道题目究竟错在哪里。我也找来了AC的代码：

#include<stdio.h>
#include<math.h>

int main(void)
{
    double min;
    double A;
    long i;
    long j;
    long N;
    long D;
    long L;
    long pd;
    long pn;

    while (scanf("%lf %ld", &A, &L) != EOF)
    {
        pn = -999999;
        pd = 1;
        min = 9999999;

        for (D=1; D<=L; ++D)
        {
            N = (long)(D * A);
   
            if (N > L)
            {
                break;
            }
   
            for (i=0; i<=1; ++i)
            {
                if (fabs(min - A) > fabs((double)(N+i)/(double)D - A))
                {
                    pn = N+i;
                    pd = D;
                    min = (double)(N+i)/(double)D;
                }
            }
        }
  
        if (pn == -999999)
        {
            for (D=1; D<=L; ++D)
            {
                for (N=1; N<=L; ++N)
                {
                    if (fabs(min - A) > fabs((double)N/(double)D - A))
                    {
                        pn = N;
                        pd = D;
                        min = (double)N/(double)D;
                    }
                }
            }
        }
  
        printf("%ld %ld\n", pn, pd);
    }

    return 0;
}

但是这段AC的代码在输入3.33 9的时候给出的答案是10 3，显然是错误的答案。困惑中。求高人指点。

• Relative Posts