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