|
ko20010214
版主
积分 7294
发帖 1628
注册 2002-10-16
状态 离线
|
『楼 主』:
计算24的程序－－C语言编程例题[转帖]
发信人: 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[7]; //表达式栈
void Evaluate(int& fz, int& fm)
//计算表达式的值, fz, fm为计算结果的分子, 分母
{
int op, l, m, opn[4];
op = s[sp]; //取栈顶元素
for (l = 0; l 0) //是数字
{
opn[l] = m;
opn[l + 1] = 1;
}
else //是运算符
Evaluate(opn[l], opn[l + 1]);
}
//根据运算符进行计算
//opn[0]/opn[1] 是第一个操作数,
//opn[2]/opn[3] 是第二个操作数,
switch (op)
{
case -4: //乘法
fz = opn[0] * opn[2];
fm = opn[1] * opn[3];
break;
case -3: //加法
fz = opn[0] * opn[3] + opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -2: //减法
fz = opn[0] * opn[3] - opn[1] * opn[2];
fm = opn[1] * opn[3];
break;
case -1: //除法
fz = opn[0] * opn[3];
fm = opn[1] * opn[2];
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[4];
CString m;
//记录表达式中间四个元素的排列方式
// 其中loc[0], loc[1]表示第二, 第三两个运算符的位置
// loc[2], loc[3]表示第一, 第二两个操作数的位置
int loc[5][4] = {{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[l1] = a;
for (l2 = 0; l2 < 4; l2++)
{
if (l2 == l1) continue;
num[l2] = b;
for (l3 = 0; l3 < 4; l3++)
{
if (l3 == l1 || l3 == l2) continue;
num[l3] = c;
num[6 - l1 - l2 - l3] = d;
//表达式最后两个必须是数字
s[5] = num[2];
s[6] = num[3];
for (l = 0; l < 5; l++)
{
s[loc[l][2]] = num[0];
s[loc[l][3]] = num[1];
for (op1 = -4; op1 < 0; op1++)
{
//表达式第一个必须运算符
s[0] = op1;
for (op2 = -4; op2 < 0; op2++)
{
s[loc[l][0]] = op2;
for (op3 = -4; op3 < 0; op3++)
{
s[loc[l][1]] = 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·[FROM: 166.111.68.247]
(本文采用S-Term文章拷贝脚本拷贝)
==================================================
|
ko20010214
=================================
大功告成，打个Kiss!
ko20010214@MSN.com
神州优雅Q300C
Intel CeleronM 370处理器 | 256MbDDR内存
40G硬盘 | USB2.0 | IEEE 1394
13.3 ' WXGA 宽屏(16:10) | COMBO光驱
10/100M网卡 | 四合一读卡器
|
|
 2003-6-15 00:00 |
|
|
ko20010214
版主
积分 7294
发帖 1628
注册 2002-10-16
状态 离线
|
『第
2 楼』:
再贴一个程序：
也是清华的，算24的程序。
#include
#include
int get1(int (*p1)[4],char (*p2)[3])
{ int temp;
switch((*p2)[0])
{ case 0: temp=(*p1)[0]+(*p1)[1]; break;
case 1: temp=(*p1)[0]-(*p1)[1]; break;
case 2: temp=(*p1)[0]*(*p1)[1]; break;
case 3: if ((*p1[1])&&((*p1)[0]%(*p1)[1]==0))
{ temp=(*p1)[0]/(*p1)[1];
break;
}
else return(0);
}
switch((*p2)[1])
{ case 0: temp+=(*p1)[2]; break;
case 1: temp-=(*p1)[2]; break;
case 2: temp*=(*p1)[2]; break;
case 3: if ((*p1)[2]&&(temp%(*p1)[2]==0))
{ temp=temp/(*p1)[2];
break;
}
else return(0);
}
switch((*p2)[2])
{ case 0: temp+=(*p1)[3]; break;
case 1: temp-=(*p1)[3]; break;
case 2: temp*=(*p1)[3]; break;
case 3: if ((*p1)[3]&&(temp%(*p1)[3]==0))
{ temp=temp/(*p1)[3];
break;
}
else return(0);
}
return(temp);
}
int get2(int (*p1)[4],char (*p2)[3])
{ int temp;
switch((*p2)[1])
{ case 0: temp=(*p1)[1]+(*p1)[2]; break;
case 1: temp=(*p1)[1]-(*p1)[2]; break;
case 2: temp=(*p1)[1]*(*p1)[2]; break;
case 3: if ((*p1)[2]&&((*p1)[1]%(*p1)[2]==0))
{ temp=(*p1)[1]/(*p1)[2];
break;
}
else return(0);
}
switch((*p2)[0])
{ case 0: temp=(*p1)[0]+temp; break;
case 1: temp=(*p1)[0]-temp; break;
case 2: temp=(*p1)[0]*temp; break;
case 3: if ((temp)&&((*p1)[0]%temp==0))
{ temp=(*p1)[0]/temp;
break;
}
else return(0);
}
switch((*p2)[2])
{ case 0: temp+=(*p1)[3]; break;
case 1: temp-=(*p1)[3]; break;
case 2: temp*=(*p1)[3]; break;
case 3: if ((*p1)[3]&&(temp%(*p1)[3]==0))
{ temp=temp/(*p1)[3];
break;
}
else return(0);
}
return(temp);
}
int get3(int (*p1)[4],char (*p2)[3])
{ int temp;
switch((*p2)[1])
{ case 0: temp=(*p1)[1]+(*p1)[2]; break;
case 1: temp=(*p1)[1]-(*p1)[2]; break;
case 2: temp=(*p1)[1]*(*p1)[2]; break;
case 3: if ((*p1)[2]&&((*p1)[1]%(*p1)[2]==0))
{ temp=(*p1)[1]/(*p1)[2];
break;
}
else return(0);
}
switch((*p2)[2])
{ case 0: temp+=(*p1)[3]; break;
case 1: temp-=(*p1)[3]; break;
case 2: temp*=(*p1)[3]; break;
case 3: if ((*p1)[3]&&(temp%(*p1)[3]==0))
{ temp=temp/(*p1)[3];
break;
}
else return(0);
}
switch((*p2)[0])
{ case 0: temp=(*p1)[0]+temp; break;
case 1: temp=(*p1)[0]-temp; break;
case 2: temp=(*p1)[0]*temp; break;
case 3: if ((temp)&&(*p1)[0]%temp==0)
{ temp=(*p1)[0]/temp;
break;
}
else return(0);
}
return(temp);
}
int get4(int (*p1)[4],char (*p2)[3])
{ int temp;
switch((*p2)[2])
{ case 0: temp=(*p1)[2]+(*p1)[3]; break;
case 1: temp=(*p1)[2]-(*p1)[3]; break;
case 2: temp=(*p1)[2]*(*p1)[3]; break;
case 3: if ((*p1)[3]&&((*p1)[2]%(*p1)[3]==0))
{ temp=(*p1)[2]/(*p1)[3];
break;
}
else return(0);
}
switch((*p2)[1])
{ case 0: temp=(*p1)[1]+temp; break;
case 1: temp=(*p1)[1]-temp; break;
case 2: temp=(*p1)[1]-temp; break;
case 3: if ((temp)&&(*p1)[1]%temp==0)
{ temp=(*p1)[1]/temp;
break;
}
else return(0);
}
switch((*p2)[0])
{ case 0: temp=(*p1)[0]+temp; break;
case 1: temp=(*p1)[0]-temp; break;
case 2: temp=(*p1)[0]*temp; break;
case 3: if ((temp)&&(*p1)[0]==0)
{ temp=(*p1)[0]/temp;
break;
}
else return(0);
}
return(temp);
}
int get5(int (*p1)[4],char (*p2)[3])
{ int tmp1,tmp2;
switch((*p2)[0])
{ case 0: tmp1=(*p1)[0]+(*p1)[1]; break;
case 1: tmp1=(*p1)[0]-(*p1)[1]; break;
case 2: tmp1=(*p1)[0]*(*p1)[1]; break;
case 3: if ((*p1)[1]&&((*p1)[0]%(*p1)[1]==0))
{ tmp1=(*p1)[0]/(*p1)[1];
break;
}
else return(0);
}
switch((*p2)[2])
{ case 0: tmp2=(*p1)[2]+(*p1)[3]; break;
case 1: tmp2=(*p1)[2]-(*p1)[3]; break;
case 2: tmp2=(*p1)[2]*(*p1)[3]; break;
case 3: if ((*p1)[3]&&((*p1)[2]%(*p1)[3]==0))
{ tmp2=(*p1)[2]/(*p1)[3];
break;
}
else return(0);
}
switch((*p2)[1])
{ 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[24][4],(*pp1)[4],input[4],goal,i,j,k,m,n;
char (*pp2)[3],code[64][3];
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[m][0]=i;
code[m][1]=j;
code[m][2]=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[n][0]=input;
num[n][1]=input[j];
num[n][2]=input[k];
num[n][3]=input[m];
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[12];
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[3]=(*pp2)[0];
analyst[6]=(*pp2)[1];
analyst[9]=(*pp2)[2];
if((analyst[3]=='*')||(analyst[3]=='/')||
(analyst[6]=='+')||(analyst[6]=='-'))
{ analyst[1]='0'; analyst[5]='0'; }
if((analyst[6]=='*')||(analyst[6]=='/')||
(analyst[9]=='+')||(analyst[9]=='-'))
{ analyst[0]='0'; analyst[8]='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[2]=(*pp2)[0];
analyst[5]=(*pp2)[1];
analyst[9]=(*pp2)[2];
if((analyst[2]=='+')||(analyst[2]!='/')&&
((analyst[5]=='*')||(analyst[5]=='/')))
{ analyst[3]='0'; analyst[7]='0'; }
if((analyst[2]=='*')||(analyst[2]=='/')||
(analyst[9]=='+')||(analyst[9]=='-'))
{ analyst[0]='0'; analyst[8]='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[1]=(*pp2)[0];
analyst[5]=(*pp2)[1];
analyst[8]=(*pp2)[2];
if((analyst[5]=='*')||(analyst[5]=='/')||
(analyst[8]=='+')||(analyst[8]=='-'))
{ analyst[3]='0'; analyst[7]='0'; }
if((analyst[1]=='+')||(analyst[1]!='/')&&
((analyst[8]=='*')||(analyst[8]=='/')))
{ analyst[2]='0'; analyst[10]='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[1]=(*pp2)[0];
analyst[4]=(*pp2)[1];
analyst[7]=(*pp2)[2];
if((analyst[4]=='+')||(analyst[4]!='/')&&
((analyst[7]=='*')||(analyst[7]=='/')))
{ analyst[5]='0'; analyst[9]='0'; }
if((analyst[1]=='+')||(analyst[1]!='/')&&
((analyst[4]=='*')||(analyst[4]=='/')))
{ analyst[2]='0'; analyst[10]='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[2]=(*pp2)[0];
analyst[5]=(*pp2)[1];
analyst[8]=(*pp2)[2];
if((analyst[2]=='*')||(analyst[2]=='/')||
(analyst[5]=='+')||(analyst[5]=='-'))
{ analyst[0]='0'; analyst[4]='0'; }
if((analyst[5]=='+')||(analyst[5]!='/')&&
((analyst[8]=='*')||(analyst[8]=='/')))
{ analyst[6]='0'; analyst[10]='0'; }
}
for(i=0;i<11;i++)
switch(analyst)
{ case 'a': cout<<(*pp1)[0]; break;
case 'b': cout<<(*pp1)[1]; break;
case 'c': cout<<(*pp1)[2]; break;
case 'd': cout<<(*pp1)[3]; break;
case '0': break;
default: cout<<analyst;
}
cout<<endl;
}
else
{ for(i=0,pp1=num;i<24;i++,pp1++)
{ j=(*pp1)[0]*(*pp1)[1];
k=(*pp1)[0]*(*pp1)[2];
if(k%(*pp1)[3]==0)
{ k/=(*pp1)[3];
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)[0]*(*pp1)[3];
k=(*pp1)[1]*(*pp1)[3];
n=(*pp1)[2];
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)[0]<<"*("<<(*pp1)[1]<<'+'
<<(*pp1)[2]<<'/'<<(*pp1)[3]<<')'<<endl;
break;
case 2:cout<<(*pp1)[0]<<"*("<<(*pp1)[1]<<'-'
<<(*pp1)[2]<<'/'<<(*pp1)[3]<<')'<<endl;
break;
case 3:cout<<(*pp1)[0]<<"*("<<(*pp1)[1]<<'/'
<<(*pp1)[2]<<'-'<<(*pp1)[3]<<')'<<endl;
break;
case 4:cout<<(*pp1)[0]<<"/("<<(*pp1)[1]<<'+'
<<(*pp1)[2]<<'/'<<(*pp1)[3]<<')'<<endl;
break;
case 5:cout<<(*pp1)[0]<<"/("<<(*pp1)[1]<<'-'
<<(*pp1)[2]<<'/'<<(*pp1)[3]<<')'<<endl;
break;
case 6:cout<<(*pp1)[0]<<"/("<<(*pp1)[1]<<'/'
<<(*pp1)[2]<<'-'<<(*pp1)[3]<<')'<<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 + +,-,*,/ *,/ +,-,*,/
// *,- *,/
|
ko20010214
=================================
大功告成，打个Kiss!
ko20010214@MSN.com
神州优雅Q300C
Intel CeleronM 370处理器 | 256MbDDR内存
40G硬盘 | USB2.0 | IEEE 1394
13.3 ' WXGA 宽屏(16:10) | COMBO光驱
10/100M网卡 | 四合一读卡器
|
|
|
2003-6-15 00:00 |
|
|
ko20010214
版主
积分 7294
发帖 1628
注册 2002-10-16
状态 离线
|
『第
3 楼』:
再贴一个程序：也是清华的， 算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[4])(double,double)={add,sub,mul,div};
const char op[4]={'+','-','*','/'};
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[4];
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[0].f-DES)<PRE)flag=output(f[0]);
}
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[l]=f[l];
for(l=i+1;l<j;l++)h[l]=f[l];
for(l=j;lPRE)
{
h.f=fun[k](f.f,f[j].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[k](f[j].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的问题，爽！
有没有人看得懂啊？回个贴。
|
ko20010214
=================================
大功告成，打个Kiss!
ko20010214@MSN.com
神州优雅Q300C
Intel CeleronM 370处理器 | 256MbDDR内存
40G硬盘 | USB2.0 | IEEE 1394
13.3 ' WXGA 宽屏(16:10) | COMBO光驱
10/100M网卡 | 四合一读卡器
|
|
|
2003-6-15 00:00 |
|
|
