题目翻译来自http://www.nocow.cn/index.php/Translate:USACO/frac1
Translate:USACO/frac1
Ordered Fractions顺序的分数
输入一个自然数N,对于一个最简分数a/b(分子和分母互质的分数),满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。
描述
这有一个例子,当N=5时,所有解为:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
给定一个自然数N,1<=n<=160,请编程按分数值递增的顺序输出所有解。
注:①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。
格式
PROGRAM NAME: frac1
INPUT FORMAT:
(file frac1.in)
单独的一行 一个自然数N(1..160)
OUTPUT FORMAT:
(file frac1.out)
每个分数单独占一行,按照大小次序排列
SAMPLE INPUT
5
SAMPLE OUTPUT
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
【题解】
列举--》快排--》输出(注意重复的)
1 { 2 ID:fuzhong2 3 PROG:frac1 4 LANG:PASCAL 5 } 6 var 7 s,f:array[1..25600] of longint; 8 z:array[1..25600] of real; 9 w:real; 10 n,i,j,p:longint; 11 procedure com(var x,y:longint); 12 var 13 i:longint; 14 begin 15 for i:= y div 2 +1 downto 2 do 16 begin 17 if (y mod i=0) and (x mod i=0) then begin y:=y div i; x:=x div i; exit; end; 18 end; 19 end; 20 procedure qsort(l,h:longint); 21 var 22 i,j,tt:integer; 23 t,m:real; 24 begin 25 i:=l; j:=h; 26 m:=z[(i+j) div 2]; 27 repeat 28 while z[i]<m do inc(i); 29 while m<z[j] do dec(j); 30 if i<=j then 31 begin 32 t:=z[i]; z[i]:=z[j]; z[j]:=t; 33 tt:=f[i];f[i]:=f[j];f[j]:=tt; 34 tt:=s[i];s[i]:=s[j];s[j]:=tt; 35 inc(i); dec(j); 36 end; 37 until i>j; 38 if i<h then qsort(i,h); 39 if j>l then qsort(l,j); 40 end; 41 begin 42 assign(input,'frac1.in'); reset(input); 43 assign(output,'frac1.out');rewrite(output); 44 read(n); 45 p:=0; 46 for i:= 1 to n do 47 for j:=1 to i-1 do 48 begin 49 inc(p); 50 f[p]:=i; 51 s[p]:=j; 52 z[p]:=(j/i*10000)div 1; 53 end; 54 qsort(1,p); 55 w:=-1; 56 writeln('0/1'); 57 for i:= 1 to p do 58 begin 59 if z[i]=w then continue else w:=z[i]; 60 com(s[i],f[i]); 61 writeln(s[i],'/',f[i]); 62 end; 63 writeln('1/1'); 64 close(input); 65 close(output); 66 end.
真心写的有点乱
USER: fu zhongqing [fuzhong2] TASK: frac1 LANG: PASCAL Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 676 KB] Test 2: TEST OK [0.000 secs, 676 KB] Test 3: TEST OK [0.000 secs, 676 KB] Test 4: TEST OK [0.000 secs, 676 KB] Test 5: TEST OK [0.000 secs, 676 KB] Test 6: TEST OK [0.000 secs, 676 KB] Test 7: TEST OK [0.000 secs, 676 KB] Test 8: TEST OK [0.000 secs, 676 KB] Test 9: TEST OK [0.000 secs, 676 KB] Test 10: TEST OK [0.000 secs, 676 KB] Test 11: TEST OK [0.011 secs, 676 KB] All tests OK.
Your program ('frac1') produced all correct answers! This is your submission #2 for this problem. Congratulations!
Here are the test data inputs:
------- test 1 ---- 1 ------- test 2 ---- 2 ------- test 3 ---- 4 ------- test 4 ---- 7 ------- test 5 ---- 10 ------- test 6 ---- 15 ------- test 7 ---- 24 ------- test 8 ---- 50 ------- test 9 ---- 75 ------- test 10 ---- 100 ------- test 11 ---- 160Keep up the good work!
Thanks for your submission!