TooBug

Appearance

JavaScript版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个！

为了尽量减少重复表达式，我决定将表达式按运算符类型分类，方案如下：

  1. 将所有只含有加减法提出来，将第一个数字前面也加上运算符，共有4个运算符，所以共有2^4=16种运算符方案，因为加减法是可以交换可以结合的，所以等价的表达式就不用再验证。又因为24点中不能4个数字前全是减号（负号），即至少有一个正数作为被减数，所以共有16-15个表达式；同理可知，只含有乘除法的表达式有15个（除号放在数前面用“1/”表式，即该数的倒数）。
  2. 若是两端乘除再中间一加减（如2*9+1*6），用于乘除的两两组合有C(4,2)/2=3种，每个乘除运算有3种（两数相乘，前者除后者，后者除前者），加减有3种（两数相加，前者减后者，后者减前者），共有3*3^2*3=81个表达式；同理，若是两端加减再中间一乘除，共有81个表达式。
  3. 若是前面两个乘除运算，后面一个加减运算，用于乘除运算的数字组合有4种选择，乘除方案有2^3-1=7种（因为不能全是除，所以减一），加减有3种，共有4*7*3=84个表达式，同理，若是先两个加减运算，再一个乘除运算，有84个表达式。
  4. 若是先乘除一次，再加减一次，再加减或者乘除一次，则第一步乘除运算取数字有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。