枚举所有的 排序
View Code
1 /* 2 ID: your_id_here 3 PROG: frac1 4 LANG: C++ 5 */ 6 #include <iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm> 10 using namespace std; 11 int w[201][201]; 12 struct node 13 { 14 int x,y; 15 double s; 16 }q[20001]; 17 void gcd(int x,int y) 18 { 19 int i; 20 int tx = x,ty = y; 21 for(i = ty; i >= 2 ; i--) 22 { 23 if(y%i==0&&x%i==0) 24 { 25 y = y/i; 26 x = x/i; 27 } 28 } 29 w[x][y] = 1; 30 } 31 bool cmp(node x,node y) 32 { 33 return x.s<y.s; 34 } 35 int main() 36 { 37 freopen("frac1.in","r",stdin); 38 freopen("frac1.out","w",stdout); 39 int i,j,k,n,g=0; 40 cin>>n; 41 for(i = 2; i <= n ; i++) 42 for(j = 1; j < i ;j++) 43 { 44 gcd(i,j); 45 } 46 for(i = 1; i <= n ; i++) 47 for(j = 1; j <= n ; j++) 48 { 49 if(w[i][j]) 50 { 51 g++; 52 q[g].x = i; 53 q[g].y = j; 54 q[g].s = j*1.0/(i*1.0); 55 } 56 } 57 sort(q+1,q+g+1,cmp); 58 cout<<"0/1\n"; 59 for(i = 1; i <= g ; i++) 60 printf("%d/%d\n",q[i].y,q[i].x); 61 cout<<"1/1\n"; 62 fclose(stdin); 63 fclose(stdout); 64 return 0; 65 }