原帖及讨论：http://bbs.bccn.net/thread-208692-1-1.html 1.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数，且它们中最大的质数最小算法：DP,背包问题，复杂度约为O( (N/10)^2 ) #include<stdio.h>#include<string.h>#include<math.h>#define SIZE 5000#define SIZELINE 20000int x[SIZE]={2},l; /*质数表*/struct{      char ok;      int l[200];      short p;} countline[SIZELINE];void qsort(int low,int high,int key[]){     int i,j,tag;     i=low; j=high;     if(i<j)     {       tag=key[i];       do       {         while(tag<key[j] && i<j) j--;         if(i<j)         {                key[i]=key[j];                i++;                while(tag>=key[i] && i<j) i++;                if(i<j)                {                       key[j]=key[i];                       j--;                }         }       }while(i<j);       key[i]=tag;       qsort(low,j-1,key);       qsort(i+1,high,key);     }}int main(void){    int i,j,k,tmp;    int n;    while(scanf("%d",&n)!=EOF)    {        l=1;        memset(countline,0,sizeof(countline));        for(i=3;i<=n;i++)        {          tmp=sqrt(i);          for(j=2;j<=tmp;j++)            if(i%j==0) break;          if(j>tmp)          {            x[l]=i;            l++;          }        }        countline[0].ok=1;        for(i=0;i<l;i++)        {          for(j=n;j>0;j--)          {            if(j<x[i]) break;            if(!countline[j].ok && countline[j-x[i]].ok)            {              countline[j].ok=1;              countline[j].l[countline[j].p]=x[i];              countline[j].p++;              k=0;              while(k<countline[j-x[i]].p)              {                countline[j].l[countline[j].p]=countline[j-x[i]].l[k];                countline[j].p++; k++;              }            }          }          if(countline[n].ok) break;        }                qsort(0,countline[n].p-1,countline[n].l);        for(i=0;i<countline[n].p;i++) printf("%4d ",countline[n].l[i]);        printf("\n");    }    return 0;} 2.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数，分解的质数个数最多算法：搜索+减枝 #include<stdio.h>#include<math.h>#include<string.h>#define SIZE 1000int best[SIZE],lenbest; /*当前最好的序列及长度*/int q[SIZE]; /*当前尝试*/ int x[SIZE]={2},lenx; /*质数表*/ int lenmax;int dfs(int now,int left,int count){    int i,j;    int tmp;    if(left==0)    {      if(count>lenbest)      {        memcpy(best,q,sizeof(best));        lenbest=count;      }      if(count==lenmax) return 1;      return 0;    }    for(i=now;i<lenx;i++)    {      if(left<x[i]) return 0;      tmp=left;      for(j=i;j<lenx;j++)      {        tmp-=x[j];        if(tmp<0) break;      }      if(count+j-i<=lenbest) return 0;      q[count]=x[i]; if(dfs(i+1,left-x[i],count+1)) return 1;    }    return 0;}int main(void){    int i,j,tmp;    int n;    while(scanf("%d",&n)!=EOF)    {        lenx=1;        memset(best,0,sizeof(best));        lenbest=0;        for(i=3;i<=n;i++)        {          tmp=sqrt(i);          for(j=2;j<=tmp;j++)            if(i%j==0) break;          if(j>tmp)          {            x[lenx]=i;            lenx++;          }        }        tmp=0; lenmax=0;        for(i=0;i<lenx;i++)        {          tmp+=x[i];          lenmax++;          if(tmp>n) { lenmax--; break; }          if(tmp==n) break;        }        dfs(0,n,0);        for(i=0;i<lenbest;i++) printf("%4d ",best[i]);        if(!lenbest) printf("No answer");        printf("\n");    }    return 0;} 3.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数，使之解为元素个数最多且在元素最多的前提下使最大元素最小算法：搜索+减枝 #include<stdio.h>#include<math.h>#include<string.h>#define SIZE 1000int best[SIZE],lenbest,great; /*当前最好的序列及长度*/int q[SIZE]; /*当前尝试*/ int x[SIZE]={2},lenx; /*质数表*/ int lenmax;int dfs(int now,int left,int count){    int i,j;    int tmp;    if(left==0)    {      if(count>lenbest || (count==lenbest && q[count-1]<great))      {        memcpy(best,q,sizeof(best));        lenbest=count;        great=q[count-1];      }      if(count==lenmax) return 0;      return 0;    }    for(i=now;i<lenx;i++)    {      if(left<x[i]) return 0;      tmp=left;      if(x[i]>great) return 0;      for(j=i;j<lenx;j++)      {        tmp-=x[j];        if(tmp<0) break;      }      if(count+j-i+1<=lenbest) return 0;      q[count]=x[i]; dfs(i+1,left-x[i],count+1);    }    return 0;}int main(void){    int i,j,tmp;    int n;    while(scanf("%d",&n)!=EOF)    {        lenx=1;        great=10000000;        memset(best,0,sizeof(best));        lenbest=0;        for(i=3;i<=n;i++)        {          tmp=sqrt(i);          for(j=2;j<=tmp;j++)            if(i%j==0) break;          if(j>tmp)          {            x[lenx]=i;            lenx++;          }        }        tmp=0; lenmax=0;        for(i=0;i<lenx;i++)        {          tmp+=x[i];          lenmax++;          if(tmp>n) { lenmax--; break; }          if(tmp==n) break;        }        dfs(0,n,0);        for(i=0;i<lenbest;i++) printf("%4d ",best[i]);        if(!lenbest) printf("No answer");        printf("\n");    }    return 0;}

评论