usaco_frac1.cpp

usaco自己做的1到5章的代码

/*
ID:wangyuc2
PROG:frac1
LANG:C++
*/
#include <iostream>
#include <fstream>
#include <memory.h>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin ("frac1.in");
ofstream fout ("frac1.out");   
struct data{
       int a,b;
       double c;
       }d[30000];
       
int op(const void *a,const void *b)
{
     data *c=(data *)a;
     data *d=(data *)b;
     if(c->c<d->c) return 1;
     else if(c->c==d->c) return 0;
     else return -1;
}

int gcd(int a,int b)
{
 if(b == 0)
  return a;
 return gcd(b,a%b);
}

int main()
{
    int i,j,k=0,n;
    fin>>n;
    for(i=1;i<=n;i++)
       for(j=1;j<=i;j++)
       {
           if(gcd(j,i)==1)
           {
               d[k].a=j;
               d[k].b=i;
               d[k].c=(double)i/(double)j;
               k++;
           }
       }
    qsort(d,k,sizeof(data),op);
    fout<<"0/1"<<endl;
    for(i=0;i<k;i++)
      fout<<d[i].a<<'/'<<d[i].b<<endl;
   // system("PAUSE");
    return 0;
}