计算24点的程序及分析过程
最近正在学习数据结构。和同事闲聊时，聊到了24点的问题（就是给出4个数，然后用加减剩除及括号算出24来），记得前一阵还在网上看了一道24点的题： 5 5 5 1 ，如何算出24来？当时想了好长时间没想出来。最近工作不是很忙就自己写一下程序练习一下吧。
以下讲述的是我思考该问题的思路及方法，如有不当之处请赐教：）
我首先想到的是用穷举法，因为就4 个数和4 个运算符再加上括号，表达式的数量不会很多，我算了一下，运算数：4×3×2×1=24,运算符：4×4×4×4=256,再括号应该是10种（没有优化的情况），总共是：24×256×10=61440，用穷举的话也很快（其实是想不到时其它办法：）
要穷举的话，可以大体分为三部分：
1.生成表达式
2.计算表达式的值
3.输出正确的结果
其中以上三步最复杂的是第一步（其实要是写程序的话，第2步应该是最麻烦的，但是php已经为我们提供的简单的方法，稍后讨论）
生成表达式时，我决定采用递归来写，原因是写起来简单些，但效率会稍低一些。
生成表达式也就是一个组合的问题，大体算法就像这样：
$str = array(1,2,3,4);
$r = array();
function c($k)
{
global $str;
global $r;
if ( $k == 4 ) {
display();
return;
}
for ($i = 0; $i < 4; $i++) {
$r[$k] = $str[$i];
c($k+1);
}
}
以上程序稍加改动就成了N皇后的解法。
还是感觉用递归写比较简洁一些。
有了以上的程序，再做一睦简单的改动便可以生成我们所需要的表达式（详见后面的程序）。
另外还有一点就是括号的问题，为了减少复杂度，我是直接在生成的表达式里添加上括号的，把所有的括号形式都写上（最好优化一下，要不然会产生很多有多余括号的表达式）。
写好了生成表达式的函数后，这个程序的工作就算做完一多半了。第二步计算表达式的值我用到了php的一个函数：eval(),有了这个函数可真是省了不少力，只需一行便能把字符串的表达式算出结果（具体用法可以查一下手册），妙！
剩下的第三点就简单了，真是输出一下结果而以。
以下是程序的完整代码，如有好的建议请多多指教：
<?php
/***************************************************************************************
* 功能：本程序的功能是给出4个数，求出通过 '+'、'-'、'*'、'/'及括号运算,结果为24的所有解
* 参数说明:接收4个数字，用空格分开
* es: 24point 1 2 3 4
* 输出：输出所有正确的解
*
* Author : xks
* Email : xks@anymacro.com
*
* 一 8月 22 16:45:48 CST 2005
***************************************************************************************/
define('OPERANDNUM', 4); //支持的运算数的个数，本程序只支持4个
define('RESULT', 24); //所要求的结果是24, 也可改为其它值
$operand = array(); //运算数
$operator = array('+', '-', '*', '/'); //运算符(不包括括号，括号在本程序中直接加上的）
$exp = array(); //生成的表达式
$rightexp = array(); //正确的表达式
$rightnum = 0; //正确的表达式的数目
$lenoperator = count($operator); //运算符的个数(不包括括号)
$lenexp = $lenoperator + OPERANDNUM; //整个表达式的长度（不包括号)
//从命令行接收运算数,本程序只支持4个
if ($argc != OPERANDNUM + 1) {
echo "Arguments error!\n";
echo "es: 24point 1 2 3 4\n";
return;
}
else {
for ($i = 0; $i < OPERANDNUM; $i++)
$operand[$i] = $argv[$i+1];
}
$opetimes = array_count_values(array_slice($operand, 0));//统计每个运算数出现的次数，
//用来检测是否有重复表达式
//开始计算
Createexp(0);
//递归函数，用来根据输入的运算数生成表达式，并且调用 calculate()函数计算表达式的结果
function CreateExp($k)
{
global $operator;
global $operand;
global $lenoperator;
global $exp;
global $lenexp;
global $opetimes;
$i = 0;//运算数计数
$j = 0;//运算符计数
//生成表达式后传给 calculate()计算
if ($k == $lenexp - 1) {
calculate($exp);
return;
}
while ($i < OPERANDNUM && $j < $lenoperator) {
//当k为奇数时，则$exp[$k]应该填入运算符，否则$exp[$k]应该填入运算数
//ps:我在写这条注释的时候，突然头脑中闪过一个问题：0是偶数吧?呵呵小学里的概念都记不清
//了，我问了两位同事竟然也有不同的答案，google了一下，竟然发现有好多人在讨论 0是奇数
//还是偶然的问题，真是有意思。所以这里先定为奇数和非奇数吧:)
if ($k % 2 == 0) {
/* 去除相同数字开头的表达式，避免产生重复的表达式
* 例如:3 5 3 2 ,以第一个3开头的表达式和以第二个3开头的表达式是相同的，
* 所以如果运算数中有相同的数字，则只处理第一个出现的数字
*/
if ( in_array($operand[$i], array_slice($operand, 0, $i)) && $k == 0) {
break;
}
//测试一个表达式中是否有超过运算数出现的次数的数,不太好理解，也就是说
//比如4个运算数为：3 5 3 2 ，下面的语句就是为了防止一个表达式中
//出现3个3的情况
$expcount = array_count_values(array_slice($exp, 0, $k));
if ($expcount[$operand[$i]]=='' ||
$expcount[$operand[$i]] < $opetimes[$operand[$i]] ) {
$exp[$k] = $operand[$i++];
}
else {
$i++;
continue;
}
}
else { //奇数的情况
$exp[$k] = $operator[$j++];
}
//递归调用
CreateExp($k+1);
}
}
function calculate($exp)
{
global $rightexp;
global $rightnum;
global $rightnum;
//去除重复的表达式，我在本程序中的做法是将正确的表达式存到一个数组中，产生新的表达式时，
//先在数组中查找一下是否已经出现过。Not a good idea! 但暂时想不到更好的办法。
//虽然在前面已经做了部分过滤工作，但是当运算数有重复值的时候还是无法避免出现产生重复表达式
//只好采用此方法
$strexp = implode('', $exp);
if ( array_search( $strexp, $rightexp ))
return;
$rightexp[$rightnum++] = $strexp;
$exp2 = array();
$i = 0;
/* 以下是对添加上括号的表达式处理方法，已经做过优化，不会产生多余括号的情况
* 具体方法可以自己分析一下，写的不是很优雅。
* 4个数可以产生的表达式变形如下(运算数之间的空格用运算符填充):
* a b c d
* a b (c d)
* (a b) (c d)
* (a b c) d
* a (b c) d
* a (b c d)
* 另外还有4种情况，经过分析后都可以优化掉。
*/
$exp2[$i++] = "$exp[0]$exp[1]$exp[2]$exp[3]$exp[4]$exp[5]$exp[6]";
if ( mulordiv($exp[3]) && addorsub($exp[5]))
$exp2[$i++] = "$exp[0]$exp[1]$exp[2]$exp[3]($exp[4]$exp[5]$exp[6])";
if ( mulordiv($exp[3]) && mulordiv($exp[5]) && addorsub($exp[3]))
$exp2[$i++] = "($exp[0]$exp[1]$exp[2])$exp[3]($exp[4]$exp[5]$exp[6])";
if ( mulordiv($exp[5]) && (addorsub($exp[1]) || addorsub($exp[3])) )
$exp2[$i++] = "($exp[0]$exp[1]$exp[2]$exp[3]$exp[4])$exp[5]$exp[6]";
if ( (mulordiv($exp[1]) || mulordiv($exp[5])) && addorsub($exp[3]) )
$exp2[$i++] = "$exp[0]$exp[1]($exp[2]$exp[3]$exp[4])$exp[5]$exp[6]";
if ( (mulordiv($exp[1]) || mulordiv($exp[5])) && addorsub($exp[3]) )
$exp2[$i++] = "$exp[0]$exp[1]($exp[2]$exp[3]$exp[4])$exp[5]$exp[6]";
if ( (addorsub($exp[1]) || addorsub($exp[3])) && mulordiv($exp[1]) )
$exp2[$i++] = "$exp[0]$exp[1]($exp[2]$exp[3]$exp[4]$exp[5]$exp[6])";
if ( addorsub($exp[1]) && mulordiv($exp[3]) )
$exp2[$i++] = "($exp[0]$exp[1]$exp[2])$exp[3]$exp[4]$exp[5]$exp[6]";
// 计算表达式的值，其中有一个很重要的技巧：eval(),这个函数可真是好用，帮我省掉了1xx行代码
// 利用这个函数可以直接求出表达式的值，而不用再去分析表达式以及运算符的优先级等等
// 求表达式的值属于编译原理的知识，如果你正在学的话，那自己写个求表达式的程序练习一下
//是个不错的建议 u
for ($j = 0; $j < $i; $j++) {
$result = 0;
@eval("\$result=$exp2[$j];");
if ($result == RESULT) {
display($exp2[$j]);
}
}
}
//显示表达式
function display($exp)
{
echo $exp . '=' . RESULT ."\n";
}
//测试$opt 是否为'+' or '-'
function addorsub($opt)
{
return ($opt == '+' || $opt == '-');
}
//测试$opt 是否为'*' or '/'
function mulordiv($opt)
{
return ($opt == '*' || $opt == '/');
}
?>
