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
31
32
33
34
35
36
37
38
39
|
#include <stdio.h>
int gcd(int x, int y)
{
if (x == 0)
return y;
else
return gcd(y%x, x);
}
void imm_left(int numer, int denom, int max_denom, int *nu, int *de)
{
/* nu/de < numer/denom
* => nu < numer*de/denom
*/
int res_nu = 0, res_de = 1;
int i;
for (i = 2; i <= max_denom; i++) {
if (i == denom)
continue;
int t = numer * i / denom;
/* t/i > res_nu/res_de */
if (gcd(t, i) != 1)
continue;
if (t * res_de > i * res_nu) {
res_nu = t;
res_de = i;
}
}
*nu = res_nu;
*de = res_de;
}
int main()
{
int nu, de;
imm_left(3, 7, 1000000, &nu, &de);
printf("%d/%d\n", nu, de);
}
|
