中国DOS联盟

发信人: wfaye (打倒北约), 信区: GreatTurn
标 题: 计算24的程序
发信站: BBS 水木清华站 (Wed Feb 7 10:48:30 2001)

看大家一直在孜孜以求的计算24, 不如贴个程序出来,
可以在1秒种之内解决任何计算24的问题. 当然想算25, 26...
也是可以的. 希望以此作为24问题的终结.

#include "stdafx.h"
//
//原理, 将4个数字和3个运算符按"波兰表达式"组成一个序列,
// 计算该序列的值是否为所求目标. 可以对这个序列的组成
// 进行遍历, 以确定是否有解.
//根据我的计算如果只限于用1-10之间的数字计算24, 总共有
// 715个不同的题目, 其中566个有解. 如果是1-13, 则有
// 1820个不同的题目, 其中1362个有解
//
int total = 0; //解的个数
int sp; //当前表达式栈指针
int s; //表达式栈
void Evaluate(int& fz, int& fm)
//计算表达式的值, fz, fm为计算结果的分子, 分母
{
int op, l, m, opn;
op = s; //取栈顶元素
for (l = 0; l 0) //是数字
{
opn = m;
opn = 1;
}
else //是运算符
Evaluate(opn, opn);
}
//根据运算符进行计算
//opn/opn 是第一个操作数,
//opn/opn 是第二个操作数,
switch (op)
{
case -4: //乘法
fz = opn * opn;
fm = opn * opn;
break;
case -3: //加法
fz = opn * opn + opn * opn;
fm = opn * opn;
break;
case -2: //减法
fz = opn * opn - opn * opn;
fm = opn * opn;
break;
case -1: //除法
fz = opn * opn;
fm = opn * opn;
break;
}
}
void Display(CString& m)
//将表达式转换为字符串
{
int i;
CString n;
m = "";
for (i = 0; i < 7; i++)
{
switch (s)
{
case -4: m += " *"; break;
case -3: m += " +"; break;
case -2: m += " -"; break;
case -1: m += " /"; break;
default: n.Format("%3d", s); m += n; break;
}
}
}
void Compute(int target, int a, int b, int c, int d, CStringArray& ma)
// target - 计算结果(一般为24)
// a, b, c, d - 参加计算的4个数
// ma - 解的字符串表达形式
{
int l1, l2, l3, op1, op2, op3;
int l, fz, fm, num;
CString m;

//记录表达式中间四个元素的排列方式
// 其中loc, loc表示第二, 第三两个运算符的位置
// loc, loc表示第一, 第二两个操作数的位置
int loc = {{1, 2, 3, 4}, {1, 3, 2, 4}, {1, 4, 2, 3},
{2, 3, 1, 4}, {2, 4, 1, 3}};
//num中记录a, b, c, d的一个排列
for (l1 = 0; l1 < 4; l1++)
{
num = a;
for (l2 = 0; l2 < 4; l2++)
{
if (l2 == l1) continue;
num = b;
for (l3 = 0; l3 < 4; l3++)
{
if (l3 == l1 || l3 == l2) continue;
num = c;
num = d;
//表达式最后两个必须是数字
s = num;
s = num;
for (l = 0; l < 5; l++)
{
s] = num;
s] = num;
for (op1 = -4; op1 < 0; op1++)
{
//表达式第一个必须运算符
s = op1;
for (op2 = -4; op2 < 0; op2++)
{
s] = op2;
for (op3 = -4; op3 < 0; op3++)
{
s] = op3;
sp = 0;
Evaluate(fz, fm);
//分母不为0, 可以整除, 商为24表示计算成功
if (fm != 0 && fz % fm == 0 && fz / fm == target)
{
Display(m);
ma.Add(m);
total++;
//这里加return就是只求一个解,
//否则是求出全部解(没有考虑剔除重复解)
return;
}
}
}
}
}
}
}
}
}

--

※ 来源:·BBS 水木清华站 smth.org·

(本文采用S-Term文章拷贝脚本拷贝)
==================================================

再贴一个程序：
也是清华的，算24的程序。
#include
#include
int get1(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
return(temp);
}
int get2(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&((*p1)%temp==0))
{ temp=(*p1)/temp;
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
return(temp);
}
int get3(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp+=(*p1); break;
case 1: temp-=(*p1); break;
case 2: temp*=(*p1); break;
case 3: if ((*p1)&&(temp%(*p1)==0))
{ temp=temp/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&(*p1)%temp==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
return(temp);
}
int get4(int (*p1),char (*p2))
{ int temp;
switch((*p2))
{ case 0: temp=(*p1)+(*p1); break;
case 1: temp=(*p1)-(*p1); break;
case 2: temp=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ temp=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)-temp; break;
case 3: if ((temp)&&(*p1)%temp==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
switch((*p2))
{ case 0: temp=(*p1)+temp; break;
case 1: temp=(*p1)-temp; break;
case 2: temp=(*p1)*temp; break;
case 3: if ((temp)&&(*p1)==0)
{ temp=(*p1)/temp;
break;
}
else return(0);
}
return(temp);
}
int get5(int (*p1),char (*p2))
{ int tmp1,tmp2;
switch((*p2))
{ case 0: tmp1=(*p1)+(*p1); break;
case 1: tmp1=(*p1)-(*p1); break;
case 2: tmp1=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ tmp1=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: tmp2=(*p1)+(*p1); break;
case 1: tmp2=(*p1)-(*p1); break;
case 2: tmp2=(*p1)*(*p1); break;
case 3: if ((*p1)&&((*p1)%(*p1)==0))
{ tmp2=(*p1)/(*p1);
break;
}
else return(0);
}
switch((*p2))
{ case 0: tmp1+=tmp2; break;
case 1: tmp1-=tmp2; break;
case 2: tmp1*=tmp2; break;
case 3: if ((tmp2)&&(tmp1%tmp2==0))
{ tmp1/=tmp2;
break;
}
else return(0);
}
return(tmp1);
}
void main()
{ int num,(*pp1),input,goal,i,j,k,m,n;
char (*pp2),code;
cout<>goal;
cout<<"Input four numbers:";
for(i=0;i>input;
m=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
{ code=i;
code=j;
code=k;
m++;
}
n=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
if (j!=i) for(k=0;k<4;k++)
if ((k!=i)&&(k!=j)) { m=6-i-j-k;
num=input;
num=input;
num=input;
num=input;
n++;
}
m=0;
for(i=0,pp1=num;i<24;i++,pp1++)
{ for(j=0,pp2=code;j<64;j++,pp2++)
{ k=get1(pp1,pp2); if (k==goal) {m=1; break;}
k=get2(pp1,pp2); if (k==goal) {m=2; break;}
k=get3(pp1,pp2); if (k==goal) {m=3; break;}
k=get4(pp1,pp2); if (k==goal) {m=4; break;}
k=get5(pp1,pp2); if (k==goal) {m=5; break;}
}
if(m) break;
}
if(m)
{ char analyst;
for(i=0;i<3;i++)
switch((*pp2))
{ case 0*pp2)='+'; break;
case 1*pp2)='-'; break;
case 2*pp2)='*'; break;
case 3*pp2)='/';
}
switch (m)
{ //The following may be hard to understand!
//See how and why to do in the end of the program!
// ( ( a ? b ) ? c ) ? d ?=+,-,*,/
// 0 1 2 3 4 5 6 7 8 9 10
case 1:strcpy(analyst,"((a?b)?c)?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
break;
// ( a ? ( b ? c ) ) ? d
// 0 1 2 3 4 5 6 7 8 9 10
case 2:strcpy(analyst,"(a?(b?c))?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
break;
// a ? ( ( b ? c ) ? d )
// 0 1 2 3 4 5 6 7 8 9 10
case 3:strcpy(analyst,"a?((b?c)?d";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
break;
// a ? ( b ? ( c ? d ) )
// 0 1 2 3 4 5 6 7 8 9 10
case 4:strcpy(analyst,"a?(b?(c?d))";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
break;
// ( a ? b ) ? ( c ? d )
// 0 1 2 3 4 5 6 7 8 9 10
case 5:strcpy(analyst,"(a?b)?(c?d)";
analyst=(*pp2);
analyst=(*pp2);
analyst=(*pp2);
if((analyst=='*'||(analyst=='/'||
(analyst=='+'||(analyst=='-')
{ analyst='0'; analyst='0'; }
if((analyst=='+'||(analyst!='/'&&
((analyst=='*'||(analyst=='/'))
{ analyst='0'; analyst='0'; }
}
for(i=0;i<11;i++)
switch(analyst)
{ case 'a': cout<<(*pp1); break;
case 'b': cout<<(*pp1); break;
case 'c': cout<<(*pp1); break;
case 'd': cout<<(*pp1); break;
case '0': break;
default: cout<<analyst;
}
cout<<endl;
}
else
{ for(i=0,pp1=num;i<24;i++,pp1++)
{ j=(*pp1)*(*pp1);
k=(*pp1)*(*pp1);
if(k%(*pp1)==0)
{ k/=(*pp1);
if(j+k==goal) { m=1; break; }
else if(j-k==goal) { m=2; break; }
else if(k-j==goal) { m=3; break; }
}
else
{ j=(*pp1)*(*pp1);
k=(*pp1)*(*pp1);
n=(*pp1);
if((k+n)&&(j%(k+n)==0))
{ if(j/(k+n)==goal)
{ m=4; break; }
}
else
if((k-n)&&(j%(k-n)==0))
if(j/(k-n)==goal) { m=5; break; }
else if(j/(n-k)==goal) { m=6; break; }
}
}
if(!m) cout<<"If you get it,please E-mail to:publicfrk@netease.com\n";
else switch (m)
{ case 1:cout<<(*pp1)<<"*("<<(*pp1)<<'+'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 2:cout<<(*pp1)<<"*("<<(*pp1)<<'-'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 3:cout<<(*pp1)<<"*("<<(*pp1)<<'/'
<<(*pp1)<<'-'<<(*pp1)<<''<<endl;
break;
case 4:cout<<(*pp1)<<"/("<<(*pp1)<<'+'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 5:cout<<(*pp1)<<"/("<<(*pp1)<<'-'
<<(*pp1)<<'/'<<(*pp1)<<''<<endl;
break;
case 6:cout<<(*pp1)<<"/("<<(*pp1)<<'/'
<<(*pp1)<<'-'<<(*pp1)<<''<<endl;
}
}
}
// .T. means you can get ride of ( )
// a?(b?c) (a?b)?c
// + + .T. .T.
// + - .T. .T.
// + * .T. .F.
// + / .T. .F.
// - + .F. .T.
// - - .F. .T.
// - * .T. .F.
// - / .T. .F.
// * + .F. .T.
// * - .F. .T.
// * * .T. .T.
// * / .T. .T.
// / + .F. .T.
// / - .F. .T.
// / * .F. .T.
// / / .F. .T.
//----------------------------------------------------------------
//Conculsion + +,-,*,/ *,/ +,-,*,/
// *,- *,/

再贴一个程序：也是清华的， 算24程序终结版(TC20)


/*TO24 lasy 2002.01.25*/

#define PRE 1E-6
#define DES 24.0

#include
#include

double add(double a,double b){return a+b;}
double sub(double a,double b){return a-b;}
double mul(double a,double b){return a*b;}
double div(double a,double b){return a/b;}

double (*fun)(double,double)={add,sub,mul,div};
const char op={'+','-','*','/'};

struct num
{
double f;
struct num *a,*b;
char op;
};

char to24(int n,struct num *f);
char output(struct num f);
char *fml(struct num f);

main()
{
int i,tmp;
struct num f;
for(i=0;i<4;i++)
{
printf("\nInput Number %d:",i+1);
scanf("%d",&tmp);
f.f=(double)tmp;f.a=f.b=NULL;f.op=0;
}
printf("\nSolutions:\n";
if(to24(4,f)==0)printf("None!";
}

char to24(int n,struct num *f)
{
char flag=0,*tmp;
int i,j,k,l;
struct num *h;
if(n==1)
{
if(fabs(f.f-DES)<PRE)flag=output(f);
}
else
{
for(i=0;i<n;i++)for(j=i+1;j<n;j++)for(k=0;k<4;k++)
{
h=(struct num *)malloc((n-1)*sizeof(struct num));
for(l=0;l<i;l++)h=f;
for(l=i+1;l<j;l++)h=f;
for(l=j;lPRE)
{
h.f=fun(f.f,f.f);
h.a=f+i;
h.b=f+j;
flag=to24(n-1,h)||flag;
}
if(k==1||(k==3&&fabs(f.f)>PRE))
{
h.f=fun(f.f,f.f);
h.a=f+j;
h.b=f+i;
flag=to24(n-1,h)||flag;
}
free(h);
}
}
return flag;
}

char output(struct num f)
{
static int count=0;
char *tmp;
count++;
printf("%3d: %s\t",count,tmp=fml(f));
if(count%3==0)printf("\n";
free(tmp);
return 1;
}

char *fml(struct num f)
{
char *buf,*a,*b;
buf=(char *)malloc(20*sizeof(char));
if(f.a!=NULL&&f.b!=NULL&&f.op!=0)
{
sprintf(buf,"(%s%c%s)",a=fml(*f.a),f.op,b=fml(*f.b));
free(a);free(b);
}
else
sprintf(buf,"%d",(int)f.f);
return buf;
}


＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
KO的话：用编程来解决求24的问题，爽！
有没有人看得懂啊？回个贴。