求算24点的程序,要求快且求出所有解!
给出4个整数.1,2,3,4允许改变顺序,则可以是4,3,2,1
分四类情况:
A\允许改变数字顺序,不允许使用括号,使用加减乘除.
B\允许改变数字顺序,允许使用括号,使用加减乘除.
C\不允许改变数字顺序,不允许使用括号,使用加减乘除.
D\不允许改变数字顺序,允许使用括号,使用加减乘除.
在这四种情况下,写出程序!
8\8\4\3
先给一个,看谁先算出来 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, #] & /@ Tuples[{"+", "-", "*", "/"}, {3}]]] 找到一个过去写的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; short o1; short o2; short o3; 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]; INT bb=input]; INT cc=input]; INT dd=input]; short op1=expr.first_op(); char ops1=opprint; short op2=expr.second_op(); char ops2=opprint; short op3=expr.third_op(); char ops3=opprint; 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)) 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&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],1); factor_num bb=factor_num(input],1); factor_num cc=factor_num(input],1); factor_num dd=factor_num(input],1); OperatorFun fun1=funs; OperatorFun fun2=funs; OperatorFun fun3=funs; 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; int i,j; input=s1;input=s2;input=s3;input=s4; for(i=0;i<4;i++){ for(j=i+1;j<4;j++){ if(input<input[ i]){ INT temp=input; input=input[ i]; input[ i]=temp; } } } if(input==input){//a==b if(input!=input){ if(input!=input){//only a==b INT temp=input; input=input; input=temp; temp=input; input=input; input=temp; c_main(input,mask_cd,r); }else{//a==b,c==d c_main(input,mask_ab_cd,r); } }else if(input!=input){//a==b==c!=d INT temp=input; input=input; input=temp; c_main(input,mask_bcd,r); }else{//a==b==c==d c_main(input,mask_abcd,r); } }else{//a!=b if(input==input){ if(input!=input){//b==c INT temp=input; input=input; input=temp; c_main(input,mask_cd,r); }else{//b==c==d c_main(input,mask_bcd,r); } }else{ if(input==input){//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={0,1,2,3}; do{ o0[ i]=a; o1[ i]=a; o2[ i]=a; o3[ i]=a; i++; }while(next_permutation(a,a+4)); for(i=0;i<24;i++){ short inv; inv]=0; inv]=1; inv]=2; inv]=3; if(inv<inv){ mask_cd|=(1<<i); } if(inv<inv&&inv<inv){ mask_bcd|=(1<<i); } if(inv<inv&&inv<inv){ 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); } } 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 http://bbs.emath.ac.cn/images/common/back.gif
文字内容和代码都没看明白! 找到一个过去写的c++代码#include
#include
#include
using namespace std;
int pm[]={0x1,0x55,0x10515,0x555555,0x41041,0x15,0x30f3f,0xffffff,
...
mathe 发表于 2012-4-13 08:28 http://bbs.emath.ac.cn/images/common/back.gif
没有注释的程序,将来自己能看明白吗?
我很怀疑!
我觉得那么长的程序,还不如弄成压缩一下传上来呢
对了,最好还有注释与说明,不然程序真的很难懂! 其实这个代码几乎不包含什么有用的信息,主要是一个表格,包含了四个数的不等价的表达式的一种编码后的形式。而产生表格的代码我已经找不到。 文字内容和代码都没看明白!
mathematica 发表于 2012-4-13 11:48 http://bbs.emath.ac.cn/static/image/common/back.gif
赫赫,wayne的意思是:(* 关于题目中的情况C: *)s := Select, #] & /@Tuples[{"+", "-", "*", "/"}, {3}]],ToExpression[#] == 24 &]; (* 这里套用wayne的代码 *){1, 2, 3, 4} // s (* 例子一 *){8, 8, 4, 3} // s (* 例子二 *)其实,我个人喜欢他们的风格,赫赫。 还可以用x~jia~y来表示(x+y),赫赫。 7# zgg___
https://bbs.emath.ac.cn/static/image/smiley/1/loveliness.gif,逃不过zgg的慧眼
感觉有括号的情况要麻烦些 我也看不懂,Mathematica的函数真多
页:
[1]