COGS p646 为 法雷序列
分析：
这题枚举出来真分数（欧几里得算法判断），然后快排。
当真分数a/b<真分数c/d时，有a*d<b*c
我是直接对真分数的实数值进行排序
1 type
2 node=record
3 x,y:longint; //integer足矣 4 d:double; //real足矣 5 end; 6 var
7 n,i,j,len:longint; 8 sn:array[1..8000] of node; //如果不想用记录类型，可以用一个二维数组 + 一个一位数组代替 9 function gcd(x,y:longint):longint; // function gcd(x,y:longint):longint; 10 begin // begin
11 if x=0 then gcd:=y // if y=0 then exit(x) 12 else gcd:=gcd(y mod x,x); // else exit(gcd(y,x mod y)); 13 end; // end
14
15 {function gcd(x,y:longint):longint; 16 var t:longint; 17 begin 18 while y<>0 do begin 19 t:=x; x:=y; y:=t mod y; 20 end; 21 end;}
22
23 procedure qsort(l,r:longint); 24 var i,j:longint; 25 mid:double; 26 temp:node; 27 begin
28 i:=l; j:=r; 29 mid:=sn[(l+r) div 2].d; 30 while i<=j do
31 begin
32 while sn[i].d<mid do inc(i); 33 while sn[j].d>mid do dec(j); 34 if i<=j then
35 begin
36 temp:=sn[i]; sn[i]:=sn[j]; sn[j]:=temp; //若用上述数组则需要写三行交换语句，记录类型直接交换 37 inc(i); dec(j); 38 end; 39 end; 40 if i<r then qsort(i,r); 41 if l<j then qsort(l,j); 42 end; 43 begin
44 assign(input,'frac1.in'); 45 assign(output,'frac1.out'); 46 reset(input); 47 rewrite(output); 48 readln(n); 49 sn[1].x:=0; sn[1].y:=1; sn[1].d:=0.0; 50 sn[2].x:=1; sn[2].y:=1; sn[2].d:=1.0; 51 len:=2; //也可以写成下面这样，省去初始化,直接输出首项和末项 52 for i:=2 to n do //for i:=1 to n-1 do
53 for j:=1 to i-1 do //for j:=i+1 to n do
54 if gcd(i,j)=1 then
55 begin
56 inc(len); 57 sn[len].x:=j; sn[len].y:=i; sn[len].d:=j/i; 58 end; 59 qsort(1,len); 60 for i:=1 to len do
61 writeln(sn[i].x,'/',sn[i].y); 62 close(input); 63 close(output); 64 end.
排行榜第一的大神用hash，不用排序直接输出，霸气啊~
瞻仰下牛的程序：
1 {
2 ID: qilinar3 3 PROG: frac1 4 LANG: PASCAL 5 }
6 var
7 hash:array[0..160*159,1..2] of integer; 8 i,j,n:integer; 9 t:longint; 10 begin
11 assign(input,'frac1.in');reset(input); 12 assign(output,'frac1.out');rewrite(output); 13 readln(n); 14 for i:=0 to n do
15 for j:=1 to n do
16 if j>=i then
17 begin
18 t:=round(i/j*160*159); 19 if hash[t][2]=0 then
20 begin hash[t][1]:=i; hash[t][2]:=j; end; 21 end; 22 for i:=0 to 160*159 do if hash[i][2]<>0 then writeln(hash[i][1],'/',hash[i][2]); 23 close(input);close(output); 24 end.