📄 usaco 2_1_2 ordered fractions 题解_leokan的blog.mht
字号:
A=20
href=3D"http://hi.baidu.com/leokan/profile">=B8=F6=C8=CB=B5=B5=B0=B8</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/friends">=BA=C3=D3=D1</A> =
<SPAN>|</SPAN><A=20
href=3D"http://hi.baidu.com/leokan/modify/spbasic/0">=C9=E8=D6=C3</A> =
</DIV></DIV>
<DIV class=3Dstage>
<DIV class=3Dstagepad>
<DIV style=3D"WIDTH: 100%">
<TABLE class=3Dmodth cellSpacing=3D0 cellPadding=3D0 width=3D"100%" =
border=3D0>
<TBODY>
<TR>
<TD class=3Dmodtl width=3D7> </TD>
<TD class=3Dmodtc noWrap>
<DIV class=3Dmodhead><SPAN =
class=3Dmodtit>=B2=E9=BF=B4=CE=C4=D5=C2</SPAN></DIV></TD>
<TD class=3Dmodtc noWrap align=3Dright>
<DIV class=3Dmodopt><A class=3Dmodact=20
href=3D"http://hi.baidu.com/leokan/creat/blog/"><IMG=20
src=3D"http://img.baidu.com/hi/img/ico_postnew.gif" =
align=3DabsMiddle=20
border=3D0>=D0=B4=D0=C2=CE=C4=D5=C2</A></DIV></TD>
<TD class=3Dmodtr width=3D7> </TD></TR></TBODY></TABLE>
<DIV class=3Dmodbox id=3Dm_blog>
<DIV class=3Dtit>USACO 2.1.2 Ordered Fractions =CC=E2=BD=E2</DIV>
<DIV class=3Ddate>2008=C4=EA01=D4=C227=C8=D5 =D0=C7=C6=DA=C8=D5 =
22:33</DIV>
<TABLE style=3D"TABLE-LAYOUT: fixed">
<TBODY>
<TR>
<TD>
<DIV class=3Dcnt>
<H2>USACO 2.1.2 Ordered Fractions</H2>
<DIV class=3Dt_msgfont>Ordered Fractions<BR><BR>Consider the set =
of all=20
reduced fractions between 0 and 1 inclusive with denominators less =
than or=20
equal to N. <BR><BR>Here is the set when N =3D 5: <BR><BR>0/1 1/5 =
1/4 1/3=20
2/5 1/2 3/5 2/3 3/4 4/5 1/1<BR><BR>Write a program that, given an =
integer=20
N between 1 and 160 inclusive, prints the fractions in order of =
increasing=20
magnitude. <BR><BR>PROGRAM NAME: frac1<BR>INPUT FORMAT<BR>One line =
with a=20
single integer N. <BR>SAMPLE INPUT (file frac1.in) =
<BR>5<BR><BR>OUTPUT=20
FORMAT<BR>One fraction per line, sorted in order of magnitude. =
<BR>SAMPLE=20
OUTPUT (file=20
=
frac1.out)<BR>0/1<BR>1/5<BR>1/4<BR>1/3<BR>2/5<BR>1/2<BR>3/5<BR>2/3<BR>3/4=
<BR>4/5<BR>1/1<BR><BR><BR><BR>Ordered=20
Fractions<BR><BR>=CB=B3=D0=F2=B5=C4<SPAN class=3Dt_tag=20
=
href=3D"tag.php?name=3D%B7%D6%CA%FD">=B7=D6=CA=FD</SPAN><BR><BR>=D2=EB =
by tim=20
=
green<BR><BR><BR>=CA=E4=C8=EB=D2=BB=B8=F6=D7=D4=C8=BB=CA=FDN=A1=A1<BR>=C7=
=EB=D0=B4=D2=BB=B8=F6=B3=CC=D0=F2=C0=B4=D4=F6=D0=F2=CA=E4=B3=F6=B7=D6=C4=B8=
=D0=A1=D3=DA=B5=C8=D3=DAN=B5=C4=BC=C8=D4=BC=D5=E6=B7=D6=CA=FD<BR><BR>PROG=
RAM=20
NAME: frac1<BR><BR>INPUT =
FORMAT<BR>=B5=A5=B6=C0=B5=C4=D2=BB=D0=D0=A1=A1=D2=BB=B8=F6=D7=D4=C8=BB=CA=
=FDN(1..160)<BR><BR>SAMPLE=20
INPUT (file frac1.in) <BR>5<BR><BR>OUTPUT=20
=
FORMAT<BR>=C3=BF=B8=F6=B7=D6=CA=FD=B5=A5=B6=C0=D5=BC=D2=BB=D0=D0<BR><BR>S=
AMPLE OUTPUT (file=20
=
frac1.out)<BR>0/1<BR>1/5<BR>1/4<BR>1/3<BR>2/5<BR>1/2<BR>3/5<BR>2/3<BR>3/4=
<BR>4/5<BR>1/1</DIV>
<P></P>
<HR>
<P></P>
<P><STRONG>USACO 2.1.2 Ordered =
Fractions<BR>=CC=E1=BD=BB=B4=CE=CA=FD=A3=BA1=B4=CE</STRONG></P>
<P><STRONG>=B7=BD=B7=A81=A3=BA</STRONG></P>
=
<P><STRONG>=CF=C8=CA=E4=B3=F6=D2=BB=B8=F60/1=C8=BB=BA=F3=BD=AB=CB=F9=D3=D0=
=B7=D6=C4=B8=B5=C4=B7=D6=D7=D3=C9=E8=CE=AA1=A3=AC=B4=E6=C8=EB=D2=BB=B8=F6=
=CA=FD=D7=E9=D6=D0=A3=AC=D1=B0=D5=D2=CA=FD=D7=E9=D6=D0=D7=EE=D0=A1=B5=C4=C4=
=C7=B8=F6=CA=FD=BD=AB=CB=FC=CA=E4=B3=F6=A3=AC=C8=BB=BA=F3=BD=AB=D5=E2=B8=F6=
=B7=D6=CA=BD=B5=C4=B7=D6=D7=D3=CE=AA=B5=BD=CF=C2=D2=BB=B8=F6=D3=EB=B7=D6=C4=
=B8=BB=A5=D6=CA=B5=C4=B7=D6=D7=D3=A1=A3=D0=A1=D3=DA1=B5=C4=D7=EE=B4=F3=B5=
=C4=CA=FD=BE=CD=CA=C7n-1/n=C1=CB=A3=AC=CB=F9=D2=D4=BF=C9=D2=D4=D3=C3=D5=E2=
=B8=F6=D7=F7=CE=AAwhile=D1=AD=BB=B7=B5=C4=BD=E1=CA=F8=CC=F5=BC=FE=A1=A3=D7=
=EE=BA=F3=CA=E4=B3=F61/1.</STRONG></P>
=
<P><STRONG>{<BR>TASK:frac1<BR>LANG:PASCAL<BR>}<BR>{$D-,L-,Y-,R-,S-,I-,Q-}=
<BR>program=20
frac1;<BR>const maxn=3D160;<BR>var<BR> =20
fraction:array[1..maxn] of integer;<BR> =20
prime:array[0..maxn] of integer;<BR> =20
textt:array[1..500000] of char;<BR> =20
n:integer;<BR>procedure init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'frac1.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR> for=20
i:=3D1 to n do<BR> =20
fraction[i]:=3D1;<BR>end;<BR>procedure=20
initprime;<BR>var<BR> =
i,j:integer;<BR> =20
isprime:array[2..maxn] of boolean;<BR>begin<BR> =20
fillchar(isprime,sizeof(isprime),true);<BR> for =
i:=3D2 to=20
trunc(sqrt(n)) do<BR> if =
isprime[i]=20
=
then<BR>  =
;=20
for j:=3D2 to (n div i)=20
=
do<BR> &=
nbsp; =20
isprime[j*i]:=3Dfalse;<BR> =20
fillchar(prime,sizeof(prime),0);<BR> for i:=3D2 =
to n=20
do<BR> if isprime[i]=20
=
then<BR>  =
;=20
=
begin<BR> &nbs=
p; =20
=
inc(prime[0]);<BR> &=
nbsp; =20
=
prime[prime[0]]:=3Di;<BR> =
=20
end;<BR>end;<BR>function=20
mutual_prime(x,y:integer):boolean;<BR>var<BR> =20
i:integer;<BR>begin<BR> if x=3D1 then=20
exit(false);<BR> for i:=3D1 to prime[0]=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
if prime[i]>x then=20
=
exit(true);<BR> &nbs=
p; =20
if (x mod prime[i]=3D0)and(y mod prime[i]=3D0)=20
=
then<BR>  =
; =20
exit(false);<BR> =20
end;<BR> exit(true);<BR>end;<BR>procedure=20
work;<BR>var<BR> =
i,now:integer;<BR> =20
min:real;<BR>begin<BR> =20
assign(output,'frac1.out');rewrite(output);<BR> =20
settextbuf(output,textt,sizeof(textt));<BR> =20
writeln('0/1');<BR> =
min:=3D0;<BR> while=20
fraction[n]<n do<BR> =20
=
begin<BR> &nbs=
p;=20
=
min:=3D1;<BR> =
=20
for i:=3D1 to n=20
=
do<BR> &=
nbsp; =20
if fraction[i]/i<min=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
min:=3Dfraction[i]/i;<BR> =
&=
nbsp; =20
=
now:=3Di;<BR> =
=20
=
end;<BR>  =
;=20
=
writeln(fraction[now],'/',now);<BR> &n=
bsp; =20
=
inc(fraction[now]);<BR> &n=
bsp; =20
while not mutual_prime(fraction[now],now) do=20
inc(fraction[now]);<BR> =20
end;<BR> writeln('1/1');<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> initprime;<BR> =20
work;<BR>end.</STRONG></P>
<P><STRONG>=B7=BD=B7=A82=A3=BA</STRONG></P>
=
<P><STRONG>=D3=D6=CA=D4=C1=CB=CA=D4usaco=B7=D6=CE=F6=D6=D0=CB=B5=C3=F7=B5=
=C4=C4=C7=D6=D6=B7=D6=D2=B1=B7=A8=A1=A3=D2=D1=D6=AAn1/d1<n1+n2/d1+d2&l=
t;n2/d2,=D5=E2=D1=F9=BE=CD=BF=C9=D2=D4=D3=C3=B7=D6=D2=B1=B7=A8=BD=E2=BE=F6=
=C1=CB=A3=AC=B2=BB=B6=CF=B5=DD=B9=E9=A3=AC=D6=D5=D6=B9=CC=F5=BC=FE=CA=C7=B7=
=D6=C4=B8=A3=A8d1+d2)=B4=F3=D3=DA=CC=E2=C4=BF=D2=AA=C7=F3=B5=C4=B7=D6=C4=B8=
=A1=A3</STRONG></P>
<P>Executing...<BR> Test 1: TEST OK =
[0=20
secs]<BR> Test 2: TEST OK [0=20
secs]<BR> Test 3: TEST OK [0=20
secs]<BR> Test 4: TEST OK [0=20
secs]<BR> Test 5: TEST OK [0=20
secs]<BR> Test 6: TEST OK [0.004=20
secs]<BR> Test 7: TEST OK [0=20
secs]<BR> Test 8: TEST OK [0.004=20
secs]<BR> Test 9: TEST OK [0.004=20
secs]<BR> Test 10: TEST OK [0.004=20
secs]<BR> Test 11: TEST OK [0.008 =
secs]</P>
=
<P><STRONG>{<BR>TASK:frac1<BR>LANG:PASCAL<BR>}<BR>{$D-,L-,Y-,R-,S-,I-,Q-}=
<BR>program=20
frac1;<BR>const maxn=3D160;<BR>var<BR> =20
textt:array[1..500000] of char;<BR> =20
n:integer;<BR>procedure init;<BR>var<BR> =20
i:integer;<BR>begin<BR> =20
assign(input,'frac1.in');reset(input);<BR> =20
readln(n);<BR> =
close(input);<BR>end;<BR>procedure=20
genfrac(n1,d1,n2,d2:integer);<BR>begin<BR> if =
d1+d2>n=20
then exit;<BR> =20
genfrac(n1,d1,n1+n2,d1+d2);<BR> =20
writeln(n1+n2,'/',d1+d2);<BR> =20
genfrac(n1+n2,d1+d2,n2,d2);<BR>end;<BR>procedure=20
work;<BR>var<BR> =
i,now:integer;<BR> =20
min:real;<BR>begin<BR> =20
assign(output,'frac1.out');rewrite(output);<BR> =20
settextbuf(output,textt,sizeof(textt));<BR> =20
writeln('0/1');<BR> =20
genfrac(0,1,1,1);<BR> =20
writeln('1/1');<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> work;<BR>end.<BR></STRONG></P><STRONG>
<HR>
</STRONG>
<P></P>
=
<P><STRONG>USACO=B5=C4=CC=E2=BD=E2=A3=AC=D7=EE=BA=F3=C4=C7=B8=F6=D3=C3=B5=
=BD=C1=CB=B7=D6=D2=B1=B5=DD=B9=E9=A3=AC=D0=A7=C2=CA=CA=C7=CF=E0=B5=B1=B5=C4=
=B8=DF=B0=A1=A1=A3</STRONG></P>
<P><STRONG>Here's a very fast, straightforward solution from Alex=20
Schwedner: </STRONG></P><PRE><STRONG>#include <fstream.h>
#include <stdlib.h>
struct fraction {
int numerator;
int denominator;
};
bool rprime(int a, int b){
int r =3D a % b;
while(r !=3D 0){
a =3D b;
b =3D r;
r =3D a % b;
}
return(b =3D=3D 1);
}
int fraccompare (struct fraction *p, struct fraction *q) {
return p->numerator * q->denominator - p->denominator =
*q->numerator;
}
int main(){
int found =3D 0;
struct fraction fract[25600];
ifstream filein("frac1.in");
int n;
filein >> n;
filein.close();
for(int bot =3D 1; bot <=3D n; ++bot){
for(int top =3D 0; top <=3D bot; ++top){
if(rprime(top,bot)){
fract[found].numerator =3D top;
fract[found++].denominator =3D bot;
}
}
}
qsort(fract, found, sizeof (struct fraction), fraccompare);
ofstream fileout("frac1.out");
for(int i =3D 0; i < found; ++i)
fileout << fract[i].numerator << '/' << =
fract[i].denominator << endl;
fileout.close();
exit (0);
}
</STRONG></PRE>
<P><STRONG>Here's a super fast solution from Russ: </STRONG></P>
<P><STRONG>We notice that we can start with 0/1 and 1/1 as our=20
``endpoints'' and recursively generate the middle points by adding =
numerators and denominators. </STRONG></P><PRE><STRONG>0/1 =
1/1
1/2
1/3 2/3
1/4 2/5 3/5 3/4
1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5
</STRONG></PRE>
<P><STRONG>Each fraction is created from the one up to its right =
and the=20
one up to its left. This idea lends itself easily to a recursion =
that we=20
cut off when we go too deep. </STRONG></P><PRE><STRONG>#include =
<stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
int n;
FILE *fout;
/* print the fractions of denominator <=3D n between n1/d1 and n2/d2 =
*/
void
genfrac(int n1, int d1, int n2, int d2)
{
if(d1+d2 > n) /* cut off recursion */
return;
genfrac(n1,d1, n1+n2,d1+d2);
fprintf(fout, "%d/%d\n", n1+n2, d1+d2);
genfrac(n1+n2,d1+d2, n2,d2);
}
void
main(void)
{
FILE *fin;
fin =3D fopen("frac1.in", "r");
fout =3D fopen("frac1.out", "w");
assert(fin !=3D NULL && fout !=3D NULL);
fscanf(fin, "%d", &n);
fprintf(fout, "0/1\n");
genfrac(0,1, 1,1);
fprintf(fout, "1/1\n");
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/c644131713b2e4054a90a789">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/c644131713b2e4054a90a789.htm=
l#">=C9=BE=B3=FD</A>=20
<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3Dc644131713b2e4054a90a789=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
<!--
function blogdel(str)
{
var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
pop.setContent("callBack",delCallback);
pop.setContent("parameter",{fid:str,popup:pop});
pop.build();
pop.show();
return false;
}
function delCallback(para)
{
var o_pop=3Dpara["popup"];
o_pop.config.contentType=3D1;
o_pop.setContent("contentUrl","");
o_pop.reBuild();
G(para["fid"]).target=3Do_pop.iframeIdName;
eval("document."+para["fid"]).submit();
}
//-->
</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -