线性的算法,记录最近的分数,最后约分。
#include <stdio.h>

int gdc(int a, int b)
  {

if (a==0)
 {
return b;
}
if (b==0)
 {
return a;
}
return gdc(b, a%b);
}

int main()
  {

int n, d;
int i;
double min;
int mn, md;
int men, med;
double minest;
int temp;
int pub;
double t1, t2;
while (scanf("%d%d", &n, &d) != EOF)
 {
minest = 1;
pub = gdc(n, d);
n = n/pub;
d = d/pub;
for (i=1; i<=32767; i++)
 {
min = 1;
temp = (int)((double)i * (double)n / (double)d);
pub = gdc(i, temp);
if (temp/pub!=n || i/pub!=d)
 {
if ((double)n/(double)d-(double)temp/(double)i < (double)(temp+1)/(double)i-(double)n/(double)d)
 {
min = (double)temp/(double)i;
mn = temp;
md = i;
}
else
 {
min = (double)(temp+1)/(double)i;
mn = temp+1;
md = i;
}
}
t1 = min-(double)n/(double)d>0 ? min-(double)n/(double)d:(double)n/(double)d-min;
t2 = minest-(double)n/(double)d>0 ? minest-(double)n/(double)d:(double)n/(double)d-minest;
if (t1<t2)
 {
minest = min;
men = mn;
med = md;
}
}
pub = gdc(men, med);
printf("%d %d\n", men/pub, med/pub);
}
return 0;
}

|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|