摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法: 建表+DFS

程式碼1的速度<程式碼2的速度

但速度仍然不夠快

/*************************************************************/

#include<stdio.h>
#include<stdlib.h>
int gcd(int a,int b)           
{           
  int temp;           
  while(a%b)                 
   {                 
     temp=a;                 
     a=b;                 
     b=temp%b;                            
   }
   return b;           
}
int line[101]={0},GCD[101][101]={0};
int n,m;
void DFS (int now,int sum,int a)
{
   int b;
   if(now==m&&sum==n)
     {
        for(b=0;b<m-1;b++) printf("%d ",line[b]);
        printf("%d",line[b]);
        printf("\n");
        return;
     }
   if(sum>=n) return;
   for(a=a;a<=n-sum;a++)
      {
         for(b=0;b<now;b++)
             if(GCD[line[b]][a]!=1) break;
         if(b==now&&n-sum>=a)
            {
              line[now]=a;
              DFS (now+1,sum+a ,a);
            }
      }
}
main()
{
 int a,b;
 for(a=1;a<=100;a++)
    for(b=1;b<=100;b++)
       GCD[a][b]=gcd(a,b);
 int t,time=1;
 while(scanf("%d",&t)==1)
 while(t--)
    {
      scanf("%d %d",&n,&m);
      printf("Case %d:\n",time++);
      DFS (0,0,1);
    }
 return 0;
}
/***************************************/

#include<stdio.h>
#include<stdlib.h>
int ppt[101][10]={0},top[101]={0};  
int prime()  
{  
  int a,b;  
  ppt[1][0]=1;
 for(a=2;a<101;a++)     
      if(top[a]==0)     
         for(b=1;a*b<=101;b++)
            ppt[a*b][top[a*b]++]=a;     
}
int line[101]={0},appear[101]={0};
int n,m;
void DFS (int now,int sum,int a,int flag)
{
   int b;
   if(now==m&&sum==n)
     {
        for(b=0;b<m-1;b++) printf("%d ",line[b]);
        printf("%d",line[b]);
        printf("\n");
        return;
     }
   if(sum>=n) return;
   for(a=a;a<=n-sum;a++)
      {
         if(flag==1&&a%2==0) continue;
         int find=0;
         for(b=0;b<top[a];b++)
             if(appear[ppt[a][b]]==1) {find=1;break;}
         if(find==0)
            {
              line[now]=a;
              appear[ppt[a][0]]=1;appear[ppt[a][1]]=1;appear[ppt[a][2]]=1;appear[ppt[a][3]]=1;
              DFS (now+1,sum+a ,a+(a!=1),(a%2==0));
              appear[ppt[a][0]]=0;appear[ppt[a][1]]=0;appear[ppt[a][2]]=0;appear[ppt[a][3]]=0;
            }
      }
}
main()
{
 int a,b;
 int t;
 prime();
 while(scanf("%d",&t)==1)
 {
   int time=1;
    while(t--)
       {
         scanf("%d %d",&n,&m);
         printf("Case %d:\n",time++);
         DFS (0,0,1,0);
       }
 } 
 return 0;
}