回复 10# 的帖子
你的答案是不符合最小要求的。 ----------------解决方案--------------------------------------------------------
[bo]以下是引用 [un]qitian[/un] 在 2008-4-12 17:32 的发言：[/bo]
你的答案是不符合最小要求的。
你的答案是不符合最小要求的。
不是要求分为最多个吗(对于1998最多可分为32个质数)?难道我看错题的要求了
----------------解决方案--------------------------------------------------------
如果按照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;
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
----------------解决方案--------------------------------------------------------
优化了一下,更快
程序代码：
#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;
}
----------------解决方案--------------------------------------------------------
程序二的结果:
程序代码：
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
----------------解决方案--------------------------------------------------------
若输入数据大于5000,请将
#define SIZE 1000
改为
#define SIZE 10000
或更大
----------------解决方案--------------------------------------------------------
回复 16# 的帖子
对2008不太对，只是要求这些质数尽可能取值小且不同，不用考虑最多的个数。2008的结果应是：
2008 = 2 5 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 113 127 131 137 139
----------------解决方案--------------------------------------------------------
是这样啊～～～
题意又理解错了
再等一下，一会发代码
----------------解决方案--------------------------------------------------------
２００８：
2 3 5 7 11 13 17 19 23 29 37 43 53 59 61 67
71 73 79 83 89 97 101 103 107 109 113 127 131 137 139
结果虽然出来了，但是由于我一开始理解题意与实际题意相差甚远，原算法模型对实际题意不适应,因此此算法模型效率不太高，有时间我按照这个题意重新构造算法模型，因此最后这个代码就不帖了
[[it] 本帖最后由 卧龙孔明 于 2008-4-12 18:13 编辑 [/it]]
----------------解决方案--------------------------------------------------------