现在的位置: 首页 > 综合 > 正文

PHP 输入两个整数n 和m,从数列1,2,3…….n 中随意取几个数, 使其和等于m ,要求将其中所有的可能组合列出来

2012年08月27日 ⁄ 综合 ⁄ 共 703字 ⁄ 字号 评论关闭
 1 <?php
 2     #输入sum和n,要求输出1,2...n里所有和为sum的组合
 3     #这是一个可划分子问题问题
 4     #若用f(sum, n)表示问题的界,则元素组合共有两种情况
 5     #1. 和为sum的组合里包括n,则f(sum, n) = f(sum - n, n - 1)
 6     #2. 和为sum的组合里不包括n,则 f(sum, n) = f(sum, n - 1)
 7     #所以 f(sum, n) = f(sum - n, n - 1) U f(sum, n - 1)
 8 
 9     function combination($sum, $n, $comb) {
10         if ($n < 0 || $sum < 0) {
11             #当n < 0或者sum < 0都是不符合条件的结果
12             // print_r($comb);
13             // echo "sum: {$sum} n: {$n}<br>";
14             return;
15         }
16 
17         if ($sum < $n) {
18             combination($sum, $sum, $comb); #sum < n,则不可能需要比sum大的数来构成组合
19             return;
20         }
21         
22         #结果求得
23         if ($sum == 0) {
24             #输出元素组合
25             echo "Combination: ";
26             foreach ($comb as $val) {
27                 echo $val . " ";
28             }
29             echo "<br>";
30             return;
31         }
32 
33         #组合里包含n的情况
34         $comb[] = $n;
35         combination($sum - $n, $n - 1, $comb);
36 
37         #组合里不包含n的情况
38         array_pop($comb);
39         combination($sum, $n - 1, $comb);
40     }
41 
42     combination(10, 15, array());
43 ?>

抱歉!评论已关闭.