#include "math.h"
#define null 0
#define Node struct node
#define len sizeof(Node)
Node
{
 char cdata[7];
 float fdata;
 Node *next;
};
int IsZhiShu(int n)
{
  int k,i;k=sqrt(n); i=2;
  while(i<=k){if(n%i==0) break;i++;}
  if(i>=k+1)return 1;else return 0;
}
int CanYueFen(int x,int y)
{
  int i,j;i=x>=y?x:y;
  if(IsZhiShu(i))return 0;
  else
   {i=x<=y?x:y;for(j=2;j<=i;j++)if(x%j==0&&y%j==0) return 1;return 0;}
}
void MyPrint(Node *p)
{
  while(p!=null)
  {
    printf("%s",p->cdata);
    p=p->next;
  }
}

Node * MyInit(int n)
{
 Node *head,*p,*pnew;
 int i,j;
 head=(Node *)malloc(len);p=(Node *)malloc(len);
 head->cdata[0]='0';head->cdata[1]='/';head->cdata[2]='1';head->cdata[3]=',';
 head->cdata[4]='\0';head->fdata=0;head->next=p;
 p->cdata[0]='1';p->cdata[1]='/';p->cdata[2]='1';p->cdata[3]='\0';
 p->fdata=1;p->next=null;
 if(n==1){return head;}
 else
 {
   i=2;while(i<=n)
       {
         if(i<10)
           {
             if(IsZhiShu(i))
             {
               for(j=1;j<i;j++)
               {pnew=(Node *)malloc(len);pnew->fdata=(float)j/(float)i;
                pnew->next=null;pnew->cdata[0]=j+'0';pnew->cdata[1]='/';
                pnew->cdata[2]=i+'0';pnew->cdata[3]=',';
                pnew->cdata[4]='\0';p=head;
                while(1)
                 {
                   if(pnew->fdata>p->fdata&&pnew->fdata<p->next->fdata)
                    {pnew->next=p->next;p->next=pnew;break;}
                     p=p->next;
                 }
               }
             }
             else
             {
               j=1;while(j<i)
               {
                 if(!CanYueFen(i,j))
                 {
                   pnew=(Node *)malloc(len);pnew->fdata=(float)j/(float)i;
                   pnew->next=null;pnew->cdata[0]=j+'0';pnew->cdata[1]='/';
                   pnew->cdata[2]=i+'0';pnew->cdata[3]=',';
                   pnew->cdata[4]='\0';p=head;
                  while(1)
                   {
                   if(pnew->fdata>p->fdata&&pnew->fdata<p->next->fdata)
                    {pnew->next=p->next;p->next=pnew;break;}
                     p=p->next;
                   }
                 }
                j++;
               }
             }
           }

else if(i>=10&&i<100)
         {
            if(IsZhiShu(i))
             {
               for(j=1;j<i;j++)
               {pnew=(Node *)malloc(len);pnew->fdata=(float)j/(float)i;
                pnew->next=null;
                if(j<10)
                 {pnew->cdata[0]=j+'0';pnew->cdata[1]='/';
                  pnew->cdata[2]=i/10+'0';pnew->cdata[3]=i%10+'0';
                  pnew->cdata[4]=','; pnew->cdata[5]='\0';
                 }
                else
                { pnew->cdata[0]=j/10+'0';pnew->cdata[1]=j%10+'0';
                  pnew->cdata[2]='/';pnew->cdata[3]=i/10+'0';
                  pnew->cdata[4]=i%10+'0';pnew->cdata[5]=',';
                  pnew->cdata[6]='\0';
                }p=head;
                while(1)
                 {
                   if(pnew->fdata>p->fdata&&pnew->fdata<p->next->fdata)
                    {pnew->next=p->next;p->next=pnew;break;}
                     p=p->next;
                 }
               }
             }
            else
             {
               j=1;while(j<i)
               {
                 if(!CanYueFen(i,j))
                 { pnew=(Node *)malloc(len);pnew->fdata=(float)j/(float)i;
                   pnew->next=null;
                   if(j<10)
                 {pnew->cdata[0]=j+'0';pnew->cdata[1]='/';
                  pnew->cdata[2]=i/10+'0';pnew->cdata[3]=i%10+'0';
                  pnew->cdata[4]=','; pnew->cdata[5]='\0';
                 }
                else
                 { pnew->cdata[0]=j/10+'0';pnew->cdata[1]=j%10+'0';
                  pnew->cdata[2]='/';pnew->cdata[3]=i/10+'0';
                  pnew->cdata[4]=i%10+'0';pnew->cdata[5]=',';
                  pnew->cdata[6]='\0';
                 }p=head;
                while(1)
                 {
                  if(pnew->fdata>p->fdata&&pnew->fdata<p->next->fdata)
                   {
                    pnew->next=p->next;
                    p->next=pnew;
                    break;
                   }
                     p=p->next;
                   }
                 }
                j++;
               }
             }
         }
         i++;
       }
   return head;
 }
}
void MyFree(Node *head)
{
 Node *p;
 while(head==null)
 {
  p=head;
  head=head->next;
  free(p);
 }
}

main()
{
 Node *t;
 int n;
 clrscr();
 printf("please input a number between 1and 90~!input 0 to exit~!\n");
 while(1)
 {
   scanf("%d",&n);
   if(n==0) break;
   else if(n>=1&&n<=90)
   {
    t=MyInit(n);
    MyPrint(t);
    MyFree(t);
    printf("\npress any key to continue~!\n");
    getch();
   }
   else printf("\n wrong input ~!!\n");
   printf("\nplease input a number between 1and 91~!input 0 to exit~!\n");
 }
}

#include<stdio.h>
#include<malloc.h>
#define LEN sizeof(struct fare)
struct fare
    {
        int nemr;
        int demo;
        struct fare * next;
    };
void FareySequence(int n, char farey[])
{    
    int temp;
    struct fare *p1,*p2,*head;
    void print(struct fare *head);
    struct fare *Initial(); /* 创建一个初始化链表*/
    struct fare *Insert(struct fare *fback,int fnemr,int fdemo); //插入节点
    void Output(struct fare *fy,char farey[]);
    head=Initial();
    p1=head;
    p2=p1->next;
    while(p2!=NULL)
    {
        temp=p1->demo+p2->demo;
        if( temp<=n )
        {            
            p2=Insert(p1,p1->nemr +p2->nemr,temp );            
        }
        else
        {
            p1=p2;
            p2=p2->next;
        }
    }
    Output(head,farey);    
}
struct fare *Initial()
{
    struct fare *head;
    struct fare *p1,*p2;
    int i;
    p1=p2=(struct fare *)malloc(LEN);
    head=p1;
    for(i=0;i<=1;i++)
    {
        p2->next=p1;
        p1->nemr=i;
        p1->demo=1;
        p2=p1;
        p1=(struct fare *)malloc(LEN);
    }
    p2->next=NULL;
    return(head);
}
struct fare *Insert(struct fare *fback,int fnemr,int fdemo) //插入节点
{
    struct fare *p;
    p=(struct fare *)malloc(LEN);
    p->next =fback->next;
    p->nemr=fnemr;
    p->demo =fdemo;
    fback->next=p;
    return(p);
}
void Output(struct fare *fy,char farey[])
{
    char *p;
    int offset=0;
    struct fare *sp;
    sp=fy;
    p=farey;
    do
    {
        offset=sprintf(p,"%d/%d,",sp->nemr,sp->demo);
        p+=offset;
        sp=sp->next;
    }while(sp!=NULL);
    p--;
    *p='\0';
}

#include <cstdio>
#include <algorithm>
#define L 25
using namespace std;

//采用辗转相除来判断是否可约 
int gcv( int a, int b )
{
     int big = max( a, b );
    int small = min( a, b );
    int temp;
    while( small > 1 )
    {
           temp = big % small;
          if( temp == 0 )    break;
          big = small;
          small = temp;       
    }    
    return small > 1 ? 0 : 1;
}

//寻找当前最小的不可约分数 
int search( int start, int end, int Farey[] )
{
     int n = start;
     int s = start, m = Farey[start];
     for( int i = start + 1; i <= end; i++ )
     {
          if( (i*m - s*Farey[i])<0 )
         {    
                  s = i;
                  m = Farey[i];
                  n = i;      
         }
    }
    return n;
}

void FareySequence( int n, char farey[] )
{
      int Farey[n];    //建立一个数组来表示所有分数 
     int cnum, i;
     int start = 1, end = 1;
     
     sprintf( farey, "0/1," );
      for( i = 1; i < n; i++ )    Farey[i] = n;
     
     while( Farey[n-1] != n-1 )
     {      
          cnum = search( start, end, Farey );    
          if( !gcv( cnum , Farey[cnum] ))
          {
                 do{
                             Farey[cnum] = max( Farey[cnum]-1, cnum );                 
                   }while( !gcv(cnum, Farey[cnum]) );
                   continue;
          }
          
          char temp[L];
          sprintf( temp, "%d/%d,", cnum, Farey[cnum] );
          strcat( farey, temp ); 
          
          Farey[cnum] = max( Farey[cnum]-1, cnum );
          
          if( cnum == Farey[cnum] )    start++;
    
          for( i = cnum; i < n && Farey[i]!=n; i++ );
          
          end = i;              
     }    
     
     char temp[]="1/1\0";
     strcat( farey, temp );
}

int main()
{
     char farey[1000];
     FareySequence( 8, farey );
     printf("%s\n", farey );
     system("pause");
     return 0;
}

//昨天在9楼交过一次。那个算法空间占用太大O(n*n)，在n=1000时临时数据需要超过500M内存。
//所以又想了这个算法：将1/2,1/3,....1/n这n－1个元素构造小顶堆。每次从堆顶拿出一个元素，放到farey[]中。
//从堆顶删去这个元素，加入分母相同分子更大的元素（如果存在），整理堆。重复，直到堆为空。
//时间复杂度与我的上一个程序相同，但空间是线性的。
#include<iostream.h>
#include<string.h>

//求最大公约数
int gcd(int a,int b)    
{
    if (a%b==0) return b;
    return gcd(b,a%b);
}

//数字转字符串
void num2str(int x,char* str)   
{
    int p=0;
    long t=1;
    while (t*10<=x) 
        t*=10;
    while (t>0) 
    {
        str[p++]=char(x/t+48);
        x%=t;
        t/=10;
    }
    str[p]=0;
}

//字符串连接函数
//开始用的是strcat，时间复杂度达到了惊人的n^4。不得不自己又写了个。
void strJoin(char* a,long* len,const char* b)
{
    int p=0;
    while (b[p])
        a[(*len)++]=b[p++];
    a[*len]=0;
}

//整理堆。从第i个元素开始，堆大小为m
void makeHeap(int* p,int* q,int i,int m)
{
    int k=i*2+1;
    if (k+1<m && p[k]*q[k+1]>p[k+1]*q[k])
        k++;
    if (k<m && p[i]*q[k]>p[k]*q[i])
    {
        int temp=p[i];
        p[i]=p[k];
        p[k]=temp;
        temp=q[i];
        q[i]=q[k];
        q[k]=temp;

        if (k*2+1<m) 
            makeHeap(p,q,k,m);
    }
}

void FareySequence(int n, char farey[])
{
    int *p,*q;                //p[]分子，q[]分母
    long len;                //farey[]的长度

    
    //初始化堆。分子全为1，分母依次是n,n-1,....2
    p=new int[n+1];
    q=new int[n+1];
    for (int i=0;i<n-1;i++)
    {
        p[i]=1;
        q[i]=n-i;
    }
    strcpy(farey,"0/1,");
    len=strlen(farey);

    int m=n-1;        //能用的分母个数，也是堆内元素个数
    while (m>0)
    {
        //将堆顶的元素转成字符串存放到farey[]中
        char str[10];
        num2str(p[0],str);
        strJoin(farey,&len,str);
        strJoin(farey,&len,"/");
        num2str(q[0],str);
        strJoin(farey,&len,str);
        strJoin(farey,&len,",");

        //获得下一个元素
        do p[0]++;
        while (p[0]<q[0] && gcd(p[0],q[0])!=1);
        //如果这个分母能扩展的元素已经用完，删掉它。
        if (p[0]==q[0])
        {
            p[0]=p[m-1];
            q[0]=q[m-1];
            m--;
        }
        if (m>1) makeHeap(p,q,0,m);    //如果堆内元素超过1个，整理堆
    }
    strJoin(farey,&len,"1/1");

    delete[] p;
    delete[] q;
}

#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int Fcmp (const void *a, const void *b)
{
    unsigned int c = *(int*)a;
    unsigned int d = *(int*)b;

    return (c & 0x0000ffff) * (d >> 16) - (d & 0x0000ffff) * (c >> 16);
}

void FareySequence(int n, char farey[])
{
    int m = n * (n - 1) / 2;
    unsigned int *num = new unsigned int[m];

    for (int i = 0; i < m; ++i)
        num[i] = 0;
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j) {
            int id = (i - 1) * (i - 2)/2 + j - 1;
            if (num[id] == 0)
                for (int k = i+i, l = j+j; k <= n; k += i, l += j)
                    num[(k-1)*(k-2)/2+l-1] = 1;
        }
    int s = 0, k = 0;
    for (int i = 0; i <= n; ++i)
        for (int j = 1; j < i; ++j, ++k)
            if (num[k] == 0)
                num[s++] = (i << 16) + j;
    qsort (num, s, sizeof (int), Fcmp);

    char str[10];
    strcpy (farey, "0/1,");
    for (int i = 0; i < s; ++i) {
        sprintf (str, "%d/%d,", num[i] & 0x0000ffff, num[i] >> 16);
        strcat (farey, str);
    }
    strcat (farey, "1/1");
        
    delete []num;
}

//改进后的程序，排序速度进一步提高

// 36match1.cpp : Defines the entry point for the console application.
//
//#define OUT_TIME

#include "stdafx.h"

#ifdef OUT_TIME
    #include "currTime.h"    
#endif

#include <math.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>
#include <search.h>

typedef  unsigned char BYTE;
typedef  unsigned long DWORD;
typedef  unsigned short WORD;
typedef  int           BOOL;

#define  TRUE    1
#define  FALSE   0

#define FAREY_BASE          1000
#define FRACTION_ARRAY_COUNT 16  //使用16个分数数组

typedef struct _PrimeTab
{
    DWORD *PrimeTab;
    BYTE *byteFlag;
    int   max;
    int   count;
}PrimeTab;

typedef struct _Fraction
{
    WORD  numerator;
    WORD  denominator;
}Fraction;


typedef struct _FractionArray
{
    Fraction *Data;
    int size;
    int count;
}FractionArray;
    
typedef struct _FareyArray
{
    BYTE *pByteArray;
    int   byteArrayLen;
    int   fac_count;
    DWORD fac[32];
    FractionArray array;
}FareyArray;

typedef struct _divArea
{
    int base;
    int pt;
    int count;
}DivArea;

// 全局变量，质数表
PrimeTab g_primeTab=
{
    NULL,
    NULL,
    0,
    0
};

FareyArray g_fareyArray;

//将n转化为字符串str，不写入字符串结束符0
//如果不考虑性能，可用sprintf(str,"%d",n)来实现类似的功能
char* my_itoa(int n,char *str)
{
    char buff[12];
    char *p=buff+11;
    if (n==0)
    {
        *str++='0';
        return str;
    }
    *p--=0;
    while (n>0)
    {
        *p-- = (n % 10)+'0';
        n/=10;
    }
    p++;
    while (*p)
        *str++= *p++;
    return str;
}

//扩大动态数组的存储空间
//形如FractionArray_实现动态数组的部分功能
//在C++中，可以用直接使用　STL中的 vector
BOOL FractionArray_setSize(FractionArray *me,int newSize)
{
    if ( me->Data!=NULL)
        delete[] me->Data;

    me->Data=new Fraction[newSize];
    
    if (me->Data==NULL)
        return FALSE;
    else
    {
        me->size=newSize;
        return TRUE;
    }
}



static int __cdecl FractionCompare(const void *element1,const void *element2)
{
    Fraction *p1,*p2;
    p1=(Fraction *)element1;
    p2=(Fraction *)element2;

    double v1,v2;
    v1=(double)(p1->numerator) / (double)(p1->denominator);
    v2=(double)(p2->numerator) / (double)(p2->denominator);
    if ( v1 > v2)
        return 1;
    else  if ( v1 < v2 )
        return -1;
    else 
        return 0;

}


//使用c库函数qsort（快速排序对分数数组排序）
void FractionArray_Sort(FractionArray *me,DivArea *pDivTab, int nDiv)
{
    int i;
    for (i=0;i<nDiv;i++)
    {
         qsort( me->Data+(pDivTab[i].base), pDivTab[i].count, sizeof( Fraction), FractionCompare );
    }
}

//输出分数数组的所有分数到buff,各个分数用/来隔开
void FractionArray_output(FareyArray *me,char buff[] )
{
    int i;
    char *tag;

    tag=buff;
    
    *tag++='0';
    *tag++='/';
    *tag++='1';
    *tag++=',';

    for (i=0;i<me->array.count;i++)
    {
        tag=my_itoa( me->array.Data[i].numerator,tag);
        *tag++='/';
        tag=my_itoa( me->array.Data[i].denominator,tag);
        *tag++=',';
    }

    *tag++='1';
    *tag++='/';
    *tag++='1';
    *tag=0;
}

//形如FractionArray_实现动态数组的部分功能
//在C++中，可以用直接使用　STL中的 vector
//释放分数数组所占用的内存空间
void FractionArray_Free(FractionArray *me)
{
    if (me->Data!=NULL)
        delete[] me->Data;
    me->Data=NULL;
    me->count=me->size=0;
}

//形如FractionArray_实现动态数组的部分功能
//在C++中，可以用直接使用　STL中的 vector
//初始化分数数组，预留FRACTION_ARRAY_BASE个元素空间
void FractionArray_Init(FractionArray *me)
{
    me->Data=NULL;
    me->count=me->size=0;
}

// 用埃氏筛法计算n以内的所有质数
//sift the all prime less than  n 
void PrimeTab_Sift(BYTE *siftbuff,DWORD n)
{
    DWORD i,sqrt_n,p;
    //----------------------------
    sqrt_n=(int)sqrt(n)+1;
    while (sqrt_n*sqrt_n >n)
        sqrt_n--;
    
    memset(siftbuff,1,n+1);

    *siftbuff=0;
    *(siftbuff+1)=0; //1不是质数
    *(siftbuff+2)=1; //2是质数

    for (i=4;i<=n;i+=2)
        *(siftbuff+i)=0;          //筛去2的倍数

    for (i=3;i<=sqrt_n;) //i 是质数
    {
        for (p=i*i;p<=n; p+=2*i)
            *(siftbuff+p)=0; //筛去i 的奇数倍
        i+=2;
        while ( *(siftbuff+i)==0 ) 
            i++; //前进到下一个质数
    }
}

//初始化n以内的质数表，
//如果质数的范围小于n，则用埃氏筛法重新筛选质数
BOOL PrimeTab_ReSift(PrimeTab *pTab,DWORD n)
{
    int i,count1,count2;
    if ( n<=pTab->max)
        return TRUE;

    if (pTab->byteFlag!=NULL)
    {
        delete[] pTab->byteFlag;
        pTab->byteFlag=NULL;
    }      
    
    if (pTab->PrimeTab!=NULL)
    {
        delete[] pTab->PrimeTab;
        pTab->PrimeTab;
    }

    pTab->byteFlag=new BYTE[n+1];
    if (pTab->byteFlag==NULL)
        return FALSE;
    
    PrimeTab_Sift(pTab->byteFlag,n);
    
    //统计n以内的所有质数的个数
    for (count1=0,i=0;i<=n;i++)
    {
        if (pTab->byteFlag[i])
            count1++;
    }
    
    pTab->PrimeTab=new DWORD[count1];
    
    //将筛出来的质数放入质数表
    count2=0;
    for (i=0;i<=n;i++)
    {
        if (pTab->byteFlag[i])
        {
            pTab->PrimeTab[count2]=i;
            count2++;
        }
    }
    pTab->max=n;
    pTab->count=count2;
    return TRUE;
}


//释放FareyArray变量占用的内存空间
BOOL Farey_Free(FareyArray *p)
{
    if (p->pByteArray!=NULL)
    {
        delete[] p->pByteArray;
        p->pByteArray=NULL;
    }
    p->byteArrayLen=0;
    FractionArray_Free(&(p->array));
    return TRUE;
}

//为本程序分配所需的内存空间，仅需在main开始时调用一次
BOOL InitData()
{
    g_fareyArray.byteArrayLen=0;
    g_fareyArray.pByteArray= new BYTE[FAREY_BASE+1];
    if (g_fareyArray.pByteArray==NULL)
        return FALSE;
    
    g_fareyArray.byteArrayLen=FAREY_BASE;
    FractionArray_Init( &(g_fareyArray.array));
    return TRUE;
}

//释入为本程序分配所需的内存空间，仅需在main结束时时调用一次
void FreeData()
{
    if (g_primeTab.PrimeTab!=NULL)
        delete[] g_primeTab.PrimeTab;
    
    if (g_primeTab.byteFlag!=NULL)
        delete[] g_primeTab.byteFlag;

    g_primeTab.count=0;
    g_primeTab.max =0;
    
    g_primeTab.PrimeTab=NULL;
    g_primeTab.byteFlag=NULL;

    Farey_Free(&g_fareyArray);
}

//为计算法雷序列分配内存空间 
BOOL Farey_Init(FareyArray *p,int n)
{
    if (n< p->byteArrayLen  && p->pByteArray!=NULL) 
        return TRUE;

    p->byteArrayLen=0;
    p->pByteArray= new BYTE[n+1];
    if (p->pByteArray==NULL)
        return FALSE;
    
    p->byteArrayLen=n;
    FractionArray_Init( &(p->array));
    return TRUE;
}

// 判断n 是否是质数，是返回1，否，将素因子存入p->fac
int Farey_isPrime( int n,
    FareyArray *p,
    PrimeTab *primeTab
    )
{
    int flag,t,i=0;

    p->fac_count=p->fac[0]=0;
    
    if ( primeTab->byteFlag[n] )
        return TRUE;

    i=0;
    while (n>1 && i<primeTab->count)
    {
        t=primeTab->PrimeTab[i];
        if ( t*2>n)
            break;

        flag=0;
        while ( n % t==0 )
        {
            n /=t;
            flag=1;
        }

        if ( flag)
        {
            p->fac[p->fac_count]=t;
            p->fac_count++;
        }
        
        if ( primeTab->byteFlag[n] )
        {
            p->fac[p->fac_count]=n;
            p->fac_count++;
            break;    
        }
        i++;
    }
    return FALSE;
}