100分求救:一个算法

Question

在9～1这九个数字之间添加＋－×÷符号和括号，使结果等于2002？九个数字的前后顺序
不能变！希望能用程序表达出来,我想了想可能要到正则表达式吧,就是关于()的,可是我正则表达式不怎么想起来了(也可能不是用这个方法吧),谢谢

Answer 1

to  gogon() 
----------------
关键是算法，如果是试出来的，就没有多大意义。换一个数字，就要重新试

Answer 2

一个学长给C程序的算法
#include <stdio.h> 
int left[10],mid[10],right[10]; 
int value[10]; 
int iffound; 
int sum; void f(int n) 
{ 
int i,it; 
int flag1,flag2,exc1,exc2; if (n>1) 
{ 
  /* Choose 2 Number */ 
  for(i=1;i<n;i++) 
  { 
   /* 2 Number Locations */ 
   flag1=i; 
   flag2=i+1; 
   left[n]=value[flag1]; 
   right[n]=value[flag2]; 
   exc1=value[flag1]; 
   exc2=value[flag2];    /* 4 Kinds of Caculation */ 
   { 
    /* + */ 
    value[flag1]=value[flag1]+value[flag2]; 
    mid[n]=1; 
    for(it=flag2;it<=n-1;it++) 
     value[it]=value[it+1]; 
    /* Next N-1 */ 
    f(n-1); 
    /* Return Record */ 
    for(it=n;it>flag2;it--) 
     value[it]=value[it-1]; 
    value[flag2]=exc2; 
    value[flag1]=exc1; 
   } 
   { 
    /* - */ 
    value[flag1]=value[flag1]-value[flag2]; 
    mid[n]=2; 
    for(it=flag2;it<=n-1;it++) 
     value[it]=value[it+1]; 
    /* Next N-1 */ 
    f(n-1); 
    /* Return Record */ 
    for(it=n;it>flag2;it--) 
     value[it]=value[it-1]; 
    value[flag2]=exc2; 
    value[flag1]=exc1; 
   } 
   { 
    /* * */ 
    value[flag1]=value[flag1]*value[flag2]; 
    mid[n]=3; 
    for(it=flag2;it<=n-1;it++) 
     value[it]=value[it+1]; 
    /* Next N-1 */ 
    f(n-1); 
    /* Return Record */ 
    for(it=n;it>flag2;it--) 
     value[it]=value[it-1]; 
    value[flag2]=exc2; 
    value[flag1]=exc1; 
   } 
   { 
    /* / */ 
    if (value[flag2]!=0) 
    { 
    if (value[flag1]%value[flag2]==0) 
    { 
     value[flag1]=value[flag1]/value[flag2]; 
     mid[n]=4; 
     for(it=flag2;it<=n-1;it++) 
      value[it]=value[it+1]; 
     /* Next N-1 */ 
     f(n-1); 
     /* Return Record */ 
     for(it=n;it>flag2;it--) 
      value[it]=value[it-1]; 
     value[flag2]=exc2; 
     value[flag1]=exc1; 
    } 
    } 
   } 
  } 
} 
else 
{ 
  if (value[n]==sum) 
  { 
   iffound=iffound+1; 
   printf("FOUND the %ith Method!\n",iffound); 
   for(it=9;it>1;it--) 
   { 
    printf("%i",left[it]); 
    if (mid[it]==1) 
     printf("+"); 
    if (mid[it]==2) 
     printf("-"); 
    if (mid[it]==3) 
     printf("*"); 
    if (mid[it]==4) 
     printf("/"); 
    printf("%i\n",right[it]); 
   } 
  } 
} 
} 
void main() 
{ 
int i; printf("Input The Total Number(ex. 2002):"); 
scanf("%i",&sum); /* Initial */ 
for(i=9;i>=1;i--) 
  value[10-i]=i; iffound=0; f(9); if (iffound==0) 
  printf("No Found!\n"); 
}

Answer 3

优化：数字左右同时出现的括号没有意思，可以判断剔除
 
优化后：<(5*3)^7*5   <54296875次运算