站内搜索

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

原帖及讨论: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 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;
}

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;
}

 

  • 上一篇:关于for结构中省略表达式的论文
  • 下一篇:abs、 labs的返回值分别为int和long是很不恬当的!。。。