首页新闻手机家电数码电脑财经大模型直播

合数分解成质数之和问题探究

来源：编程中国作者：若水 2008-04-16/15:44

软件频道

编程学院

C/C++/VC

入门教程

正文

1.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数，且它们中最大的质数最小
算法：DP,背包问题，复杂度约为O( (N/10)^2 )

#include<stdio.h>
#include<string.h>
#include<math.h>
#define SIZE 5000
#define SIZELINE 20000
int 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;
}

#p#分页标题#e#

2.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数，分解的质数个数最多
算法：搜索+减枝

#include<stdio.h>
#include<math.h>
#include<string.h>
#define SIZE 1000
int 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 1000
int 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;
}

#p#分页标题#e#

{{cmoun}}人已赞

评论 {{userinfo.comments}}