//昨天在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个元素开始，堆大小为mvoid 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;}

评论