TooBugJavaScript版24点
2010年5月12日
前几天去森林公园烧烤，和同学一起玩24点。以前玩过，再次玩起来还是觉得不甘心，尤其是当我们都认为无解的情况。
回来后就想写24点的计算程序，想了一下，似乎除了穷举之外没有其他的方法，上网搜了一下，也都是用的穷兴举法。不过算法不算很高效，其中http://www.blogjava.net/comic222/archive/2009-01-06/250101.html所述算法取2个数字有6种取法，运算有6种（减法和除法是有顺序的），第二次取数有3种取法，运算有6种，第三次取数有1种取法，运算有6种，所以一共有6*6*3*6*1*6=3888个表达式，而http://hi.baidu.com/greation/blog/item/1f68fbfa808d10d9b58f3106.html就更夸张了，直接用循环（多少重，我没数……）要判断次数：4*3*2*1*4*4*4*11=16896。（不过这个思路挺好的，设定了11个表达式形式，不过经我验证，第一个表达式可以完全归入下面十个。）
分析发现，在穷举过程中存在大量重复表达式，比如1，2，3，4这四个数字，1+2+3+4要运算一次，2+1+3+4又要运算一次，这样1+2+3+4等价的表达式就多达24个！
为了尽量减少重复表达式，我决定将表达式按运算符类型分类，方案如下：
- 将所有只含有加减法提出来，将第一个数字前面也加上运算符，共有4个运算符，所以共有2^4=16种运算符方案，因为加减法是可以交换可以结合的，所以等价的表达式就不用再验证。又因为24点中不能4个数字前全是减号（负号），即至少有一个正数作为被减数，所以共有16-15个表达式；同理可知，只含有乘除法的表达式有15个（除号放在数前面用“1/”表式，即该数的倒数）。
- 若是两端乘除再中间一加减（如2*9+1*6），用于乘除的两两组合有C(4,2)/2=3种，每个乘除运算有3种（两数相乘，前者除后者，后者除前者），加减有3种（两数相加，前者减后者，后者减前者），共有3*3^2*3=81个表达式；同理，若是两端加减再中间一乘除，共有81个表达式。
- 若是前面两个乘除运算，后面一个加减运算，用于乘除运算的数字组合有4种选择，乘除方案有2^3-1=7种（因为不能全是除，所以减一），加减有3种，共有4*7*3=84个表达式，同理，若是先两个加减运算，再一个乘除运算，有84个表达式。
- 若是先乘除一次，再加减一次，再加减或者乘除一次，则第一步乘除运算取数字有6种取法，乘除方案有3种，第二步取数字有2种取法，加减方案有3种，第三步取数字有1种取法，加减乘除方案有7种（2*4-1），共有6*3*2*3*1*7=756个表达式；同理，先加减再乘除再加减，共有756个表达式。
共计需要判断的表达式有15+15+81+81+84+84+756+756=1872个。
已经用JavaScript实现，未加入对输入是否合法的判断。因为乘法中“负负得正”，所以有时候会出现几乎重复的方案，是否能够进一步优化待尚探讨。凌晨2点写完。以下是具体的程序代码：
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>JavaScript 24点</title>
</head>
<body>
数1：<input type="text" /><br />
数2：<input type="text" /><br />
数3：<input type="text" /><br />
数4：<input type="text" /><br />
<input type="submit" value="计算" onclick="startcalc();" />
<div id="result"></div>
</body>
<script language="javascript">
var n=new Array(0,0,0,0)
var o=new Array("","","","","","")
var count=0;
function check(expression)
{
count++;
if (Math.abs(eval(expression)-24)<0.0001)
{
document.getElementById("result").innerHTML=document.getElementById("result").innerHTML+"第"+count+"次判断，找到有效解："+expression+"<br />";
}
}
function startcalc()
{
count=0;
for (var i=0;i<4;i++)
{
n[i]=document.getElementsByTagName("input")[i].value;
}
//全加减和全乘除，类似a+b-c+d
for (var i=0;i<2;i++)
for (var j=0;j<2;j++)
for (var k=0;k<2;k++)
for (var l=0;l<2;l++)
{
//加减
o[0]=["","-"][i];
o[1]=["+","-"][j];
o[2]=["+","-"][k];
o[3]=["+","-"][l];
if(!(o[0]=="-"&&o[1]=="-"&&o[2]=="-"&&o[3]=="-"))
check(o[0]+n[0]+o[1]+n[1]+o[2]+n[2]+o[3]+n[3]);
//乘除
o[0]=["","1/"][i];
o[1]=["*","/"][j];
o[2]=["*","/"][k];
o[3]=["*","/"][l];
if(!(o[0]=="1/"&&o[1]=="/"&&o[2]=="/"&&o[3]=="/"))
check(o[0]+n[0]+o[1]+n[1]+o[2]+n[2]+o[3]+n[3]);
}
//两端乘除中间加减或者两端加减中间乘除，如（6-2）*（8-2）
for(var i=1;i<4;i++)
{
var temparr=new Array(0,0,0,0);
temparr=n;
var tempnum=temparr[i];
temparr[i]=temparr[1];
temparr[1]=tempnum;
for(var j1=0;j1<2;j1++)
for(var j2=0;j2<2;j2++)
for(var j3=0;j3<2;j3++)
for(var j4=0;j4<2;j4++)
for(var j5=0;j5<2;j5++)
for(var j6=0;j6<2;j6++)
{
//先加减后乘除
o[0]=["","1/"][j1];
o[1]=["","-"][j2];
o[2]=["+","-"][j3];
o[3]=["*","/"][j4];
o[4]=["","-"][j5];
o[5]=["+","-"][j6];
if(!(o[0]=="1/"&&o[3]=="/") && !(o[1]=="-"&&o[2]=="-") && !(o[4]=="-"&&o[5]=="-"))
check(o[0]+"("+o[1]+temparr[0]+o[2]+temparr[1]+")"+o[3]+"("+o[4]+temparr[2]+o[5]+temparr[3]+")");
//先乘除后加减
o[0]=["","-"][j1];
o[1]=["","1/"][j2];
o[2]=["*","/"][j3];
o[3]=["+","-"][j4];
o[4]=["","1/"][j5];
o[5]=["*","/"][j6];
if(!(o[0]=="-"&&o[3]=="-") && !(o[1]=="1/"&&o[2]=="/") && !(o[4]=="1/"&&o[5]=="/"))
check(o[0]+o[1]+temparr[0]+o[2]+temparr[1]+o[3]+o[4]+temparr[2]+o[5]+temparr[3]);
}
}
//两次乘除一次加减或者两次加减一次乘除，如3*4*3-12
for(var i=0;i<4;i++)
{
var temparr=new Array(0,0,0,0);
temparr=n;
var tempnum=temparr[i];
temparr[i]=temparr[3];
temparr[3]=tempnum;
for(var j1=0;j1<2;j1++)
for(var j2=0;j2<2;j2++)
for(var j3=0;j3<2;j3++)
for(var j4=0;j4<2;j4++)
for(var j5=0;j5<2;j5++)
{
//先加减后乘除
o[0]=["","1/"][j1];
o[1]=["","-"][j2];
o[2]=["+","-"][j3];
o[3]=["+","-"][j4];
o[4]=["*","/"][j5];
if(!(o[1]=="-"&&o[2]=="-"&&o[3]=="-") && !(o[0]=="1/"&&o[4]=="/"))
check(o[0]+"("+o[1]+temparr[0]+o[2]+temparr[1]+o[3]+temparr[2]+")"+o[4]+temparr[3]);
//先乘除后加减
o[0]=["","-"][j1];
o[1]=["","1/"][j2];
o[2]=["*","/"][j3];
o[3]=["*","/"][j4];
o[4]=["+","-"][j5];
if(!(o[1]=="1/"&&o[2]=="/"&&o[3]=="/") && !(o[0]=="-"&&o[4]=="-"))
check(o[0]+o[1]+temparr[0]+o[2]+temparr[1]+o[3]+temparr[2]+o[4]+temparr[3]);
}
}
//alert(count);
//至此共判断360次，与预期一样
//乘除一次，加减一次，加减乘除一次，或者反过来，如(（3+4）*3)+3
for(var i=0;i<4;i++)
for(var j=i+1;j<4;j++)
{
var temparr=new Array(0,0,0,0);
temparr=n;
var tempnum=temparr[i];
temparr[i]=temparr[0];
temparr[0]=tempnum;
tempnum=temparr[j];
temparr[j]=temparr[1];
temparr[1]=tempnum;
for (var k=2;k<4;k++)
{
tempnum=temparr[k];
temparr[k]=temparr[2]
temparr[2]=tempnum;
for(var j1=0;j1<2;j1++)
for(var j2=0;j2<2;j2++)
for(var j3=0;j3<2;j3++)
for(var j4=0;j4<2;j4++)
for(var j5=0;j5<2;j5++)
for(var j6=0;j6<4;j6++)
{
//先加减后乘除再加减
o[0]=["","-"][j1];
o[1]=["","1/"][j2];
o[2]=["","-"][j3];
o[3]=["+","-"][j4];
o[4]=["*","/"][j5];
o[5]=["+","-","*","/"][j6];
if(!(o[2]=="-"&&o[3]=="-")&&!(o[1]=="1/"&&o[4]=="/")&&!(o[0]=="-"&&o[5]=="-"))
check(o[0]+"("+o[1]+"("+o[2]+temparr[0]+o[3]+temparr[1]+")"+o[4]+temparr[2]+")"+o[5]+temparr[3]);
//先乘除后加减再乘除
o[0]=["","1/"][j1];
o[1]=["","-"][j2];
o[2]=["","1/"][j3];
o[3]=["*","/"][j4];
o[4]=["+","-"][j5];
o[5]=["+","-","*","/"][j6];
if(!(o[2]=="1/"&&o[3]=="/")&&!(o[1]=="-"&&o[4]=="-")&&!(o[0]=="1/"&&o[5]=="/"))
check(o[0]+"("+o[1]+"("+o[2]+temparr[0]+o[3]+temparr[1]+")"+o[4]+temparr[2]+")"+o[5]+temparr[3]);
}
}
}
document.getElementById("result").innerHTML=document.getElementById("result").innerHTML+"共计判断表达式"+count+"次";
}
</script>
</html>
演示地址已经放到https://rawcdn.githack.com/TooBug/works/gh-pages/24points/index.html。