切换到宽版
发帖 回复
返回列表
12
  • 14652阅读
  • 16回复

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

 上一主题 下一主题
离线archimedes
管理员
 
只看楼主 倒序阅读 0 发表于: 2005-12-13
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

题是读懂了，大家讨论一下怎样做！
回复
举报
分享到 淘江湖 新浪 QQ微博 QQ空间 开心 人人 豆瓣 网易微博 百度 鲜果 白社会 飞信
离线archimedes
管理员
只看该作者 1 发表于: 2005-12-14
我想的是用Farey分数数列
回复
举报
离线stevenjl
管理员
只看该作者 2 发表于: 2005-12-16
穷举，排序，搜索呢？
Dream Walker...
回复
举报
离线archimedes
管理员
只看该作者 3 发表于: 2005-12-19
很好！但是时间复杂度...
回复
举报
离线stevenjl
管理员
只看该作者 4 发表于: 2005-12-20
那么你的思路呢？
Dream Walker...
回复
举报
离线tctc
OIFans初赛选手
只看该作者 5 发表于: 2005-12-23
可以生成
0/1 1/1中间插入0 + 1/ 1 + 1
然后再用类似方法生成0/1 和1/2之间的,边界是分母大过头了

还没试过，不知道能不能过……
回复
举报
离线archimedes
管理员
只看该作者 6 发表于: 2005-12-26
tctc，你的生成法运用了Farey分数数列的性质，算法是正确的，但是不知道能不能过
回复
举报
离线stevenjl
管理员
只看该作者 7 发表于: 2005-12-31
这个,数学上怎么证明呢?
Dream Walker...
回复
举报
离线archimedes
管理员
只看该作者 8 发表于: 2006-01-03
请看数论书，管理员同志
回复
举报
离线archimedes
管理员
只看该作者 9 发表于: 2006-01-28
我做的！
复制代码
  1. {
  2. ID: oifans1
  3. PROG: frac1
  4. LANG: PASCAL
  5. }
  6. program USACO_TrainingGate_2_1_OrderedFractions;
  7. type
  8. fraction=object
  9.   n,d:integer;
  10.   function v:real;
  11. end;
  12. var
  13. a:array[1..10000]of fraction;
  14. n,i,j,k:integer;
  15. f:fraction;
  16. function fraction.v:real;
  17. begin
  18. v:=n/d;
  19. end;
  20. function gcd(a,b:integer):integer;
  21. begin
  22. if b=0 then gcd:=a else gcd:=gcd(b,a mod b);
  23. end;
  24. procedure qSort(l, r: Integer);
  25. var
  26. i, j: integer;
  27. x: real; y: fraction;
  28. begin
  29. i := l; j := r; x := a[(l+r) div 2].v;
  30. repeat
  31.   while a[i].v < x do inc(i);
  32.   while x < a[j].v do dec(j);
  33.   if i <= j then
  34.   begin
  35.     y := a[i]; a[i] := a[j]; a[j] := y;
  36.     inc(i); dec(j);
  37.   end;
  38. until i > j;
  39. if l < j then qSort(l, j);
  40. if i < r then qSort(i, r);
  41. end;
  43. begin
  44. assign(input,'frac1.in'); reset(input);
  45. assign(output,'frac1.out'); rewrite(output);
  46. readln(n);
  47. i:=1;
  48. {Create the fraction array}
  49. for j:=1 to n do
  50.   for k:=1 to j do
  51.     if gcd(j,k)=1 then
  52.     begin
  53.       a[i].d:=j;
  54.       a[i].n:=k;
  55.       inc(i);
  56.     end;
  57. dec(i);
  58. {QuickSort the fraction array}
  59. qSort(1,i);
  60. {Output}
  61. writeln('0/1');
  62. for j:=1 to i do writeln(a[j].n,'/',a[j].d);
  63. close(output);
  64. end.
[ 此贴被sammy312在2006-01-28 16:29重新编辑 ]
回复
举报
发帖 回复
返回列表
12
快速回复
限100 字节
 
上一个 下一个