零度资讯 - 文章、资讯、攻略、教程随你看!
您的位置:零度软件下载程序设计C&C++ → 合数分解成质数之和问题探究

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

发表时间:09-04-23     作者:佚名     阅读:次     评论:0字体大小:A- A+

本文导读:1.将一个合数分解成多个质数,使分解的各个质数均不等、它们的和等于该合数,且它们中最大的质数最小 算法:DP,背包问题,复杂度约为O( (N/10)^2 ) #include<stdio.h> #include<string.h> #include<math.h> #define ..
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&n

阅读本文后您有什么感想? 已有 1 人给出评价!

  • 0

    欢迎
  • 0

    白痴
  • 0

    拜托
  • 0

    惊讶
  • 0

    加油
  • 0

    鄙视
相关资讯
    没有数据
相关软件
最新评论
我要抢沙发
(您的评论需要经过审核才能显示)0人参与,0条评论
140

零度软件 - 所有软件均来自网络如有版权问题请联系我们 - 蜀ICP备 05031544号
Copyright © 2004-2016 www.05sun.com online services. All rights reserved.