PHP 如何递归算法？
程序员文章站
2022-05-29 15:58:18
...
题目
有一个数组，由30个1~999键值组成，和为 12865，请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865回答
如何把以下代码简化，因为 $i ~ $iN 是不确定的。如果有其他算法更好
function loopDeep($sum , $count, $min, $max)
{
for ($i = $min; $i 2015-8-23 一种算法，查看分布。（by CSDN某大牛）
$r = foo(12865, 30);
echo array_sum($r), PHP_EOL; //验证总和
print_r(array_count_values($r)); //查看分布
function foo($num, $k, $min = 1, $max = 999)
{
$res = array_fill(0, $k, 1);
do {
for ($i = 0; $i $max) $t = $max - $res[$i];
if ($sum + $t > $num) $t = $num - $sum;
$res[$i] += $t;
}
} while ($num > $sum);
return $res;
}
12865
Array
(
[222] => 2
[589] => 1
[127] => 1
[538] => 1
[268] => 1
[444] => 1
[922] => 1
[537] => 1
[211] => 1
[17] => 1
[848] => 1
[800] => 1
[893] => 1
[274] => 1
[499] => 1
[45] => 1
[660] => 1
[686] => 1
[968] => 1
[491] => 1
[355] => 1
[849] => 1
[857] => 1
[322] => 1
[217] => 1
[1] => 4
)
回复内容：
题目
有一个数组，由30个1~999键值组成，和为 12865，请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865回答
如何把以下代码简化，因为 $i ~ $iN 是不确定的。如果有其他算法更好
function loopDeep($sum , $count, $min, $max)
{
for ($i = $min; $i 2015-8-23 一种算法，查看分布。（by CSDN某大牛）
$r = foo(12865, 30);
echo array_sum($r), PHP_EOL; //验证总和
print_r(array_count_values($r)); //查看分布
function foo($num, $k, $min = 1, $max = 999)
{
$res = array_fill(0, $k, 1);
do {
for ($i = 0; $i $max) $t = $max - $res[$i];
if ($sum + $t > $num) $t = $num - $sum;
$res[$i] += $t;
}
} while ($num > $sum);
return $res;
}
12865
Array
(
[222] => 2
[589] => 1
[127] => 1
[538] => 1
[268] => 1
[444] => 1
[922] => 1
[537] => 1
[211] => 1
[17] => 1
[848] => 1
[800] => 1
[893] => 1
[274] => 1
[499] => 1
[45] => 1
[660] => 1
[686] => 1
[968] => 1
[491] => 1
[355] => 1
[849] => 1
[857] => 1
[322] => 1
[217] => 1
[1] => 4
)
正准备睡觉，瞬间有了思路。。。
先来个js版本的---我是前端（：
function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
if($loop_index==$loop_num){
if($sum==$sum_end){
console.log('///$sum:'+$sum+'/$sum_end:'+$sum_end+'/$indexArr:'+$indexArr+'/$loop_index:'+$loop_index);
}
return false;
}else{
for(var $ii=$i;$ii($max-$loop_num+1+$loop_index)){
break;
}
$sum=eval($indexArr.join("+"));
console.log('$sum:'+$sum+'/$sum_end:'+$sum_end+'/$loop_index:'+$loop_index+'/$ii:'+$ii+'/$indexArr:'+$indexArr);
forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
}
}
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
for(var $i=$min;$iphp：
function forFn($i,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
if($loop_index==$loop_num){
if($sum==$sum_end){
echo('///$sum:'.$sum.'/$sum_end:'.$sum_end.'/$indexArr:'.$indexArr);
print_r($indexArr);
};
return false;
}else{
for($ii=$i;$ii($max-$loop_num+1+$loop_index)){
break;
}
$sum=array_sum($indexArr);
forFn($ii+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr);
}
}
};
function addFn($min,$max,$sum,$sum_end,$loop_num,$loop_index,$indexArr){
for($i=$min;$i刚刚用node跑了一下，没跑完（复杂度太大），也不知道对不对，谁跑完结果告诉我一下（：
可以睡觉去了。。。
用测试数据0，1，2，3跑了一下
[0,1,2,3]取3个数字，和为6；
addFn(0,3,0,6,3,0,[])
dp方案
dp, 只用一维数组节省内存, 但是题目复杂度太大... 不玩了.
public Set> compute(int N, int SUM, int MAX_KEY) {
Set>[] pre = null;
Set>[] cur = new Set[SUM + 1];
// one elem
for (int i = 0; i ();
cur[i].add(Collections.singletonList(i));
}
for (int i = 2; i = 0 && pre[j - k] != null) {
if (cur[j] == null)
cur[j] = new HashSet();
for (List l: pre[j - k]) {
List tmp = new ArrayList(l);
tmp.add(k);
Collections.sort(tmp);
cur[j].add(tmp);
}
}
}
return cur[SUM];
}
@Test
public void test(){
compute(30, 12865, 999);
}
dp方案2
二维数组, 太费内存
private Set>[][] dp = null;
private Set> res = null;
public Set> compute(int N, int SUM, int MAX_KEY) {
dp = new Set[N + 1][SUM + 1];
for (int i = 0; i ();
dp[1][i].add(Collections.singletonList(i));
}
for (int i = 2; i = 0 && dp[i - 1][j - k] != null) {
if (dp[i][j] == null)
dp[i][j] = new HashSet();
for (List l: dp[i - 1][j - k]) {
List tmp = new ArrayList(l);
tmp.add(k);
dp[i][j].add(tmp);
}
}
return dp[N][SUM];
}
递归方案
Java代码. 用了一些优化提高效率, 但复杂度还是太高. 权当参考吧.
private Set failedSet = null;
private Set> res = null;
public Set> compute() {
failedSet = new HashSet();
res = new HashSet();
computeInt(30, 12865, 999, new int[30]);
return res;
}
private boolean computeInt(int count, int sum, int max, int[] arr) {
if (count == 0 || sum tmp = Arrays.stream(arr).sorted().boxed()
.collect(Collectors.toList());
res.add(tmp);
}
return sum == 0;
}
long key = (long)count * Integer.MAX_VALUE + sum;
if (failedSet.contains(key))
return false;
boolean found = false;
for (int i = 0; i
题目意思比较含糊，没说要所有结果还是只要一组还是搜索特定结果；
只要一组，数字可以重复的话，29个1加一个12836就可以了；
只要一组数字，数字要求不重复，随机生成29个，sum超过12865和重复数字的回退，最后一个用12865减掉前面29个值；
如果搜索给定的数组的话，直接DFS吧；
如果是求出所有可能结果，那就BFS吧。