Heim > Backend-Entwicklung > PHP-Tutorial > PHP 如何递归算法?

PHP 如何递归算法?

WBOY
Freigeben: 2016-06-06 20:29:37
Original
1089 Leute haben es durchsucht

题目

<code>有一个数组,由30个1~999键值组成,和为 12865,请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865</code>
Nach dem Login kopieren
Nach dem Login kopieren

回答

如何把以下代码简化,因为 $i ~ $iN 是不确定的。如果有其他算法更好

<code>
function loopDeep($sum , $count, $min, $max)
{
    for ($i = $min; $i </code>
Nach dem Login kopieren
Nach dem Login kopieren

2015-8-23 一种算法,查看分布。(by CSDN某大牛)

<code class="php">
$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;
}
</code>
Nach dem Login kopieren
Nach dem Login kopieren
<code class="html">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
)
</code>
Nach dem Login kopieren
Nach dem Login kopieren

回复内容:

题目

<code>有一个数组,由30个1~999键值组成,和为 12865,请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865</code>
Nach dem Login kopieren
Nach dem Login kopieren

回答

如何把以下代码简化,因为 $i ~ $iN 是不确定的。如果有其他算法更好

<code>
function loopDeep($sum , $count, $min, $max)
{
    for ($i = $min; $i </code>
Nach dem Login kopieren
Nach dem Login kopieren

2015-8-23 一种算法,查看分布。(by CSDN某大牛)

<code class="php">
$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;
}
</code>
Nach dem Login kopieren
Nach dem Login kopieren
<code class="html">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
)
</code>
Nach dem Login kopieren
Nach dem Login kopieren

正准备睡觉,瞬间有了思路。。。
先来个js版本的---我是前端(:

<code>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;$i</code>
Nach dem Login kopieren

php:

<code>
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</code>
Nach dem Login kopieren

刚刚用node跑了一下,没跑完(复杂度太大),也不知道对不对,谁跑完结果告诉我一下(:
可以睡觉去了。。。

PHP 如何递归算法?

用测试数据0,1,2,3跑了一下
[0,1,2,3]取3个数字,和为6;

<code>addFn(0,3,0,6,3,0,[])</code>
Nach dem Login kopieren

PHP 如何递归算法?

dp方案

dp, 只用一维数组节省内存, 但是题目复杂度太大... 不玩了.

<code>public Set<list>> compute(int N, int SUM, int MAX_KEY) {
    Set<list>>[] pre = null;
    Set<list>>[] 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<integer> l: pre[j - k]) {
                        List<integer> 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);
}
</integer></integer></list></list></list></code>
Nach dem Login kopieren

dp方案2

二维数组, 太费内存

<code>private Set<list>>[][] dp = null;
private Set<list>> res = null;

public Set<list>> 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<integer> l: dp[i - 1][j - k]) {
                        List<integer> tmp = new ArrayList(l);
                        tmp.add(k);
                        dp[i][j].add(tmp);
                    }
                }
    return dp[N][SUM];
}
</integer></integer></list></list></list></code>
Nach dem Login kopieren

递归方案

Java代码. 用了一些优化提高效率, 但复杂度还是太高. 权当参考吧.

<code>private Set<long> failedSet = null;
private Set<list>> res = null;

public Set<list>> 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 </list></list></long></code>
Nach dem Login kopieren

题目意思比较含糊,没说要所有结果还是只要一组还是搜索特定结果;
只要一组,数字可以重复的话,29个1加一个12836就可以了;
只要一组数字,数字要求不重复,随机生成29个,sum超过12865和重复数字的回退,最后一个用12865减掉前面29个值;
如果搜索给定的数组的话,直接DFS吧;
如果是求出所有可能结果,那就BFS吧。

Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage