Ordered Fractions

	Source : Unknown
	Time limit : 3 sec		Memory limit : 32 M

Submitted : 1227, Accepted: 383

Consider the set of all reduced fractions between 0 and 1 inclusive with denomin

ators 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.

INPUT FORMAT

Several lines with a single integer N in each line. Process to the end of file.

SAMPLE INPUT

5
5

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude. print a blank line after each testcase.

SAMPLE OUTPUT

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

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

这个题开始提交时超时后来才发现输入输出太多了改成C语言的输入输出就没有超时了 0.12MS 相差几十倍这个以后得注意点啊嘿嘿难怪曾哥那么喜欢用C语言我却习惯用C++了一时改不过来

View Code

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <fstream>
 4 #include <stdio.h>
 5 using namespace std;
 6 
 7 #define max 170
 8 struct pp
 9 {
10     int x,y;
11     double b;
12 };
13 
14 int  judge(int x,int y)
15 {
16     int t;
17     while (y)
18     {
19         t=y;
20         y=x%y;
21         x=t;
22     }
23     return x;
24 }
25 bool mycomp(const pp &x,const pp &y)
26 {
27     if(x.b<y.b)  return true;
28     return false;
29 }
30 int main()
31 {
32 //    ifstream cin("1.txt");
33 //    ofstream cout("2.txt");
34 //    freopen("output","w",stdout);
35     int i,j,k;
36     int p=0,q;
37     int temp;
38     //while (cin>>p)
39         int m=0;
40         pp t[max*max];
41         for(i=1;i<max;i++)
42         {
43             for(j=0;j<max;j++)
44             {
45                 t[m++].b=1;
46             }
47         }
48         m=0;
49         for(i=1;i<=170;i++)
50         {
51             for(j=i;j<=170;j++)
52             {
53                 if(judge(i,j)>1) t[m].b=1;
54                 else
55                 {
56                     t[m].b=i*1.0/j;
57                     t[m].x=i;
58                     t[m].y=j;
59                     m++;
60                 }                
61             }
62         }
63         sort(t,t+m,mycomp);
64         while (scanf("%d",&p)!=EOF)
65     //    while(cin>>p)
66     {
67                 //    cout<<"0/1"<<endl;
68             printf("0/1\n");
69         for (i=0;i<m;i++)
70         {
71             if(t[i].b<1&&t[i].x<=p&&t[i].y<=p) //cout<<t[i].x<<"/"<<t[i].y<<endl;
72                 printf("%d/%d\n",t[i].x,t[i].y);
73         }
74         printf("1/1\n\n");
75         //cout<<"1/1"<<endl;
76     //    cout<<endl;
77     }
78     return 0;
79 }