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

79愛的鼓勵 1訂閱站台

強大的CN進化史 將呈列許多 ? 的作法

以下為最原始的生成組合+二分搜尋+插入排序

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

#include<stdio.h>        
#include<stdlib.h>        
int n,m;        
int different[1000000],input[50],top;        
int Search(int n,int L,int find[])        
{        
 int lower=0, mid, high=L-1;        
 int index=-1;        
    do   /*二分搜尋*/       
    {        
      mid=(lower+high)/2;        
      if(find[mid]<n)   lower=mid+1;        
      else if(find[mid]>n)   high=mid-1;        
      else   index=mid;        
    }        
    while(index==-1&&lower<=high);        
  return index;        
}        
void check(int data)        
{        
    int index=Search(data,top,different);        
    if(index==-1)        
       {        
          int a;        
          for(a=top-1;a>=0;a--)        
             if(data<different[a])
                different[a+1]=different[a];
             else break; 
          different[a+1]=data;      
          top++;
       }        
}        
void make (int now,int a,int n,int SUM)        
{        
  int b=a;        
  if(now>1)        
     check(SUM);         
           
  for(b=a;b<=n;b++)        
       make(now+1,b+1,n,SUM+input[b]);        
     
}        
main()        
{          
 while(scanf("%d",&n)==1)        
    {        
       int a,b,c;        
       for(a=1;a<=n;a++)        
           scanf("%d",&input[a]);        
       for(a=1;a<=n;a++)           
          {           
            c=a;           
            for(b=a+1;b<=n;b++)           
                if(input[b]<input[c]) c=b;           
            int temp;        
            temp=input[a];        
            input[a]=input[c];        
            input[c]=temp;        
          }         
       top=0;        
       make(1,1,n,0);        
       for(a=0;a<top;a++)  different[a]=0;        
       printf("%d\n",top);        
    }        
 return 0;           
}

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

以下程式碼為 a13032002 提供的DP想法

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

#include<stdio.h>        
#include<stdlib.h>        
int n,m;        
int different[1000000]={0},input[50],top;        
int Search(int n,int L)        
{        
 int lower=0, mid, high=L-1;        
 int index=-1;        
    do   /*二分搜尋*/       
    {        
      mid=(lower+high)/2;        
      if(different[mid]<n)   lower=mid+1;        
      else if(different[mid]>n)   high=mid-1;        
      else   index=mid;        
    }        
    while(index==-1&&lower<=high);        
  return index;        
}        
void check(int data)        
{        
    int index=Search(data,top);  
    if(index==-1)        
       {        
          int a;        
          for(a=top-1;a>=0;a--)        
             if(data<different[a])
                different[a+1]=different[a];
             else break; 
          different[a+1]=data;      
          top++;
       }        
}        
main()        
{          
 while(scanf("%d",&n)==1)        
    {        
       int a,b,c;
       top=1;
       for(a=1;a<=n;a++)
           {
              scanf("%d",&input[a]);        
              int M=top,NEW[50000],Ntop=0;
              for(b=0;b<M;b++)
                 NEW[Ntop++]=different[b]+input[a];
              for(b=0;b<M;b++)
                 check(NEW[b]);
           }
       printf("%d\n",top-1);        
    }        
 return 0;           
}

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

以下作法  利用二元搜尋樹 代替二分搜尋+插入排序

但由於生成出來的數長得不好  所以速度小於上面的

(此時未習得平衡)

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

#include<stdio.h>        
#include<stdlib.h>        
int n,m;
int link[50000][2]={0},NUM[50000]={0},top;
void Tree(int now,int value)
{
    if(value>NUM[now])
      {
         if(link[now][1]==0)
            link[now][1]=++top,NUM[top]=value;
         else
            Tree(link[now][1],value);
      }
    else if(value<NUM[now])
      {
         if(link[now][0]==0)
            link[now][0]=++top,NUM[top]=value;
         else
            Tree(link[now][0],value);
      }
}
main()        
{          
 while(scanf("%d",&n)==1)        
    {        
       int a,b,c,M;      
       for(a=0;a<top;a++)
          link[a][0]=0,link[a][1]=0,NUM[a]=0;
       top=1;
       for(a=1;a<=n;a++)
           {
              scanf("%d",&m);        
              M=top;
              for(b=1;b<=M;b++)
                 Tree(1,m+NUM[b]);
           }
       printf("%d\n",top-1);

    }        
 return 0;           
}

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

習得平衡之後 速度成為之中最快的28 ms 但是仍比HASH慢...

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

#include<stdio.h>        
#include<stdlib.h>        
int n,m;
int link[50000][2]={0},NUM[50000]={0},top,MAX;
void Tree(int now,int value,int L)
{
    if(MAX<L) MAX=L;
    if(value>NUM[now])
      {
         if(link[now][1]==0)
            link[now][1]=++top,NUM[top]=value;
         else
            Tree(link[now][1],value,L+1);
      }
    else if(value<NUM[now])
      {
         if(link[now][0]==0)
            link[now][0]=++top,NUM[top]=value;
         else
            Tree(link[now][0],value,L+1);
      }
}
int s[50000],stop=0;
void treesort(int now)
{
   if(link[now][0]!=0) treesort(link[now][0]);
   s[stop++]=NUM[now];
   if(link[now][1]!=0) treesort(link[now][1]);
}
void putin(int l,int h,int flag)
{
   if(l>h) return;
   int m=(l+h)/2;
   if(flag==1) NUM[1]=s[m];
   else  Tree(1,s[m],0);
   putin(l,m-1,0);
   putin(m+1,h,0);
}
void balance()
{
   stop=0,top=1;
   treesort(1);
   int a;
   for(a=0;a<=stop;a++) link[a][0]=0,link[a][1]=0,NUM[a]=0;
   putin(0,stop-1,1);
}
main()        
{          
 while(scanf("%d",&n)==1)        
    {        
       int a,b,c,M;      
       for(a=0;a<top;a++)
          link[a][0]=0,link[a][1]=0,NUM[a]=0;
       top=1;
       for(a=1;a<=n;a++)
           {
              scanf("%d",&m);        
              M=top,MAX=0;
              for(b=1;b<=M;b++)
                 Tree(1,m+NUM[b],0);
              if(MAX>50) balance();
           }
       printf("%d\n",top-1);
    }        
 return 0;           
}