PHP方法实现1-9数列中添加‘+’，‘-’或'，使和为100，并输出数列

rcwg 2018-03-20 原文

PHP方法实现1-9数列中添加‘+’，‘-’或”，使和为100，并输出数列

今天收到个题目：编写一个在1,2,3,4,5,6,7,8,9(顺序不能变)数字之间插入 + 或- 或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。例如 1+2+34-5+67-8+9=100；
一开始在网上找了好久，发现这个问题是在一篇很火的文章《每个程序员1小时内必须解决的5个编程问题》上的第五题，如图：
这里写图片描述
提供一个php的解决方法，如下：

$str = '123456789';
$newStr = '';
function listarr($str, $newStr)
{
    if(strlen($str) == 1){
        $newStr = $newStr.'9';//最后一位9需要手动加上；
        $v = eval("return $newStr"); //计算公式的结果；
        if($v == 100){
            echo $newStr."<hr/>";
        }
    } else {
        $newStr .= substr($str, 0, 1);
        $str = substr($str,1);
        //递归三种可能
        listarr($str, $newStr.'+');
        listarr($str, $newStr.'-');
        listarr($str, $newStr);
    }
}
listarr($str, $newStr);

但是要注意，在求和的时候使用的是eval函数，这个函数是非常非常危险的，很多人都说木马就是利用eval函数，所以基本上所有的服务器都会禁用eval的；
如果不采用eval函数的话，就需要另外写一个方法手动计算公式的值了：

 1 $str = '123456789';
 2 $newStr = '';
 3 function listarr($str, $newStr)
 4 {
 5     if(strlen($str) == 1){
 6         $newStr = $newStr.'9';//手动加上最后一个9；
 7         $res = cal($newStr);
 8         if($res){
 9             echo $newStr."<hr/>";
10         }
11     } else {
12         $newStr .= substr($str, 0, 1);
13         $str = substr($str, 1);
14 
15         //递归三种可能
16         listarr($str, $newStr.'+');
17         listarr($str, $newStr.'-');
18         listarr($str, $newStr);
19 }
20 function cal($str)
21 {
22     $arr = explode('+', $str);//分割数列，储存至数组中
23     $sum = 0;
24     foreach($arr as　$v){
25         if(is_numeric($v)){   //判断分割的数组是否为纯数字；
26             $sum += $v;
27         } else {
28             $vArr = explode('-', $v); //对含减号的数组再进行一次分割；
29             $sum += $vArr[0];   //第一个值前的运算符为+；
30             unset($vArr[0]);
31             $s = array_sum($vArr);
32             $sum -= $s;
33         }
34     }
35     if($sum == 100){
36         return true;
37     } else {
38         return false;
39     }
40 }
41 listarr($str, $newStr);

最后补充一个通用模板

 1 /**
 2  * $data array 要计算的数列组合；
 3  * $flag array 可用的运算符号
 4  * $result int 要求的和的值
 5  */
 6 function think_exp($data, $flag, $result)
 7 {
 8     $m = count($data);//m个数字
 9     $n = count($flag);//n个符号
10     $num =  str_split( sprintf ( "%0". ($m - 1) ."d",0) ); //生成一个[0,0,0,0,...,0]的数组
11     $exp = '';
12     while($num != 'Ok' ){
13         $line = '';
14         for ( $i=0; $i<$m; $i++  )  {
15             $line .= $data[$i]; //列出所有的式子；
16             if( isset($num[$i]) ) $line .= $flag[$num[$i]];
17         }
18         if ( eval('return '.$line.';') == $result) {
19             $exp .= $line.'='.$result.'<br />';
20         }
21         $num =  getNext($num , 0, $n);
22     }
23     return $exp;
24 }
25 function getNext($next_num , $position = 0, $n){
26     if ($position == count($next_num)) return 'Ok';
27     $next_num[$position] = $next_num[$position] + 1;
28     if ($next_num[$position] < $n) {
29         return $next_num;
30     } else {
31         $next_num[$position] = 0;
32         return getNext($next_num, $position + 1, $n);
33     }
34 }


//计算题目
echo "<font color=red>think_exp(array(1,2,3,4,5,6,7,8,9), array('','+','-','*','/'), 100); </font><br />";
echo think_exp(array(1,2,3,4,5,6,7,8,9), array('','+','-'), 100);
转自Kit_G的博客