请大家来看一下数字游戏算法，来者有分，非资深者也多多来学习csdn上真正的高手，一定受益非浅!
任给七个操作数字和一个理想目标数字，要求运用“+”，“-”，“X”，“/"，以及"(",
")"将七个数字进行组合，要求所得的结果尽量的接收理想目标数字。
要求：
1。所有输入数据均为整数，所有的运算中间数也均为整数，即：2/4式不合法的。
2。前七个操作数字均大于1小于100,理想目标数字大于1小于5000.
3。如若不能准确的得到理想目标数，则应使运算结果尽量的接进理想目标数。
4。所需数据从"input.txt"文件读取，运算结果输出到"output.txt"文件
例如：
输入文件”input.txt"格式如下：
1 2 3 4 5 7 295
输入文件“output.txt"格式如下：
(1+(4/2)*#+6*7)*5
大家看清楚了，这是很有挑战的课题哦!(最好是使用c,c++,pascal,工具不限)实在不能做提提思想也好!
问题点数：0、回复次数：17Top
1 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-06-04 00:29:01 得分 0
这个不是.......程序员杂志上的某一期擂台题目吗？动态规划的说。看一下杂志吧，我当时也没想出来。Top
2 楼mmmcd（超超）回复于 2003-06-04 00:36:50 得分 0
7!=5040
能不能全排列穷举一下,然后按照ACM/ICPC2002西安交大第一题的思路.
Top
3 楼xiaojun520（TECHIE）回复于 2003-06-04 00:40:34 得分 0
看起来，倒是停麻烦的！
Top
4 楼makefriend7（小顽童）回复于 2003-06-04 01:14:22 得分 0
第一题的思路？？
啊！不记得当时的题目了！Top
5 楼makefriend7（小顽童）回复于 2003-06-04 01:16:08 得分 0
穷举或许行吧！Top
6 楼dingopeter（Peter）回复于 2003-06-04 02:04:51 得分 0
不可能穷举，7!显然不够。你没有考虑4种运算以及运算顺序啊！还有整除的问题。
我认为可以这样：
1、在7个数中找出所以可以整除的数的组合。要考虑这种情况：4/8不是整数，6/8也不是整数，但4*6/8就是整数了。所以要因式分解。
2、用整除的数的组合替代原来的项目。这时，可用的项目将少于7个。对这些项目做+、-或*，但没有/。
3、用不同的组合方式生成不同的项目群。反复试验，直到找到合适的解。
我觉得这样应该比盲目地穷举更可行，也更有效率一些。Top
7 楼mathe（）回复于 2003-06-04 08:27:11 得分 0
DP
参考
http://members.lycos.co.uk/huidu/club/club.php?bbsid=5aa61ff26e911e12Top
8 楼mathe（）回复于 2003-06-04 08:28:27 得分 0
不过7个数穷举问题也不是很大，现在的计算机基本上差不多。8个数可能就比较麻烦了。Top
9 楼zlf_jack（风云剑客）回复于 2003-06-04 10:45:34 得分 0
up一下，等毕业设计完了再做做！Top
10 楼mmmcd（超超）回复于 2003-06-04 12:53:02 得分 0
我翻出了一个去年编的,疯狂穷举表达式和操作数的程序:
#include <stdio.h>
FILE *fp;
int list[20],error=0,answer=0;
char op[]={'*','-','+','/'};
int n,num[11];
struct a{int n;int m;}
numSequense[11];
float result,TreeValue;
typedef struct Tnode{
char op;
int num;
struct Tnode *lc;
struct Tnode *rc;}Tnode,*Tree;
Tree p[10];
void output();
void CreateNumber();
void DeleteNumber();
void CNS();
float Value();
int key1(int a,int b)
{int i;
if(a==0&&b==0)return(1);
for(i=0;i<b;i++)if(a==numSequense[i].m)return(0);
return(1);
}
void CNS(int k)
{int i;
if(k<n+1)
for(i=0;i<n+1;i++)
{if(key1(i,k)){
numSequense[k].n=num[i];numSequense[k].m=i;
CNS(k+1);
numSequense[k].n=0;numSequense[k].m=0;}}
else CreateNumber();
}
void CreateOperator(int k)
{int j;
if(k<n)for(j=0;j<4;j++)
{p[k]->op=op[j];CreateOperator(k+1);}
else {CNS(0);error=0;}
}
void CreateNumber()
{int i,j=0;
for(i=0;i<n;i++)
{if(!p[i]->lc)
{p[i]->lc=(Tree)malloc(sizeof(Tnode));
p[i]->lc->op=' ';
p[i]->lc->rc=p[i]->lc->lc=NULL;
p[i]->lc->num=numSequense[j++].n;}
if(!p[i]->rc)
{p[i]->rc=(Tree)malloc(sizeof(Tnode));
p[i]->rc->num=numSequense[j++].n;
p[i]->rc->op=' ';
p[i]->rc->rc=p[i]->rc->lc=NULL;}
}
TreeValue=Value(p[0]);
if(error==0&&TreeValue==result)
{output(p[0]);fprintf(fp,"=%.2f\n",TreeValue);answer=1;}
DeleteNumber();
}
void DeleteNumber()
{int i;
for(i=0;i<n;i++)
{if(p[i]->lc)if(p[i]->lc->op==' ')
{free(p[i]->lc);p[i]->lc=NULL;}
if(p[i]->rc)if(p[i]->rc->op==' ')
{free(p[i]->rc);p[i]->rc=NULL;}
}
}
float Calculate(float a,char c,float b)
{if(c=='+')return(a+b);
if(c=='-')return(a-b);
if(c=='*')return(a*b);
if(c=='/')if(b!=0.0)return(a/b);else{error=1;return(0.0);}
}
float Value(Tree T)
{if(T->op==' ')return(T->num);
else return(Calculate(Value(T->lc),T->op,Value(T->rc)));
}
void output(Tree T)
{if(T->op!=' ')
{if(T->lc)
if((T->op=='*'||T->op=='/')&&(T->lc->op=='+'||T->lc->op=='-'))
{fprintf(fp,"(");output(T->lc);fprintf(fp,")");}else output(T->lc);
fprintf(fp,"%c",T->op);
if(T->rc)
if((T->op=='*'||T->op=='/')&&(T->rc->op=='+'||T->rc->op=='-')||((T->op=='/')&&
(T->rc->op!=' '))||(T->op=='-'&&(T->rc->op=='+'||T->rc->op=='-')))
{fprintf(fp,"(");output(T->rc);fprintf(fp,")");}else output(T->rc);
}
else fprintf(fp,"%d",T->num);
}
void CreateTree()
{int i,j=0,k=0;
for(i=0;i<2*n;i++)
{if(list[i]==1){
p[j]=(Tree)malloc(sizeof(Tnode));
p[j]->op=' ';p[j]->num=0;
p[j]->rc=p[j]->lc=NULL;
if(i>0){if(list[i-1]==1)p[k]->lc=p[j];
else p[k]->rc=p[j];
k=j;j++;}else j++;}
else if(list[i-1]==0)k--;
}
CreateOperator(0);
}
main(){
int i,i0,i1,j,step,k=0;
fp=fopen("out.txt","w");
do {printf("please input the total number of the members(2--7):");
scanf("%d",&n);}
while(n<2||n>7);
printf("The result you want(number):");scanf("%f",&result);
printf("Please input %d numbers:",n);
for(i=0;i<n;i++){scanf("%d",&num[i]);numSequense[i].n=numSequense[i].m=0;}
n--;i=0;i1=0;i0=0;step=1;
while(i>=0){
list[i]=step;
if(list[i]==1)i1++;
else if(list[i]==0) i0++;
if(i1==n){
for(j=i+1;j<2*n;j++){
list[j]=0;
}
k++;
if(k<=n)CreateTree();
step=list[i]-1;
if(list[i]==1)i1--;
else i0--;
}
else if(i1<i0){
while(list[i]==0){
i--;
if(list[i+1]==1)i1--;
else i0--;}
step=list[i]-1;
i1--;
}else {
i++;
step=1;
}
}
if(!answer)printf("Sorry,no answer.\n");
else printf("OK!!\n");
}
Top
11 楼mmmcd（超超）回复于 2003-06-04 12:53:15 得分 0
结果:(输入6 259 1 2 3 4 5 7,运行13秒,很多重复)
(4*5*2-3)*7*1=259.00
(5*4*2-3)*7*1=259.00
(2*5*4-3)*7*1=259.00
(5*2*4-3)*7*1=259.00
(2*4*5-3)*7*1=259.00
(4*2*5-3)*7*1=259.00
(4*5*2-3)*1*7=259.00
(5*4*2-3)*1*7=259.00
(2*5*4-3)*1*7=259.00
(5*2*4-3)*1*7=259.00
(2*4*5-3)*1*7=259.00
(4*2*5-3)*1*7=259.00
((3+4)*5+2)*7*1=259.00
((4+3)*5+2)*7*1=259.00
((3+4)*5+2)*1*7=259.00
((4+3)*5+2)*1*7=259.00
(4*5*2*1-3)*7=259.00
(5*4*2*1-3)*7=259.00
(2*5*4*1-3)*7=259.00
(5*2*4*1-3)*7=259.00
(2*4*5*1-3)*7=259.00
(4*2*5*1-3)*7=259.00
(4*5*1*2-3)*7=259.00
(5*4*1*2-3)*7=259.00
(1*5*4*2-3)*7=259.00
(5*1*4*2-3)*7=259.00
(1*4*5*2-3)*7=259.00
(4*1*5*2-3)*7=259.00
(2*5*1*4-3)*7=259.00
(5*2*1*4-3)*7=259.00
(1*5*2*4-3)*7=259.00
(5*1*2*4-3)*7=259.00
(1*2*5*4-3)*7=259.00
(2*1*5*4-3)*7=259.00
(2*4*1*5-3)*7=259.00
(4*2*1*5-3)*7=259.00
(1*4*2*5-3)*7=259.00
(4*1*2*5-3)*7=259.00
(1*2*4*5-3)*7=259.00
(2*1*4*5-3)*7=259.00
(5/1*4*2-3)*7=259.00
(4/1*5*2-3)*7=259.00
(5/1*2*4-3)*7=259.00
(2/1*5*4-3)*7=259.00
(4/1*2*5-3)*7=259.00
(2/1*4*5-3)*7=259.00
((3*5+4)*2-1)*7=259.00
((5*3+4)*2-1)*7=259.00
(4*5/1*2-3)*7=259.00
(5*4/1*2-3)*7=259.00
(2*5/1*4-3)*7=259.00
(5*2/1*4-3)*7=259.00
(2*4/1*5-3)*7=259.00
(4*2/1*5-3)*7=259.00
(4*5*2/1-3)*7=259.00
(5*4*2/1-3)*7=259.00
(2*5*4/1-3)*7=259.00
(5*2*4/1-3)*7=259.00
(2*4*5/1-3)*7=259.00
(4*2*5/1-3)*7=259.00
((5-2)*4*3+1)*7=259.00
((5-2)*3*4+1)*7=259.00
((3+4)*5*1+2)*7=259.00
((4+3)*5*1+2)*7=259.00
((3+4)*1*5+2)*7=259.00
((4+3)*1*5+2)*7=259.00
((1+3)*4*2+5)*7=259.00
((3+1)*4*2+5)*7=259.00
((1+3)*2*4+5)*7=259.00
((3+1)*2*4+5)*7=259.00
((1*4+3)*5+2)*7=259.00
((4*1+3)*5+2)*7=259.00
((1*3+4)*5+2)*7=259.00
((3*1+4)*5+2)*7=259.00
((2*5+1)*3+4)*7=259.00
((5*2+1)*3+4)*7=259.00
((4/1+3)*5+2)*7=259.00
((3/1+4)*5+2)*7=259.00
((3+4)/1*5+2)*7=259.00
((4+3)/1*5+2)*7=259.00
((3+4)*5/1+2)*7=259.00
((4+3)*5/1+2)*7=259.00
(4*5*2-3)/1*7=259.00
(5*4*2-3)/1*7=259.00
(2*5*4-3)/1*7=259.00
(5*2*4-3)/1*7=259.00
(2*4*5-3)/1*7=259.00
(4*2*5-3)/1*7=259.00
((3+4)*5+2)/1*7=259.00
((4+3)*5+2)/1*7=259.00
(2*3+7)*5*4-1=259.00
(3*2+7)*5*4-1=259.00
(2*3+7)*4*5-1=259.00
(3*2+7)*4*5-1=259.00
(4*5*2-3)*7/1=259.00
(5*4*2-3)*7/1=259.00
(2*5*4-3)*7/1=259.00
(5*2*4-3)*7/1=259.00
(2*4*5-3)*7/1=259.00
(4*2*5-3)*7/1=259.00
((3+4)*5+2)*7/1=259.00
((4+3)*5+2)*7/1=259.00
(2*4*5-3)*7*1=259.00
(2*5*4-3)*7*1=259.00
(4*2*5-3)*7*1=259.00
(4*5*2-3)*7*1=259.00
(5*2*4-3)*7*1=259.00
(5*4*2-3)*7*1=259.00
(2*4*5-3)*1*7=259.00
(2*5*4-3)*1*7=259.00
(4*2*5-3)*1*7=259.00
(4*5*2-3)*1*7=259.00
(5*2*4-3)*1*7=259.00
(5*4*2-3)*1*7=259.00
(5*(3+4)+2)*7*1=259.00
(5*(4+3)+2)*7*1=259.00
(5*(3+4)+2)*1*7=259.00
(5*(4+3)+2)*1*7=259.00
(2*4*5*1-3)*7=259.00
(2*5*4*1-3)*7=259.00
(4*2*5*1-3)*7=259.00
(4*5*2*1-3)*7=259.00
(5*2*4*1-3)*7=259.00
(5*4*2*1-3)*7=259.00
(1*4*5*2-3)*7=259.00
(1*5*4*2-3)*7=259.00
(4*1*5*2-3)*7=259.00
(4*5*1*2-3)*7=259.00
(5*1*4*2-3)*7=259.00
(5*4*1*2-3)*7=259.00
(1*2*5*4-3)*7=259.00
(1*5*2*4-3)*7=259.00
(2*1*5*4-3)*7=259.00
(2*5*1*4-3)*7=259.00
(5*1*2*4-3)*7=259.00
(5*2*1*4-3)*7=259.00
(1*2*4*5-3)*7=259.00
(1*4*2*5-3)*7=259.00
(2*1*4*5-3)*7=259.00
(2*4*1*5-3)*7=259.00
(4*1*2*5-3)*7=259.00
(4*2*1*5-3)*7=259.00
(4*5/1*2-3)*7=259.00
(5*4/1*2-3)*7=259.00
(2*5/1*4-3)*7=259.00
(5*2/1*4-3)*7=259.00
(2*4/1*5-3)*7=259.00
(4*2/1*5-3)*7=259.00
((4+3*5)*2-1)*7=259.00
((4+5*3)*2-1)*7=259.00
(4/(1/5)*2-3)*7=259.00
(5/(1/4)*2-3)*7=259.00
(2/(1/5)*4-3)*7=259.00
(5/(1/2)*4-3)*7=259.00
(2/(1/4)*5-3)*7=259.00
(4/(1/2)*5-3)*7=259.00
(2*4*5/1-3)*7=259.00
(2*5*4/1-3)*7=259.00
(4*2*5/1-3)*7=259.00
(4*5*2/1-3)*7=259.00
(5*2*4/1-3)*7=259.00
(5*4*2/1-3)*7=259.00
(4*(5-2)*3+1)*7=259.00
(3*(5-2)*4+1)*7=259.00
(5*(3+4)*1+2)*7=259.00
(5*(4+3)*1+2)*7=259.00
Top
12 楼mmmcd（超超）回复于 2003-06-04 12:53:34 得分 0
(1*(3+4)*5+2)*7=259.00
(1*(4+3)*5+2)*7=259.00
(4*(1+3)*2+5)*7=259.00
(4*(3+1)*2+5)*7=259.00
(2*(1+3)*4+5)*7=259.00
(2*(3+1)*4+5)*7=259.00
((3+1*4)*5+2)*7=259.00
((3+4*1)*5+2)*7=259.00
((4+1*3)*5+2)*7=259.00
((4+3*1)*5+2)*7=259.00
((1+2*5)*3+4)*7=259.00
((1+5*2)*3+4)*7=259.00
((3+4/1)*5+2)*7=259.00
((4+3/1)*5+2)*7=259.00
(5*(3+4)/1+2)*7=259.00
(5*(4+3)/1+2)*7=259.00
(2*4*5-3)/1*7=259.00
(2*5*4-3)/1*7=259.00
(4*2*5-3)/1*7=259.00
(4*5*2-3)/1*7=259.00
(5*2*4-3)/1*7=259.00
(5*4*2-3)/1*7=259.00
(5*(3+4)+2)/1*7=259.00
(5*(4+3)+2)/1*7=259.00
(7+2*3)*5*4-1=259.00
(7+3*2)*5*4-1=259.00
(7+2*3)*4*5-1=259.00
(7+3*2)*4*5-1=259.00
(2*4*5-3)*7/1=259.00
(2*5*4-3)*7/1=259.00
(4*2*5-3)*7/1=259.00
(4*5*2-3)*7/1=259.00
(5*2*4-3)*7/1=259.00
(5*4*2-3)*7/1=259.00
(5*(3+4)+2)*7/1=259.00
(5*(4+3)+2)*7/1=259.00
(1*2*4*5-3)*7=259.00
(1*2*5*4-3)*7=259.00
(1*4*2*5-3)*7=259.00
(1*4*5*2-3)*7=259.00
(1*5*2*4-3)*7=259.00
(1*5*4*2-3)*7=259.00
(2*1*4*5-3)*7=259.00
(2*1*5*4-3)*7=259.00
(2*4*1*5-3)*7=259.00
(2*4*5*1-3)*7=259.00
(2*5*1*4-3)*7=259.00
(2*5*4*1-3)*7=259.00
(4*1*2*5-3)*7=259.00
(4*1*5*2-3)*7=259.00
(4*2*1*5-3)*7=259.00
(4*2*5*1-3)*7=259.00
(4*5*1*2-3)*7=259.00
(4*5*2*1-3)*7=259.00
(5*1*2*4-3)*7=259.00
(5*1*4*2-3)*7=259.00
(5*2*1*4-3)*7=259.00
(5*2*4*1-3)*7=259.00
(5*4*1*2-3)*7=259.00
(5*4*2*1-3)*7=259.00
(2*4*5/1-3)*7=259.00
(2*5*4/1-3)*7=259.00
(4*2*5/1-3)*7=259.00
(4*5*2/1-3)*7=259.00
(5*2*4/1-3)*7=259.00
(5*4*2/1-3)*7=259.00
(2/1*4*5-3)*7=259.00
(2/1*5*4-3)*7=259.00
(4/1*2*5-3)*7=259.00
(4/1*5*2-3)*7=259.00
(5/1*2*4-3)*7=259.00
(5/1*4*2-3)*7=259.00
(2*4/(1/5)-3)*7=259.00
(2*5/(1/4)-3)*7=259.00
(4*2/(1/5)-3)*7=259.00
(4*5/(1/2)-3)*7=259.00
(5*2/(1/4)-3)*7=259.00
(5*4/(1/2)-3)*7=259.00
(3*4*(5-2)+1)*7=259.00
(4*3*(5-2)+1)*7=259.00
(1*5*(3+4)+2)*7=259.00
(1*5*(4+3)+2)*7=259.00
(5*1*(3+4)+2)*7=259.00
(5*1*(4+3)+2)*7=259.00
(2*4*(1+3)+5)*7=259.00
(2*4*(3+1)+5)*7=259.00
(4*2*(1+3)+5)*7=259.00
(4*2*(3+1)+5)*7=259.00
((5-2)*3*4+1)*7=259.00
((5-2)*4*3+1)*7=259.00
((3+4)*1*5+2)*7=259.00
((3+4)*5*1+2)*7=259.00
((4+3)*1*5+2)*7=259.00
((4+3)*5*1+2)*7=259.00
((1+3)*2*4+5)*7=259.00
((1+3)*4*2+5)*7=259.00
((3+1)*2*4+5)*7=259.00
((3+1)*4*2+5)*7=259.00
((3+4)*5/1+2)*7=259.00
((4+3)*5/1+2)*7=259.00
(5/1*(3+4)+2)*7=259.00
(5/1*(4+3)+2)*7=259.00
((3+4)/(1/5)+2)*7=259.00
((4+3)/(1/5)+2)*7=259.00
(5*7+2)*(3+4)*1=259.00
(5*7+2)*(4+3)*1=259.00
(7*5+2)*(3+4)*1=259.00
(7*5+2)*(4+3)*1=259.00
(4*5*2-1*3)*7=259.00
(4*5*2-3*1)*7=259.00
(5*4*2-1*3)*7=259.00
(5*4*2-3*1)*7=259.00
(2*5*4-1*3)*7=259.00
(2*5*4-3*1)*7=259.00
(5*2*4-1*3)*7=259.00
(5*2*4-3*1)*7=259.00
(2*4*5-1*3)*7=259.00
(2*4*5-3*1)*7=259.00
(4*2*5-1*3)*7=259.00
(4*2*5-3*1)*7=259.00
(4*5*2-3/1)*7=259.00
(5*4*2-3/1)*7=259.00
(2*5*4-3/1)*7=259.00
(5*2*4-3/1)*7=259.00
(2*4*5-3/1)*7=259.00
(4*2*5-3/1)*7=259.00
((3+4)*5+1*2)*7=259.00
((3+4)*5+2*1)*7=259.00
((4+3)*5+1*2)*7=259.00
((4+3)*5+2*1)*7=259.00
((3+4)*5+2/1)*7=259.00
((4+3)*5+2/1)*7=259.00
(2*3+7)*4*5-1=259.00
(2*3+7)*5*4-1=259.00
(3*2+7)*4*5-1=259.00
(3*2+7)*5*4-1=259.00
(5*7+2)*(3+4)/1=259.00
(5*7+2)*(4+3)/1=259.00
(7*5+2)*(3+4)/1=259.00
(7*5+2)*(4+3)/1=259.00
(5*7+2)*1*(3+4)=259.00
(5*7+2)*1*(4+3)=259.00
(7*5+2)*1*(3+4)=259.00
(7*5+2)*1*(4+3)=259.00
(4*5*2-3)*1*7=259.00
(4*5*2-3)*7*1=259.00
(5*4*2-3)*1*7=259.00
(5*4*2-3)*7*1=259.00
(2*5*4-3)*1*7=259.00
(2*5*4-3)*7*1=259.00
(5*2*4-3)*1*7=259.00
(5*2*4-3)*7*1=259.00
(2*4*5-3)*1*7=259.00
(2*4*5-3)*7*1=259.00
(4*2*5-3)*1*7=259.00
(4*2*5-3)*7*1=259.00
(4*5*2-3)*7/1=259.00
(5*4*2-3)*7/1=259.00
(2*5*4-3)*7/1=259.00
(5*2*4-3)*7/1=259.00
(2*4*5-3)*7/1=259.00
(4*2*5-3)*7/1=259.00
(5*7*1+2)*(3+4)=259.00
(5*7*1+2)*(4+3)=259.00
(7*5*1+2)*(3+4)=259.00
(7*5*1+2)*(4+3)=259.00
(1*7*5+2)*(3+4)=259.00
(1*7*5+2)*(4+3)=259.00
(7*1*5+2)*(3+4)=259.00
(7*1*5+2)*(4+3)=259.00
(1*5*7+2)*(3+4)=259.00
(1*5*7+2)*(4+3)=259.00
(5*1*7+2)*(3+4)=259.00
(5*1*7+2)*(4+3)=259.00
((3+4)*5+2)*1*7=259.00
((3+4)*5+2)*7*1=259.00
((4+3)*5+2)*1*7=259.00
((4+3)*5+2)*7*1=259.00
((3+4)*5+2)*7/1=259.00
((4+3)*5+2)*7/1=259.00
(7/1*5+2)*(3+4)=259.00
(7/1*5+2)*(4+3)=259.00
(5/1*7+2)*(3+4)=259.00
(5/1*7+2)*(4+3)=259.00
(5*7/1+2)*(3+4)=259.00
(5*7/1+2)*(4+3)=259.00
(7*5/1+2)*(3+4)=259.00
(7*5/1+2)*(4+3)=259.00
(5*7+2)/1*(3+4)=259.00
(5*7+2)/1*(4+3)=259.00
(7*5+2)/1*(3+4)=259.00
(7*5+2)/1*(4+3)=259.00
(4*5*2-3)/(1/7)=259.00
(5*4*2-3)/(1/7)=259.00
(2*5*4-3)/(1/7)=259.00
(5*2*4-3)/(1/7)=259.00
(2*4*5-3)/(1/7)=259.00
(4*2*5-3)/(1/7)=259.00
((3+4)*5+2)/(1/7)=259.00
((4+3)*5+2)/(1/7)=259.00
Top
13 楼tonnywang（tonny_wang）回复于 2003-06-04 13:06:46 得分 0
输入7 259 1 2 3 4 5 6 7,几分钟穷举不完,
结果就更夸张了,只贴一部分:
如果只出一个结果是很快的
((2*6-4)*5-3)*7*1=259.00
((6*2-4)*5-3)*7*1=259.00
((4*6-3)*2-5)*7*1=259.00
((6*4-3)*2-5)*7*1=259.00
((2*6-4)*5-3)*1*7=259.00
((6*2-4)*5-3)*1*7=259.00
((4*6-3)*2-5)*1*7=259.00
((6*4-3)*2-5)*1*7=259.00
((4+6-2)*5-3)*7*1=259.00
((6+4-2)*5-3)*7*1=259.00
((4+6-2)*5-3)*1*7=259.00
((6+4-2)*5-3)*1*7=259.00
((2*4+6)*3-5)*7*1=259.00
((4*2+6)*3-5)*7*1=259.00
((2*4+6)*3-5)*1*7=259.00
((4*2+6)*3-5)*1*7=259.00
((6-2+4)*5-3)*7*1=259.00
((4-2+6)*5-3)*7*1=259.00
((6-2+4)*5-3)*1*7=259.00
((4-2+6)*5-3)*1*7=259.00
((4/2+6)*5-3)*7*1=259.00
((6/4+5)*3-1)*7*2=259.00
((4/6+2)*5-1)*7*3=259.00
((4/2+6)*5-3)*1*7=259.00
((6/4+5)*3-1)*2*7=259.00
((4/6+2)*5-1)*3*7=259.00
(3*6*2+5-4)*7*1=259.00
(6*3*2+5-4)*7*1=259.00
(2*6*3+5-4)*7*1=259.00
(6*2*3+5-4)*7*1=259.00
(2*3*6+5-4)*7*1=259.00
(3*2*6+5-4)*7*1=259.00
(4*5*2+3-6)*7*1=259.00
(5*4*2+3-6)*7*1=259.00
(2*5*4+3-6)*7*1=259.00
(5*2*4+3-6)*7*1=259.00
(2*4*5+3-6)*7*1=259.00
(4*2*5+3-6)*7*1=259.00
(3*6*2+5-4)*1*7=259.00
(6*3*2+5-4)*1*7=259.00
(2*6*3+5-4)*1*7=259.00
(6*2*3+5-4)*1*7=259.00
(2*3*6+5-4)*1*7=259.00
(3*2*6+5-4)*1*7=259.00
(4*5*2+3-6)*1*7=259.00
(5*4*2+3-6)*1*7=259.00
(2*5*4+3-6)*1*7=259.00
(5*2*4+3-6)*1*7=259.00
(2*4*5+3-6)*1*7=259.00
(4*2*5+3-6)*1*7=259.00
((4+6-3)*5+2)*7*1=259.00
((6+4-3)*5+2)*7*1=259.00
((4+6-3)*5+2)*1*7=259.00
((6+4-3)*5+2)*1*7=259.00
((6-3+4)*5+2)*7*1=259.00
((4-3+6)*5+2)*7*1=259.00
((6-3+4)*5+2)*1*7=259.00
((4-3+6)*5+2)*1*7=259.00
((5/2+6)*4+3)*7*1=259.00
((5/2+3)*6+4)*7*1=259.00
((4/6+5)*2+1)*7*3=259.00
((5/6+2)*4+1)*7*3=259.00
((5/2+6)*4+3)*1*7=259.00
((5/2+3)*6+4)*1*7=259.00
((4/6+5)*2+1)*3*7=259.00
((5/6+2)*4+1)*3*7=259.00
(4*5*2-6+3)*7*1=259.00
(5*4*2-6+3)*7*1=259.00
(2*5*4-6+3)*7*1=259.00
(5*2*4-6+3)*7*1=259.00
(2*4*5-6+3)*7*1=259.00
(4*2*5-6+3)*7*1=259.00
(3*6*2-4+5)*7*1=259.00
(6*3*2-4+5)*7*1=259.00
(2*6*3-4+5)*7*1=259.00
(6*2*3-4+5)*7*1=259.00
(2*3*6-4+5)*7*1=259.00
...
(3*2*6/1-4+5)*7=259.00
((4-2)*5*3+6+1)*7=259.00
((4-2)*3*5+6+1)*7=259.00
((2-1)*6*5+4+3)*7=259.00
((2-1)*5*6+4+3)*7=259.00
((2-1)*6*5+3+4)*7=259.00
((2-1)*5*6+3+4)*7=259.00
((4-2)*5*3+1+6)*7=259.00
((4-2)*3*5+1+6)*7=259.00
((3+6)*7*4+5+2)*1=259.00
((6+3)*7*4+5+2)*1=259.00
((3+6)*4*7+5+2)*1=259.00
((6+3)*4*7+5+2)*1=259.00
((3+6)*7*4+2+5)*1=259.00
((6+3)*7*4+2+5)*1=259.00
((3+6)*4*7+2+5)*1=259.00
((6+3)*4*7+2+5)*1=259.00
((4+6)*3*1+5+2)*7=259.00
((6+4)*3*1+5+2)*7=259.00
((4+6)*1*3+5+2)*7=259.00
((6+4)*1*3+5+2)*7=259.00
((2+5)*4*1+6+3)*7=259.00
((5+2)*4*1+6+3)*7=259.00
((2+5)*1*4+6+3)*7=259.00
((5+2)*1*4+6+3)*7=259.00
((4+6)*3*1+2+5)*7=259.00
((6+4)*3*1+2+5)*7=259.00
((4+6)*1*3+2+5)*7=259.00
((6+4)*1*3+2+5)*7=259.00
((2+5)*4*1+3+6)*7=259.00
((5+2)*4*1+3+6)*7=259.00
((2+5)*1*4+3+6)*7=259.00
((5+2)*1*4+3+6)*7=259.00
(5/2*4*3+6+1)*7=259.00
(4/2*5*3+6+1)*7=259.00
(3/2*4*5+1+6)*7=259.00
((2*5-1)*3+6+4)*7=259.00
((5*2-1)*3+6+4)*7=259.00
((2*5-1)*3+4+6)*7=259.00
((5*2-1)*3+4+6)*7=259.00
((1*6+4)*3+5+2)*7=259.00
((6*1+4)*3+5+2)*7=259.00
((1*4+6)*3+5+2)*7=259.00
((4*1+6)*3+5+2)*7=259.00
((1*5+2)*4+6+3)*7=259.00
((5*1+2)*4+6+3)*7=259.00
((1*2+5)*4+6+3)*7=259.00
...
(6*7*3-1)*2+5+4=259.00
(7*6*3-1)*2+5+4=259.00
(3*7*6-1)*2+5+4=259.00
(7*3*6-1)*2+5+4=259.00
(3*6*7-1)*2+5+4=259.00
(6*3*7-1)*2+5+4=259.00
(6*7*3-1)*2+4+5=259.00
(7*6*3-1)*2+4+5=259.00
(3*7*6-1)*2+4+5=259.00
(7*3*6-1)*2+4+5=259.00
(3*6*7-1)*2+4+5=259.00
((1+7)*5+2)*6+4+3=259.00
((7+1)*5+2)*6+4+3=259.00
...
(3+6)*7/1*4+5+2=259.00
(6+3)*7/1*4+5+2=259.00
((6+4)*3+2+5)*7/1=259.00
((2+5)*4+3+6)*7/1=259.00
((5+2)*4+3+6)*7/1=259.00
((2*7-3)*6*4-5)/1=259.00
((7*2-3)*6*4-5)/1=259.00
((2*7-3)*4*6-5)/1=259.00
((7*2-3)*4*6-5)/1=259.00
((4*7*2-3)*5-6)/1=259.00
((7*4*2-3)*5-6)/1=259.00
((2*7*4-3)*5-6)/1=259.00
...
此法也许行不通Top
14 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-06-04 13:30:58 得分 0
应该有DP的方法，可我只想到疯狂搜索...Top
15 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-06-04 15:30:57 得分 0
发信人: starfish (金盆洗手，退隐江湖), 信区: Algorithm
标 题: 计算24点问题的详细解析
发信站: 南京大学小百合站 (Tue Apr 1 22:01:46 2003)
24点游戏
数字游戏题解
by starfish
[说明：此文改编自我写的一篇解题报告，原题是某年国家集训队组队赛题目]
问题描述
80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。现在我们
把这个有趣的游戏推广一下：您作为游戏者将得到6个不同的自然数作为操作数，
以及另外一个自然数作为理想目标数，而您的任务是对这6个操作数进行适当的算
术运算，要求运算结果小于或等于理想目标数，并且我们希望所得结果是最优的，
即结果要最接近理想目标数。
您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：
所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是
合法的，2*（2/4）是不合法的）
下面我们给出一个游戏的具体例子：
若给出的6个操作数是：1，2，3，4，7和25，理想目标数是573；
则最优结果是573：（（（4*25-1）*2）-7）*3。
输入：
输入文件名为game.in。输入文件仅一行，包含7个整数，前6个整数Mi,
1<=Mi<=100，表示操作数，最后一个整数T, 1<=T<=1000,表示理想目标数。
输出：
输出文件名为game.out。输出文件有两行，第一行仅一个整数，表示您的程序计算
得到的最优结果；第二行是一个表达式，即您得到的最优结果的运算方案。
输入输出示例：
输入文件
1 2 3 4 7 25 573
输出文件
573
((4*25-1)*2)-7)*3
算法分析
首先我们要对这个问题进行数学抽象。
定义1：对于有理数组成的多重集合S ， f(S) 定义如下：
如果 S 是空集或只包含一个元素，则 f(S)=S ；否则
f(S)=∪ f( ( S-{r1, r2}) ∪ {r} ) ，对于每一个 r=r1+r2 , r1-r2 , r1×r2
，r1÷r2(r2≠0)，且r1, r2取遍 S 中所有元素的组成的二元组。
定义1说明：要计算集合S中的元素通过四则混合运算所能得到的所有值，我们只需
要任取 S 中的两个元素 r1 , r2 ，分别计算 r1 , r2 的加减乘除运算，然后用
所得的结果与 S 中剩下的其他数字进行四则混合运算。只要取遍所有的 r1 ,
r2 ，最后得到的所有结果的并集就是 S 中的元素通过四则混合运算所能得到的所
有值的集合。
根据上述定义，在本问题中，集合 S 就是由输入中给定的6个正整数组成的集合，
题目所求就是找出 f(S) 中小于或等于目标数的最大数。
定义2：给定两个多重集合 S1 , S2，定义
comb( S1, S2 ) = ∪ { r1+r2 , r1-r2, r1×r2, r1÷r2(r2≠0) }
(1.1)
其中 ( r1 , r2 ) ∈ S1 × S2。
定义2实际上定义了两个集合中的元素两两进行加减乘除运算所能得到的结果集合
。
定理1：对于有理数组成的多重集合 S ，如果 S 至少有两个元素，则
f(S)=∪ comb( f(S1), f(S - S1) ) (1.2)
其中 S1 取遍 S 的所有非空真子集。
定理1的含义是：要计算 S 中的元素通过四则混合运算所能得到的所有值，可以先
将 S 分解为两个子集 S1 和 S- S1 ，分别计算 S1 和 S-S1 中的元素进行四则混
合运算所能得到的结果集合，即 f(S1) 和 f(S-S1) ，然后对这两个集合中的元素
进行加减乘除运算，即 comb( f(S1), f(S-S1) ) ，最后得到的所有集合的并集就
是 f(S) 。限于篇幅，定理1的正确性易用数学归纳法证明。
定义1和定理1实际上分别给出了计算f(S)的两种不同的方法。根据定义1，可以递
归地计算f(S) ，其算法伪代码如下：
算法1
function f(S)
begin
1. if |S| < 2
2. then return S
3. else begin
4. T ← Φ
5. for each (r1, r2) in S do
6. begin
7. r ← r1 + r2;
8. T ← T + f(S – {r1, r2} + {r});
9. r ← r1 - r2;
10. T ← T + f(S – {r1, r2} + {r});
11. r ← r1 * r2;
12. T ← T + f(S – {r1, r2} + {r});
13. if (r2 <> 0) and (r1 mod r2 = 0) then
14. begin
15. r ← r1 / r2;
16. T ← T + f(S – {r1, r2} + {r});
17. end
18. end
19. return T;
20. end
end
Top
16 楼BlueSky2008（懒惰是程序员的美德）回复于 2003-06-04 15:33:48 得分 0
上述伪代码中使用了+, - 来分别表示集合的并和差运算。算法1每次选择两个数字
进行某种运算，然后将结果与剩下的数字递归地进行运算，最后求得所有数字进行
四则混合运算的结果。当然，在具体实现该算法的过程中有很多可以优化的地方，
比如根据加法交换律， a+b+c=a+c+b ，因此我们可以规定：如果上一层递归作了
加法运算，这一层仅当满足当前的操作数大于上一层的两个操作数的时候才进行加
法运算，以确保 a+b+c 这样的式子中的操作数总是从小到大排列，这样就可以避
免重复进行等价的加法计算。类似地我们可以对乘法也作此规定。在进行减法的时
候，我们可以规定只能计算大数减小数，因为最后所需计算得到的目标数是一个正
数，如果计算过程中出现负数，肯定有另外一个较大的正数与其作加法或者有另外
一个负数与其做乘除法以消除负号。因此我们总可以调整运算次序使得四则混合运
算的每一步的中间结果都是正数。在作除法的时候，因为题目规定中间结果只能是
整数，所以也只需要用大数除小数，且仅当能除尽的时候才进行除法。对于本题而
言，初始的集合 S 中一共有6个操作数，每次递归都可以合并两个操作数，所以递
归到第5层的时候集合 S 中只剩下一个数，这个数就是原先的6个操作数进行四则
混合运算所能得到的结果。本题只要求最接近目标值的结果，所以实现上述算法的
时候可以只记录当前最优的结果。对于本题也可以利用递归回溯构造出所有的四则
混合运算的语法树，但本质上与算法1是没有区别的。
定理1则给出了另一种计算f(S)的方法。我们当然也可以根据(1.2)式直接地递归计
算f(S)，但那样的话会有很多冗余计算。例如对于S={1,2,3,4}，
f(S) = comb( f({ 1 }), f({ 2,3,4}) )∪ ... ∪ comb( f({ 1,2 }), f({
3,4 }) ) ∪ ...;
计算f(S)的时候需要计算 f({ 2,3,4 })和f({ 3,4 }) ，又因为
f({2,3,4}) = comb(f({ 2 }), f({3,4})) ∪ ...;
在计算 f({ 2,3,4}) 的时候又要重复地计算 f({ 3,4 }) ，这就产生了冗余的计
算。这种情况下直接地递归就不适用。必须按照一定的顺序，递推地进行计算。这
种将递归改为递推，以解决冗余的算法设计策略，就叫做动态规划。
下面我们具体阐述一下该算法的步骤。设初始时集合 S 中的 n 个数字分别为
x[0], x[1],...,x[n-1] ，我们可以用一个二进制数k来表示S 的子集 S[k] ，
x[i] ∈ S[k] 当且仅当二进制数k的第i位为1。于是我们用一个数组 F[0..2^n-1]
就可以保存函数f对于S的所有子集的函数值（注意，函数f的函数值是一个集合）
，且 F[2^n-1]=f(S) 就是所求。
算法2
1. for i ← 0 to 2^n-1
2. do F[i]←Φ;
3. for i ← 0 to n-1
4. do F[2^i]← {x[i]};
5. for x ← 1 to 2^n-1 do
6. begin
7. for i ← 1 to i-1 do
8. begin
9. if x∧i=i then
10. begin
11. j ← x – i;
12. if i < j
13. then F[x] ← F[x] + comp(F[i],F[j]);
14. end;
15. end;
16. end;
17. return F[ 2 n ?1] ;
上述伪代码中使用了+表示集合的并运算。算法2的第1～2行将F中所有的集合初始
化为空；第3～4行中 2^i 即表示只包含元素 x[i]的子集（因为 2^i 只有第 i 位
上是1），根据定义1我们知道当集合中只有一个元素的时候函数 f 的函数值就是
那唯一的元素组成的集合，所以3～4行计算出了函数 f 对于所有只有一个元素的
子集的函数值；第5～17行按照一定的顺序计算函数 f 对于 S 的所有子集的函数
值。对于 S 的两个子集 S[i] 和 S[x] ， S[i]真包含于S[x]的充要条件是 x∧
i=i ，这里 ∧ 是按位进行与操作，而 x∧i=i 的必要条件是 i<x 。因而第7~15
行的循环将S[x]拆成两个子集S[i]和S[j]，并在第13行根据(1.2)式计算所有的
comp( f(S[i]),f(S[j]) ) 的并。第12行的判断语句是为了优化算法的效率，因为
将 S[x]拆成两个子集 S[i]和 S[j]的过程是对称的，所以我们对于 comp(
f(S[i]),f(S[j]) ) 和 comp( f(S[j]),f(S[i]) ) 两者只取一个进行计算。下面
是函数comp的伪代码：
算法3
function comp(S1, S2)
1. T ← Φ ;
2. for each x in S1 do
3. begin
4. for each y in S2 do
5. begin
6. T ← T + {(x + y)};
7. T ← T + {(x * y)};
8. if x > y then
9. begin
10. T ← T + {(x – y)};
11. if (y <> 0) and (x mod y = 0)
12. then T ← T + {(x / y)};
13. end
14. else begin
15. T ← T + {(y – x)};
16. if (x <> 0) and (y mod x = 0)
17. then T ← T + {(y / x)};
18. end;
19. end;
20. end;
21. return T;
comp在进行计算的时候不考虑参数集合S1和S2的顺序，进行减法的时候始终用大
数减小数，这样保证运算过程中不出现负数（这样做的理由前文已经阐明）。
因为我们只关心最后的f(S)中最接近目标值的数字，并且题目只要求求出任何一组
最优解，所以算法2中的集合不需要是多重集合，只要是一般的集合即可。换句话
说，集合F[i]中所有的元素互不相同，重复出现元素的我们只保留其中一个。这样
可以大大减少计算中的冗余。做了这样的处理后，算法2的效率至少不会比算法1差
，因为算法1中所能采用的主要剪枝手段是排除等价的表达式，但因为等价的两个
表达式计算出的结果也一定相同，而算法2排除了所有结果相同的表达式，所以算
法2的效率至少不会比算法1差，算法2中所进行的计算基本上都是得到最优解所必
需的计算。
在实现算法2的过程中，集合可以用一个链表加上一个哈希表来实现。链表中保存
每个表达式及其值，哈希表用来记录该集合中是否存在某个特定值的表达式。当向
集合中插入一个新的表达式的时候，首先检查哈希表，看看该集合是否已经有和新
表达式值相同的表达式，如果有的话就不插入，否则将新的表达式追加到链表末尾
。采用这种数据结构，可以在常数时间内完成集合的插入和删除操作。利用链表，
集合的并操作也很容易高效地实现。
在实现算法2的过程中，可以不必保存表达式的字符串，只需要记录下当前的值是
由哪两个集合中的元素通过哪种运算得到的，最后再根据最优解递归地计算出最优
解的表达式。这样只在最后构造最优解的表达式时才进行字符串操作，程序运行效
率能提高7～8倍左右。另外，在comb函数中进行乘法运算的时候要注意考虑运算结
果超出整数范围的情况。
经过以上优化，利用算法2实现的程序对于100个随机生成的测试数据总共只需要5
秒左右就可以出解，平均每个数据只需要50毫秒即可出解（测试用的CPU为赛扬
1GB）。这样的效率已经非常令人满意了。
Top
17 楼8alang8（alang）回复于 2003-06-04 16:20:46 得分 0
ft,我也只想到 疯狂搜索+优化Top
