#include <iostream.h>

#include <malloc.h>

#include <stdlib.h>

typedef struct date

{

       int a;

       int b;

}Date;

int check(int b,int a)//  b/a是否是真分数

{

       int i;

       for(i=2;i<=b;i++)

       if(a%i==0 && b%i==0)

              return 0;

       return 1;

}

int cmp(const void *a , const void *b )

{

       struct date *c = (struct date *)a;

       struct date *d = (struct date *)b;

       float x,y;

       x=(float)(c->b)/c->a;

       y=(float)(d->b)/d->a;

       if(x-y>0)

       return 0;

       return 1;

}

void FareySequence(int n)//, char farey[])

{

       int i,j;

       int total=0;

       Date *s;

       s=(struct date * )malloc(n*n*sizeof(struct date));

       for(i=2;i<=n;i++)

       {

              for(j=1;j<i;j++)

              {

                     if(check(j,i)==1)

                     {

                            s[total].a=i;

                            s[total].b=j;

                            total++;

                     }

              }

       }

       qsort(s,total,sizeof(s[0]),cmp);

       for(i=0;i<total;i++)

       cout<<s[i].b<<"~"<<s[i].a<<" ";

}

int main()

{

       int n;

       //char *farey;

       cin>>n;

       FareySequence(n);

}

评论