//昨天在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;
}

评论