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

79愛的鼓勵 1訂閱站台

作法:DFS搜尋所有可能

想法:複製完,一定是接貼上,及早達到星星的數目,之後一大於最小次數就退回

2009/7/14更新 由於zhouyuchen寫的超快,以至於產生新的做法

不過感謝zhouyuchen提供想法(雖然看不懂)

第2程式碼為DFS+倍數判斷(速度為第1程式碼的40倍)

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

#include<stdio.h>
#include<stdlib.h>
char way[2000][10000]={0};
int n,min,top;
int temp[10000]={0};
int num[25]={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};
void DFS(int sum,int many,int ctrlC,int ctrlV)
{
  if(sum==n&&min>=many)
    {
     int a;
     if(min==many)
      {
       top++;
       for(a=0;a<=many;a++) way[top][a]=temp[a];
      }
     else
      {
       top=0;
       for(a=0;a<=many;a++) way[top][a]=temp[a];
      }
     min=many;
    }
  if(many>=min||sum>n) return;
  if(ctrlC==1)/*複製過的話 一定是接貼上*/
   {
     temp[many+1]=2;
     DFS(sum+ctrlV,many+1,0,ctrlV);
   } 
  else
   {
     temp[many+1]=1;
     DFS(sum,many+1,1,sum);   
     temp[many+1]=2;
     DFS(sum+ctrlV,many+1,0,ctrlV);
   }
}
main()
{
 int a,b;
 while(scanf("%d",&n)==1)
   {
    int find=0;
    for(a=0;a<25&&num[a]<n;a++)
     if(n%num[a]==0) {find=1;break;}
     if(find==1)
     {
      min=2147483647;
      DFS(1,1,1,1);
      printf("min : %d\n",min);
      printf("way : %d\n",top+1);
      for(b=0;b<=top;b++)
       {
          printf("Ctrl C + ");
          for(a=2;a<min;a++)
             if(way[b][a]==1) printf("C + ");
             else if(way[b][a]==2) printf("V + ");
          if(way[b][a]==1) printf("C");
          else if(way[b][a]==2) printf("V");
          printf("\n");
       }  
      } 
     else
      {
       printf("min : %d\n",n);
       printf("way : %d\n",1);
       printf("Ctrl C + ");
       for(a=2;a<n;a++)
          printf("V + ");
       printf("V");  
          printf("\n");
      }
      
   }
 return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
char way[2000][10000]={0};
int n,min,top;
int temp[10000]={0};
void DFS(int sum,int many,int ctrlC,int ctrlV)
{
  if(sum==n&&min>=many)
    {
     int a;
     if(min==many)
      {
       top++;
       for(a=0;a<=many;a++) way[top][a]=temp[a];
      }
     else
      {
       top=0;
       for(a=0;a<=many;a++) way[top][a]=temp[a];
      }
     min=many;
    }
  if(many>=min||sum>=n) return;
  if(ctrlC==1)/*複製過的話 一定是接貼上*/
   {
     temp[many+1]=2;
     DFS(sum+ctrlV,many+1,0,ctrlV);
   } 
  else
   {
     if(n%sum==0)
     {
      temp[many+1]=1;
      DFS(sum,many+1,1,sum);  
     }
     temp[many+1]=2;
     DFS(sum+ctrlV,many+1,0,ctrlV);
   }
}
main()
{
 int a,b;
 while(scanf("%d",&n)==1)
   {

      min=2147483647;
      DFS(1,1,1,1);
      printf("min : %d\n",min);
      printf("way : %d\n",top+1);
      for(b=0;b<=top;b++)
       {
          printf("Ctrl C + ");
          for(a=2;a<min;a++)
             if(way[b][a]==1) printf("C + ");
             else if(way[b][a]==2) printf("V + ");
          if(way[b][a]==1) printf("C");
          else if(way[b][a]==2) printf("V");
          printf("\n");
      } 

   }
 return 0;
}