【四脚猫】每日一题(4月9日) :从m个数中选出n个数来 ( 0 < n <= m) ,要求n个数之间不能有重复,其和等于一个定值k。求一段程序,罗列所有的可能。 例如备选的数字是:11, 18, 12, 1, -2, 20, 8, 10, 7, 6 。 和k等于:18 那么组合的可能有:
1 2 3 4 5 6 7 8 9 10 | [18] [8,10] [-2,20] [12,6] [11,7] [11,1,6] [1,10,7] [12,-2,8] [12,1,-2,7] [11,1,-2,8] |
AN的解法很巧妙,采用二进制按位乘后加和,这个很有创意!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
风兮蜻蜒和刘文千采用递归的方式找子集,这个代码大家赶紧收藏啊,以后还能用得到啊!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | <?php /** * 组合枚举 */ function c($arr, $n, &$res, $pre = array()) { if ($n == 0) { $res[] = $pre; } else { $count = count($arr); for ($i = 0; $i < $count - $n + 1; $i++) { $temp = array_shift($arr); c($arr, $n - 1, $res, array_merge($pre, array( $temp ))); } } } // 处理数组 $arr = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6, 12, 6, 6, 6, -6 ); $sum = 18; // 条件和值 $count = count($arr); // 从C(18,1) 循环到 C(18,18) for ($i = 1; $i <= $count; $i++) { $res = array(); c($arr, $i, $res); foreach ($res as $val) { if (array_sum($val) == $sum) { echo implode(' + ', $val), ' = ', $sum, PHP_EOL; } } } |
Diven精益求精,完成后第二天又提交了超过32位的解法,厉害!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | <?php function sum_eq_constant($arr, $constant) { if (empty($arr) || !is_array($arr) || !is_numeric($constant))return false; sort($arr); $m = count($arr); $max = pow(2, $m); //有2的m次方种可能 (包括全部为零) $step = 0; $result = array(); while ($step < $max) { $zero_one_arr = array(); //定义一个0,1数组 $tmp = array( $step ); for ($i = 0; $i < $m; $i++) { //用辗转相除法 把十进制 转成二进制 $zero_one_arr[$i] = $tmp[$i] % 2; $tmp[$i + 1] = floor($tmp[$i] / 2); } $multi = array(); foreach ($zero_one_arr as $k => $v) { $multi[] = $v * $arr[$k]; } if (array_sum($multi) == $constant) { $result[] = array_diff($multi, array( 0, '0' )); } $step++; } return $result; } $arr = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6 ); $constant = 18; print_r(sum_eq_constant($arr, $constant)); |
云无心 的substr和array_diff_key已经用到出神入化了,解法很优美!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <?php function getCombine($arr, $n) { $len = count($arr); $total = pow(2, $len); $ret = array(); for ($i = 1; $i < $total; $i++) { $str = substr(str_repeat("0", $len) . decbin($i), -$len); $tmparr = array_diff_key($arr, array_diff(str_split($str), array( '1' ))); if (array_sum($tmparr) == $n) { $ret[] = implode($tmparr, ','); } } return array_unique($ret); } $data = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6 ); $n = 18; print_r(getCombine($data, $n)); |
青菜虫的堆栈思想很独特,目前逻辑还有遗漏,看能否完善下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | <?php header('Content-Type: text/html; charset=utf-8'); $arr = array(11, 18, 12, 1, -2, 20, 8, 10, 7, 6); echo ' '; print_r($arr); print_r(test($arr, 18)); echo ''; function test($arr, $k) { sort($arr); $m = count($arr); $sum = 0; $result = array(); $paths = array(); for ($i=0; $i<$m; $i++) { $tmp = $pointer = array(); $tmp[] = $arr[$i]; $pointer[] = $i; for ($j=$i+1; $j<$m; $j++) { $sum = array_sum($tmp) + $arr[$j]; $path = implode('-', $pointer); if (isset($paths[$path])) continue; if ($sum >= $k) { if ($sum == $k) { $result[] = array_merge($tmp, array($arr[$j])); } array_pop($tmp); $j = array_pop($pointer); $paths[$path] = 1; } elseif ($sum < $k) { array_push($tmp, $arr[$j]); array_push($pointer, $j); } } } return $result; } // END OF FILE |
欢迎各位攻城狮,各位大牛给每日一题投稿,大家可以把自己碰到的有趣问题,工作中碰到的难题等…发送到 稿件邮箱:2313427189@qq.com