zoj 1601 - 行者无疆 始于足下 - 行走,思考,在路上

zoj 1601

xiaohanyu posted @ Sun, 20 Jun 2010 03:25:03 +0800 in Algorithm with tags ZOJ Algorithm , 2694 readers

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

abc said:
Mon, 03 Jun 2019 17:49:42 +0800

Engineering as a subject combines mathematics, logic and science to find solutions to our daily life problems. Over the last few decades, engineering as a profession has seen vast expansion.

top engineering college in chandigarh

best engineering college in punjab

online cgc

agriculture college in Punjab

mba college in chandigarh

abc said:
Thu, 13 Jun 2019 18:29:48 +0800

Our academic pursuits, along with a range of extracurricular activities, help in honing a child’s skills and ensuring that he/she grows to be a mature and responsible citizen.

top school in greater noida

secure school in greater noida

abc said:
Fri, 05 Jul 2019 18:54:53 +0800

Apple products are revered for its quality, precision and great design. SRSG started its operations as Apple technology partners in the year 1997.
apple reseller in Mumbai
apple authorized service center in delhi
Broadcast consultancy
ipad reseller delhi
macbook air reseller ahmedabad

JessicaJones said:
Thu, 22 Aug 2019 19:14:33 +0800

I really like your writing style, great information, thankyou for posting.

<a href="https://www.godissertationhelp.co.uk/marketing-dissertation-topics/">marketing dissertation topics</a> -
<a href="https://www.godissertationhelp.co.uk/accounting-dissertation-topics/">accounting dissertation topics</a> -
<a href="https://www.godissertationhelp.co.uk/nursing-dissertation-topics/">nursing dissertation topics</a> -
<a href="https://www.godissertationhelp.co.uk/business-dissertation-topics/">business dissertation topics</a> -
<a href="https://www.godissertationhelp.co.uk/management-dissertation-topics/">management dissertation help</a>

JessicaJones said:
Thu, 22 Aug 2019 19:20:00 +0800

Very nice article, I enjoyed reading your post, very nice share, I want to twit this to my followers.

[URL=https://www.godissertationhelp.co.uk/marketing-dissertation-topics/]marketing dissertation topics[/URL] -
[URL=https://www.godissertationhelp.co.uk/accounting-dissertation-topics/]accounting dissertation topics[/URL] -
[URL=https://www.godissertationhelp.co.uk/nursing-dissertation-topics//]nursing dissertation topics[/URL] -
[URL=https://www.godissertationhelp.co.uk/business-dissertation-topics/]business dissertation topics[/URL] -
[URL=https://www.godissertationhelp.co.uk/management-dissertation-topics/]management dissertation help[/URL]

david said:
Wed, 16 Oct 2019 02:58:12 +0800

Manual method of converting a pang to pdf format is tedious so I would suggest you to use <a href="https://fr.altoconvertpngtopdf.com/">fr.altoconvertpngtopdf.com</a>. It has the best conversion time among all of the other converters.

frank said:
Wed, 16 Oct 2019 02:58:40 +0800

Manual method of converting a pang to pdf format is tedious so I would suggest you to use fr.altoconvertpngtopdf.com. It has the best conversion time among all of the other converters.


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee