小数的分数逼近,题目的思路是挺简单的,假设 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 ,显然是错误的答案。困惑中。求高人指点。