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

79愛的鼓勵 1訂閱站台

作法 : 暴力DFS (一堆for)

這題尚未確定是正確的...

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

#include<stdio.h>
#include<stdlib.h>
int n,a;
int num[20];
int tol[20];
int GCD(int a,int b)              
{              
  int temp;              
  while(a%b)                    
   {                    
     temp=a;                    
     a=b;                    
     b=temp%b;                               
   }  
   return b;              
}  
void DFS (int now)
{
   int a;
   
   if(now==n-1)
     {
       int value[20][2]={0},top=1;
       value[0][0]=num[0];
        for(a=0;a<n;a++)  value[a][1]=1;
       printf("%d",num[0]);
        for(a=0;a<n-1;a++)
           {
             if(tol[a]==1)
                {
                 value[top++][0]=num[a+1];
                 putchar(' ');putchar('+');putchar(' ');
                }
             if(tol[a]==2)
                {
                 value[top++][0]=num[a+1]*-1;
                 putchar(' ');putchar('-');putchar(' ');
                }
             if(tol[a]==3)
                {
                 value[top-1][0]*=num[a+1];
                 int g=GCD(value[top-1][1],abs(value[top-1][0]));
                 value[top-1][1]/=g;
                 value[top-1][0]/=g;
                 putchar(' ');putchar('*');putchar(' ');
                }
             if(tol[a]==4)
                {
                 value[top-1][1]*=num[a+1];
                 int g=GCD(value[top-1][1],abs(value[top-1][0]));
                 value[top-1][1]/=g;
                 value[top-1][0]/=g;
                 putchar(' ');putchar('/');putchar(' ');
                }
             printf("%d",num[a+1]);
           } 
        int sum=0,lcm=1;
        for(a=0;a<top;a++)
             lcm=lcm*abs(value[a][1])/GCD(abs(value[a][1]),lcm);
        for(a=0;a<top;a++)
             value[a][0]=lcm/abs(value[a][1])*value[a][0];
        for(a=0;a<top;a++)
             sum+=value[a][0];
        if(sum%lcm==0)
         printf(" = %d\n",sum/lcm);
        else
         { 
           putchar(' ');putchar('=');putchar(' ');
            if(sum<0) {sum=sum*-1;putchar('-');}
            int g=GCD(sum,lcm);
            sum/=g;
            lcm/=g;
            
            printf("%d/%d\n",sum,lcm);
         }
     } 
   else
   for(a=1;a<=4;a++)
      {
       tol[now]=a; 
       DFS(now+1);
      }
}
main()
{
 /* freopen("in.txt", "rt", stdin);
 freopen("output.txt", "w+t", stdout); */
  while(scanf("%d",&n)==1&&n!=0)
      {
         for(a=0;a<n;a++)
            scanf("%d",&num[a]);
         DFS(0);
      }
 return 0;
}