求算24点的程序,要求快且求出所有解!

mathematica · 发表于 2012-4-12 14:06:40

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

给出4个整数.
1,2,3,4允许改变顺序,则可以是4,3,2,1

分四类情况:
A\允许改变数字顺序,不允许使用括号,使用加减乘除.
B\允许改变数字顺序,允许使用括号,使用加减乘除.
C\不允许改变数字顺序,不允许使用括号,使用加减乘除.
D\不允许改变数字顺序,允许使用括号,使用加减乘除.

在这四种情况下,写出程序!

8\8\4\3
先给一个,看谁先算出来

wayne · 发表于 2012-4-12 14:29:44

C {-23, -13, -(23/2), -10, -9, -8, -(13/2), -5, -4, -(23/6), -(11/3), -(10/3), -(5/2), -(7/3), -2, -(7/4), -(5/3), -1, -(1/2), -(1/ 4), 0, 1/24, 1/6, 3/8, 2/3, 5/6, 1, 7/6, 5/4, 3/2, 2, 9/4, 5/2, 8/3, 11/4, 3, 11/3, 15/4, 4, 25/6, 13/3, 14/3, 11/2, 17/3, 6, 15/2, 9, 10, 11, 25/2, 14, 15, 24, 25}

TableForm[{#, ToExpression[#]} & /@ Map[StringJoin, Riffle[CharacterRange["1", "4"], #] & /@ Tuples[{"+", "-", "*", "/"}, {3}]]]

复制代码

mathe · 发表于 2012-4-13 08:28:30

找到一个过去写的c++代码

#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff,
0x3f,0x30f3f,0xaaff,0x20b,0xaaff,0x2cb2cb,0x1c71c7};
short table[]={
0, 65, 130, 195, 132, 261, 134, 199,
328, 201, 138, 203, 140, 205, 142, 207,
402, 467, 537, 410, 475, 412, 605, 414,
479, 354, 227, 164, 229, 166, 231, 42,
107, 172, 237, 174, 303, 691, 436, 501,
438, 503, 1416, 1481, 1738, 1803, 1420, 1485,
1871, 1432, 1497, 1754, 1819, 1436, 1501, 1887,
1760, 1825, 1442, 1507, 1893, 1446, 1511, 1776,
1841, 1458, 1523, 1909, 1462, 1527, 2883, 2503,
2899, 2519, 2921, 2541, 2937, 2557, 3331, 3975,
3915, 3535, 3287, 3931, 3551, 3937, 3557, 3369,
4013, 3953, 3573, 3325, 4301, 4573, 4327, 4599
};
short o0[24];
short o1[24];
short o2[24];
short o3[24];
char opprint[]={'+','-','*','/'};
int mask_cd,mask_bcd,mask_ab_cd;
#define mask_null 0xFFFFFF
#define mask_abcd 1
struct expression{
int value;
expression(int v):value(v){ }
int first_op()const{
return value & 3;
}
int second_op()const{
return (value >> 2)&3;
}
int third_op()const{
return (value >> 4)&3;
}
int graph_type()const{
return (value >> 6)/24;
}
int num_order()const{
return (value >> 6)%24;
}
};
typedef int INT;
struct factor_num{
INT up;
INT down;
factor_num(){}
factor_num(INT u,INT d):up(u),down(d){ }
};
typedef factor_num (*OperatorFun)(const factor_num& x,const factor_num& y);
factor_num sum(const factor_num& i,const factor_num& j){
INT d,u;
if(i.down==0||j.down==0){
d=0;
}else{
d=i.down * j.down;
u=i.up * j.down + j.up * i.down;
}
return factor_num(u,d);
}
factor_num dif(const factor_num& i,const factor_num& j){
INT d,u;
if(i.down==0||j.down==0){
d=0;
}else{
d=i.down * j.down;
u=i.up * j.down - j.up * i.down;
}
return factor_num(u,d);
}
factor_num prod(const factor_num& i,const factor_num& j){
INT d,u;
u=i.up * j.up;
d=i.down * j.down;
return factor_num(u,d);
}
factor_num ratio(const factor_num& i,const factor_num& j){
INT d,u;
if(i.down == 0 || j.down==0){
d=0;
}else{
d=i.down * j.up;
u=i.up * j.down;
}
return factor_num(u,d);
}
OperatorFun funs[]={sum,dif,prod,ratio};
bool equal_num(const factor_num& i,INT j)
{
if(i.down==0){
return false;
}else{
return i.up == j * i.down;
}
}
void show(INT input[],expression expr){
int order=expr.num_order();
INT aa=input[o0[order]];
INT bb=input[o1[order]];
INT cc=input[o2[order]];
INT dd=input[o3[order]];
short op1=expr.first_op();
char ops1=opprint[op1];
short op2=expr.second_op();
char ops2=opprint[op2];
short op3=expr.third_op();
char ops3=opprint[op3];
switch(expr.graph_type()){
case 0:
if(op1<2 && op2 >=2){
printf("(%d%c%d)%c",aa,ops1,bb,ops2);
} else {
printf("%d%c%d%c",aa,ops1,bb,ops2);
}
if(op2>=op3){
printf("(%d%c%d)",cc,ops3,dd);
}else{
printf("%d%c%d",cc,ops3,dd);
}
break;
case 1:
if(op2<2&&op3>=2)
printf("(");
if(op1<2&&op2>=2)
printf("(");
printf("%d%c%d",aa,ops1,bb);
if(op1<2&&op2>=2)
printf(")");
printf("%c%d",ops2,cc);
if(op2<2&&op3>=2)
printf(")");
printf("%c%d",ops3,dd);
break;
case 2:
if(op1<2&&op3>=2)
printf("(");
printf("%d%c",aa,ops1);
if(op1>=op2)
printf("(");
printf("%d%c%d",bb,ops2,cc);
if(op1>=op2)
printf(")");
if(op1<2&&op3>=2)
printf(")");
printf("%c%d",ops3,dd);
break;
case 3:
printf("%d%c",aa,ops1);
if(op1>=op3)
printf("(");
if(op2<2&&op3>=2)
printf("(");
printf("%d%c%d",bb,ops2,cc);
if(op2<2&&op3>=2)
printf(")");
printf("%c%d",ops3,dd);
if(op1>=op3)
printf(")");
break;
case 4:
printf("%d%c",aa,ops1);
if(op1>=op2)
printf("(");
printf("%d%c",bb,ops2);
if(op2>=op3)
printf("(");
printf("%d%c%d",cc,ops3,dd);
if(op2>=op3)
printf(")");
if(op1>=op2)
printf(")");
break;
}
}
#define elems(x) (sizeof(x)/sizeof(x[0]))
void c_main(INT input[],int mask,INT result)
{
int total=0;
int i;
factor_num r1,r2,r;
for(i=0;i<elems(table);i++){
int op=table[ i]&63;
int left=table[ i]>>6;
int g=left>>4;
int pl=left&15;
int pattern=pm[pl]&mask;
int j;
for(j=0;j<24;j++){
if(pattern&(1<<j)){
short elem=(j+g*24)*64+op;
expression t(elem);
short op1=t.first_op();
short op2=t.second_op();
short op3=t.third_op();
short gtype=t.graph_type();
short order=t.num_order();
factor_num aa=factor_num(input[o0[order]],1);
factor_num bb=factor_num(input[o1[order]],1);
factor_num cc=factor_num(input[o2[order]],1);
factor_num dd=factor_num(input[o3[order]],1);
OperatorFun fun1=funs[op1];
OperatorFun fun2=funs[op2];
OperatorFun fun3=funs[op3];
switch(gtype){
case 0:
r1=fun1(aa,bb);
r2=fun3(cc,dd);
r=fun2(r1,r2);
break;
case 1:
r1=fun1(aa,bb);
r2=fun2(r1,cc);
r=fun3(r2,dd);
break;
case 2:
r1=fun2(bb,cc);
r2=fun1(aa,r1);
r=fun3(r2,dd);
break;
case 3:
r1=fun2(bb,cc);
r2=fun3(r1,dd);
r=fun1(aa,r2);
break;
case 4:
r1=fun3(cc,dd);
r2=fun2(bb,r1);
r=fun1(aa,r2);
break;
}
if(equal_num(r,result)){
show(input,t);
printf("/t");
total++;
}
}
}
}
if(total)printf("/n");
}
void c24(INT s1,INT s2,INT s3,INT s4,INT r){
INT input[4];
int i,j;
input[0]=s1;input[1]=s2;input[2]=s3;input[3]=s4;
for(i=0;i<4;i++){
for(j=i+1;j<4;j++){
if(input[j]<input[ i]){
INT temp=input[j];
input[j]=input[ i];
input[ i]=temp;
}
}
}
if(input[0]==input[1]){//a==b
if(input[1]!=input[2]){
if(input[2]!=input[3]){//only a==b
INT temp=input[2];
input[2]=input[0];
input[0]=temp;
temp=input[3];
input[3]=input[1];
input[1]=temp;
c_main(input,mask_cd,r);
}else{//a==b,c==d
c_main(input,mask_ab_cd,r);
}
}else if(input[2]!=input[3]){//a==b==c!=d
INT temp=input[0];
input[0]=input[3];
input[3]=temp;
c_main(input,mask_bcd,r);
}else{//a==b==c==d
c_main(input,mask_abcd,r);
}
}else{//a!=b
if(input[1]==input[2]){
if(input[2]!=input[3]){//b==c
INT temp=input[3];
input[3]=input[1];
input[1]=temp;
c_main(input,mask_cd,r);
}else{//b==c==d
c_main(input,mask_bcd,r);
}
}else{
if(input[2]==input[3]){//c==d
c_main(input,mask_cd,r);
}else{
c_main(input,mask_null,r);
}
}
}
}
#define N 13
void init()
{
INT i=0;
short a[4]={0,1,2,3};
do{
o0[ i]=a[0];
o1[ i]=a[1];
o2[ i]=a[2];
o3[ i]=a[3];
i++;
}while(next_permutation(a,a+4));
for(i=0;i<24;i++){
short inv[4];
inv[o0[ i]]=0;
inv[o1[ i]]=1;
inv[o2[ i]]=2;
inv[o3[ i]]=3;
if(inv[2]<inv[3]){
mask_cd|=(1<<i);
}
if(inv[1]<inv[2]&&inv[2]<inv[3]){
mask_bcd|=(1<<i);
}
if(inv[0]<inv[1]&&inv[2]<inv[3]){
mask_ab_cd|=(1<<i);
}
}
}
int bits(int x){
int b=0,i;
for(i=0;i<32;i++)if(x&(1<<i))b++;
return b;
}
int main()
{
INT i=0,j,k,m;
init();
for(i=1;i<=N;i++)for(j=i;j<=N;j++)for(k=j;k<=N;k++)for(m=k;m<=N;m++){
c24(i,j,k,m,24);
}
}

复制代码

mathematica · 发表于 2012-4-13 11:48:19

C {-23, -13, -(23/2), -10, -9, -8, -(13/2), -5, -4, -(23/6), -(11/3), -(10/3), -(5/2), -(7/3), -2, -(7/4), -(5/3), -1, -(1/2), -(1/ 4), 0, 1/24, 1/6, 3/8, 2/3, 5/6, 1, 7/6, 5/4, 3/2, 2, 9/4, 5/2, 8/3 ... wayne 发表于 2012-4-12 14:29

文字内容和代码都没看明白!

mathematica · 发表于 2012-4-13 11:49:31

找到一个过去写的c++代码#include #include #include using namespace std; int pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff, ... mathe 发表于 2012-4-13 08:28

没有注释的程序,将来自己能看明白吗? 我很怀疑! 我觉得那么长的程序,还不如弄成压缩一下传上来呢对了,最好还有注释与说明,不然程序真的很难懂!

mathe · 发表于 2012-4-13 11:52:21

其实这个代码几乎不包含什么有用的信息，主要是一个表格，包含了四个数的不等价的表达式的一种编码后的形式。而产生表格的代码我已经找不到。

zgg___ · 发表于 2012-4-13 14:37:59

文字内容和代码都没看明白! mathematica 发表于 2012-4-13 11:48

赫赫，wayne的意思是：

(* 关于题目中的情况C： *)
s[z_] := Select[Map[StringJoin,Riffle[Map[ToString, z], #] & /@Tuples[{"+", "-", "*", "/"}, {3}]],ToExpression[#] == 24 &]; (* 这里套用wayne的代码 *)
{1, 2, 3, 4} // s (* 例子一 *)
{8, 8, 4, 3} // s (* 例子二 *)

复制代码

其实，我个人喜欢他们的风格，赫赫。

zgg___ · 发表于 2012-4-13 15:42:19

还可以用x~jia~y来表示(x+y)，赫赫。

wayne · 发表于 2012-4-15 10:59:39

7# zgg___

，逃不过zgg的慧眼感觉有括号的情况要麻烦些

mathe · 发表于 2012-4-18 13:20:45

我也看不懂，Mathematica的函数真多

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 求算24点的程序,要求快且求出所有解!

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评