『讨论』USACO Ordered Fractions [复制链接]

Ordered Fractions

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

PROGRAM NAME: frac1
INPUT FORMAT
One line with a single integer N.
SAMPLE INPUT (file frac1.in)
5

OUTPUT FORMAT
One fraction per line, sorted in order of magnitude.
SAMPLE OUTPUT (file frac1.out)
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

题是读懂了，大家讨论一下怎样做！

TASK: frac1
LANG: PASCAL

Compiling...
Compile: OK

Executing...
sending data (frac1) frac1 /home/kolstad/trainweb
Test 1 OK [0.003 secs]
Test 2 OK [0.003 secs]
Test 3 OK [0.002 secs]
Test 4 OK [0.003 secs]
Test 5 OK [0.003 secs]
Test 6 OK [0.003 secs]
Test 7 OK [0.003 secs]
Test 8 OK [0.005 secs]
Test 9 OK [0.008 secs]
Test 10 OK [0.011 secs]
Test 11 OK [0.029 secs]

All tests OK.




{
PROG:frac1
LANG:PASCAL
}
const
  inf='frac1.in';
  outf='frac1.out';
type
  pzy=record
    a,b:integer;
    c:real;
  end;
var
  n,k,i,j:integer;
  x:array [1..maxint] of pzy;
  temp:pzy;
function gy(a,b:integer):integer;
  var
    r:integer;
  begin
    r:=a mod b;
    while r<>0 do
      begin
        a:=b;
        b:=r;
        r:=a mod b;
      end;
    gy:=b;
  end;
procedure quicksort(v1,v2:integer);
  var
    i,j:integer;
    mid:real;
    temp:pzy;
  begin
    mid:=x[(v1+v2) div 2].c;
    i:=v1;
    j:=v2;
    while i<j do
      begin
        while x.c<mid do
          inc(i);
        while x[j].c>mid do
          dec(j);
        if i<=j then
          begin
            temp:=x;
            x:=x[j];
            x[j]:=temp;
            inc(i);
            dec(j);
          end;
      end;
    if i<v2 then
      quicksort(i,v2);
    if j>v1 then
      quicksort(v1,j);
  end;
begin
  assign(input,inf);
  reset(input);
  assign(output,outf);
  rewrite(output);
  readln(n);
  x[1].a:=0;
  x[1].b:=1;
  x[1].c:=0;
  x[2].a:=1;
  x[2].b:=1;
  x[2].c:=1;
  k:=2;
  for i:=2 to n do
    for j:=1 to i-1 do
      if gy(i,j)=1 then
        begin
          inc(k);
          x[k].a:=j;
          x[k].b:=i;
          x[k].c:=j/i;
        end;
  quicksort(1,k);
  for i:=1 to k do
    writeln(x.a,'/',x.b);
  close(input);
  close(output);
end.

[ 此贴被pzy在2006-02-13 19:48重新编辑 ]

{
PROG:frac1
LANG:PASCAL
}
const
  inf='frac1.in';
  outf='frac1.out';
type
  pzy=record
    a,b:integer;
  end;
var
  n,k,i,j:integer;
  x:array [1..maxint] of pzy;
  temp:pzy;
function gy(a,b:integer):integer;
  var
    r:integer;
  begin
    r:=a mod b;
    while r<>0 do
      begin
        a:=b;
        b:=r;
        r:=a mod b;
      end;
    gy:=b;
  end;
begin
  assign(input,inf);
  reset(input);
  assign(output,outf);
  rewrite(output);
  readln(n);
  x[1].a:=0;
  x[1].b:=1;
  x[2].a:=1;
  x[2].b:=1;
  k:=2;
  for i:=2 to n do
    for j:=1 to i-1 do
      if gy(i,j)=1 then
        begin
          inc(k);
          x[k].a:=j;
          x[k].b:=i;
        end;
  for i:=1 to k-1 do
    for j:=i+1 to k do
      if x.a*x[j].b>x.b*x[j].a then
        begin
          temp:=x;
          x:=x[j];
          x[j]:=temp;
        end;
  for i:=1 to k do
    writeln(x.a,'/',x.b);
  close(input);
  close(output);
end.

说实话，gcd那一段是从我们论坛[最新动态]文章“备战NOIP2005必须掌握的基本算法”那里抄的gcd。不是自己写的~

不敢当，说实话，我喜欢用object类型
tctc的方法也是可以的。

{ ID: oifans1 PROG: frac1 LANG: PASCAL } program USACO_TrainingGate_2_1_OrderedFractions; type fraction=object n,d:smallint; function v:longint; end; var a:array[1..10000]of fraction; n,i,j,k:smallint; f:fraction; function fraction.v:longint; begin v:=n*50000 div d; end; function gcd(a,b:smallint):boolean; begin if b=0 then begin if a=1 then exit(true); exit(false); end; gcd:=gcd(b,a mod b); end; procedure qSort(l, r:smallint); var i, j: smallint; x: longint; y: fraction; begin i := l; j := r; x := a[(l+r) div 2].v; repeat while a<i>.v < x do inc(i); while x < a[j].v do dec(j); if i <= j then begin y := a<i>; a<i> := a[j]; a[j] := y; inc(i); dec(j); end; until i > j; if l < j then qSort(l, j); if i < r then qSort(i, r); end; begin assign(input,'frac1.in'); reset(input); assign(output,'frac1.out'); rewrite(output); readln(n); i:=1; {Create the fraction array} for j:=1 to n do for k:=1 to j do if gcd(j,k) then begin a<i>.d:=j; a<i>.n:=k; inc(i); end; dec(i); {QuickSort the fraction array} qSort(1,i); {Output} writeln('0/1'); for j:=1 to i do writeln(a[j].n,'/',a[j].d); close(output); end.

楼主的代码很好，可读性也很强！
稍微改了改，主要是缩小了数据类型。使用了一个FP的新类型（smallint），提高了一些时间，小修改，再次赞颂楼主！

TASK: frac1
LANG: PASCAL

Compiling...
Compile: OK

Executing...
sending data (frac1) frac1 /home/kolstad/trainweb

Test 1 OK [0.002 secs]
Test 2 OK [0.003 secs]
Test 3 OK [0.002 secs]
Test 4 OK [0.003 secs]
Test 5 OK [0.003 secs]
Test 6 OK [0.003 secs]
Test 7 OK [0.003 secs]
Test 8 OK [0.005 secs]
Test 9 OK [0.009 secs]
Test 10 OK [0.011 secs]
Test 11 OK [0.032 secs]

All tests OK.

Your program ('frac1') produced all correct answers!  This is your
submission #41 for this problem.  Congratulations!

gcd那段写得漂亮，我怎么就想不到呢？

我的结果
USACO Training Grader Results for oi fans [oifans1]

TASK: frac1
LANG: PASCAL

Compiling...
Compile: OK

Executing...
sending data frac1
Test 1 OK [0.002 secs]
Test 2 OK [0.002 secs]
Test 3 OK [0.003 secs]
Test 4 OK [0.003 secs]
Test 5 OK [0.002 secs]
Test 6 OK [0.003 secs]
Test 7 OK [0.003 secs]
Test 8 OK [0.005 secs]
Test 9 OK [0.009 secs]
Test 10 OK [0.015 secs]
Test 11 OK [0.037 secs]

All tests OK.
Your program ('frac1') produced all correct answers! This is your
submission #11 for this problem. Congratulations!

我做的！

请看数论书，管理员同志