求算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___
:loveliness:，逃不过zgg的慧眼
感觉有括号的情况要麻烦些 我也看不懂，Mathematica的函数真多