合数分解质数之和较好的解法 - C语言论坛

楼主

问题点数：0 回复次数：12

合数分解质数之和较好的解法

算法思想,搜索+较强减枝.
小于5000的数据,可于瞬间出解,且保证解的准确性,若无解则输出No answer

程序代码：

/*
Author: SunKai
E-mail: sunkai [at] msn [dot] com
*/

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

程序二,经过本帖在11楼前的讨论,对于程序进行了修改,使之解为元素个数最多且最大元素最小

程序代码：

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

[[it] 本帖最后由卧龙孔明于 2008-4-12 17:45 编辑 [/it]]

搜索更多相关主题的帖子: int　合数　质数　解法　之和　

第 2 楼

得分:0

这个程序对于1998的解:
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59
61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 149
原帖链接:https://bbs.bccn.net/thread-208474-1-1.html

[[it] 本帖最后由卧龙孔明于 2008-4-12 16:55 编辑 [/it]]

My Blog: www.aiexp.info
虽然我的路是从这里开始的,但是这里不再是乐土.感谢曾经影响过，引导过，帮助过我的董凯,飞燕,leeco,starwing,Rockcarry,soft_wind等等等等.别了,BCCN.

第 3 楼

得分:0

ls的算法不能保证有解的一定出解,也就是可能对于一些数据死循环出不来

第 4 楼

得分:0

我的算法主要就是搜索,枚举每一种情况肯定超时严重,因此加了几条很管用的减枝

第 5 楼

得分:0

[bo]以下是引用 [un]qitian[/un] 在 2008-4-12 17:24 的发言：[/bo]

对n=1998来说的，它可以分解成以下数据。这是标准答案
3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 131 137 139

事物的正确答案不只是一个,您可以验证一下我的答案,同样是正确的

第 6 楼

得分:0

[bo]以下是引用 [un]qitian[/un] 在 2008-4-12 17:32 的发言：[/bo]

你的答案是不符合最小要求的。

不是要求分为最多个吗(对于1998最多可分为32个质数)?难道我看错题的要求了

第 7 楼

得分:0

如果按照11#,那您等一下,我马上改一下

第 8 楼

得分:0

程序代码：

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

这样代码能稍慢一些,约为1s

第 9 楼

得分:0

优化了一下,更快

程序代码：

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

第 10 楼

得分:0

程序二的结果:

程序代码：

1998:
   3    5    7   11   13   17   19   23   29   31   37   41   43   47   53   59
  61   67   71   73   79   83   89   97  101  103  107  109  113  131  137  139

2008:
   2    3    5    7   11   13   17   19   23   29   31   37   41   43   47   53
  59   61   67   71   73   79   83   89   97  101  103  107  109  113  127  139

 149