PHP如何递归算法？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP如何递归算法？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4668字，纯文字阅读大概需要7分钟。

内容图文

题目

有一个数组，由30个1~999键值组成，和为 12865，请写出计算此数组的 30 个值的方法
$arr[1]+$arr[2]+....+$arr[30]=12865

回答

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


function loopDeep($sum , $count, $min, $max)
{
    for ($i = $min; $i < $max; $i++) {
        for ($i2 = $min; $i2 < $max; $i2++) {
            for ($i3 = $min; $i3 < $max; $i3++) {
                for ($i4 = $min; $i4 < $max; $i4++) {
                    if ($i + $i2 + $i3 + $i4 == $sum) {
                        return [$i, $i2, $i3];
                    }
                }
            }
        }
    }
    
    return [];
}

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 < $k; $i++) {
            $sum = array_sum($res);
            $t = rand(0, $max - $min);
            if ($res[$i] + $t > $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 < $max; $i++) {
        for ($i2 = $min; $i2 < $max; $i2++) {
            for ($i3 = $min; $i3 < $max; $i3++) {
                for ($i4 = $min; $i4 < $max; $i4++) {
                    if ($i + $i2 + $i3 + $i4 == $sum) {
                        return [$i, $i2, $i3];
                    }
                }
            }
        }
    }
    
    return [];
}

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 < $k; $i++) {
            $sum = array_sum($res);
            $t = rand(0, $max - $min);
            if ($res[$i] + $t > $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;$ii++){
            $indexArr[$loop_index]=$ii;
            if($indexArr[$loop_index]>($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<=$max-$loop_num+1;$i++){
        var $loop_index=0;
        $indexArr[$loop_index]=$i;
        forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
    }
}

addFn(0,999,0,12865,30,0,[])

php：


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;$ii++){
            $indexArr[$loop_index]=$ii;
            if($indexArr[$loop_index]>($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<($max-$loop_num+1);$i++){
        $loop_index=0;
        $indexArr[$loop_index]=$i;
        forFn($i+1,$max,$sum,$sum_end,$loop_num,$loop_index+1,$indexArr)
    }
}

addFn(0,999,0,12865,30,0,[])

刚刚用node跑了一下，没跑完（复杂度太大），也不知道对不对，谁跑完结果告诉我一下（：
可以睡觉去了。。。

PHP如何递归算法？ - 文章图片

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

addFn(0,3,0,6,3,0,[])

PHP如何递归算法？ - 文章图片

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 <= MAX_KEY; i++) {
        cur[i] = new HashSet<>();
        cur[i].add(Collections.singletonList(i));
    }
    
    for (int i = 2; i <= N; i++) {
        pre = cur;
        cur = new Set[SUM + 1];
        for (int j = 0; j <= SUM; j++)
            for (int k = 0; k <= MAX_KEY; k++)
                if (j - k >= 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 <= MAX_KEY; i++) {
        dp[1][i] = new HashSet<>();
        dp[1][i].add(Collections.singletonList(i));
    }
    for (int i = 2; i <= N; i++)
        for (int j = 0; j <= SUM; j++)
            for (int k = 0; k <= MAX_KEY; k++)
                if (j - k >= 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 < 0) {
        if (sum == 0){
            List 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 <= max; i++) {
        arr[count - 1] = i;
        if (computeInt(count - 1, sum - i, Math.min(max, i), arr))
            found = true;
    }
    if (!found)
        failedSet.add(key);
    return found;
}

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

内容总结

以上是互联网集市为您收集整理的PHP如何递归算法？全部内容，希望文章能够帮你解决PHP如何递归算法？所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/238952.html

来源：【匿名】

【上一篇】问答网站需要用到哪些算法？【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【PHP如何递归算法？】教程文章相关的互联网学习教程文章

JAVA递归算法

1、什么是递归算法递归算法就是直接或间接调用自己的算法2、递归思想递归就是方法里调用自身在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。要点： ...

递归算法设计的基本思想是：对于一个复杂的问题，把原问题分解为若干个相对简单类同的子问题，继续下去直到子问题简单到能够直接求解，也就是说到了递推的出口，这样原问题就有递推得解。关键要抓住的是：（1）递归出口（2）地推逐步向出口逼近例子: example：求5的阶乘。。如下： Java代码 public class Test { static int multiply(int n){ if(n==1||n==0) return n; else...

Java简单递归算法(两种例子)【代码】

例子一: 程序结束口:表达式(n==-1)为true,代表n(100)被递减完了,已经不能被递减了, 如不是-1,则代表还有数值可以被递减,此题及计算结果为偶数总和,递减时应当判断当前n是否为偶数如果是偶数,则 sum(偶数总和) = n(当前数值)+ 调用此方法(n(当前数值)-1(每次递减1)) 如果不是偶数,则不需要添加到sum 里面,直接再次调用自己本身方法,n-1,进入下一轮/*** 计算1-100以内偶数的总和* n为要计算的数值(100)* sum为总和*/ public static...

递归算法实例【代码】【图】

在数学与计算机科学中，递归是指在函数的定义中使用函数自身的方法。　　递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所...

递归算法，递归复制目录【代码】

import os import shutil # todo python 递归算法def copy(src,dest):files=os.listdir(src)os.mkdir(dest)for file in files:src_file_path= os.path.join(src,file)dest_file_path=os.path.join(dest,file)if os.path.isfile(src_file_path):with open(src_file_path,"rb")as rs:reader_stream=rs.read()with open(dest_file_path,"wb")as ws:ws.write(reader_stream)else:# is dircopy(src_file_path,dest_file_path) 方法2：使...

python的递归算法学习（2）：具体实现：斐波那契和其中的陷阱【代码】【图】

1.斐波那契什么是斐波那契，斐波那契额就是一个序列的整数的排序，其定义如下；Fn = Fn-1 + Fn-2 with F0 = 0 and F1 = 1 也就是，0，1，1，2，3，5，8，13.。。。。递归实现：def fib(n):if n == 0:return 0elif n == 1:return 1else:return fib(n-1) + fib(n-2)非递归实现：def fibi(n):a, b = 0, 1for i in range(n):a, b = b, a + breturn a在这里，我们如果仔细调试，会发现，递归实现，会消耗更多的时间，这里测试如下：fr...

2的次幂表示 ----递归算法

问题描述　　任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0现在约定幂次用括号来表示，即a^b表示为a（b）此时，137可表示为：2（7）+2（3）+2（0）进一步：7=2^2+2+2^0 （2^1用2表示）3=2+2^0 所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）又如：1315=2^10+2^8+2^5+2+1所以1315最后可表示为...

一个小递归算法【代码】

public static void main(String[] args) {System.out.println("打印小于50的数，逆序");printOne(2);}public static void printOne(int n) {//System.out.println(n);if (n < 50)printOne(2 * n);else {//System.out.println(n);printTwo(n / 2);}}public static void printTwo(int n) {if (n >= 2) {System.out.println(n);printTwo(n / 2);}}说明：一个整数，大于0，不用循环和本地变量，按照n，2n，4n，8n的顺序递增，当值大于...

递归算法——农夫养牛之动归【代码】

1/** 2 * Created by Administrator on 14-5-15.3*/ 4publicclass NewCow_DP {5publicstaticvoid main(String[] args){6int[] cows=newint[31];7 cows[1]=1;8 cows[2]=1;9 cows[3]=2; 10for(int i=4;i<=30;i++){ 11 cows[i]=cows[i-1]+cows[i-3]; 12 } 13for(int i=1;i<=30;i++) 14 System.out.println(i+"年后有牛："+cows[i]); 15 } 16 } 原文：http://www.cnblogs.c...

递归算法【图】

所谓递归——函数的递归调用。c语言的这种特性给程序设计带来许多方便。尤其是接触数据结构时，会发现递归的出现频率非常之高，也行之有效~下面是笔者在接触递归这个东西时的一些个人总结和体会：　　1.直接或间接地调用函数本身。我们在程序设计时，往往要自己写一些函数来帮助整个解决方案的完成，有时一个函数中又要调用自身来帮助这个功能的实现。是不是被套话弄晕了？Don‘t worry~开个玩笑了。　　　　2.一个简单的例子可以帮...

C/C++ 使用递归算法实现汉诺塔

汉诺塔原理解析：当只有一个盘子的时候，只需要从将A塔上的一个盘子移到C塔上。当A塔上有两个盘子是，先将A塔上的1号盘子（编号从上到下）移动到B塔上，再将A塔上的2号盘子移动的C塔上，最后将B塔上的小盘子移动到C塔上。当A塔上有3个盘子时，先将A塔上编号1至2的盘子（共2个）移动到B塔上（需借助C塔），然后将A塔上的3号最大的盘子移动到C塔，最后将B塔上的两个盘子借助A塔移动到C塔上。 ...

贪心算法，递归算法，动态规划算法比较与总结【图】

一般实际生活中我们遇到的算法分为四类：一>判定性问题二>最优化问题三>构造性问题四>计算性问题而今天所要总结的算法就是着重解决最优化问题《算法之道》对三种算法进行了归纳总结，如下表所示：标准分治动态规划贪心算法适用类型通用问题优化问题优化问题子问题结构每个子问题不同很多子问题重复（不独立）只有一个子问题最优子结构不需要必须满足必须满足子问题数全部子问题都要...

递归算法详细分解例子【代码】

//例子 function demo($n){　　if($n>1)　　{ 　　　　$n=$n*demo($n-1); 　　}　　else　　{ 　　　　return 1; 　　} 　　return $n;}echo demo(10); 解答：递归其实就是“一个函数的自调用”在这个“自调用”的过程中，必须要有一个变化的“参数”，当这个“参数”达到你的期望值的时候，终止该“自调用”过程拿楼主的程序来说demo($n)内部又有调用demo($n-1)，构成了“自调用”且，$n又有一个“期望值”，即是$n>1，不满足此...

快排的非递归算法和最大子串乘积【代码】

快排的原理是，让一个数作为中间值A，使得左边的数都小于(大于)等于A，右边的数都大于(小于)A。 1publicstaticvoid quickSort(Integer[] arrayList,int begin,int end){ 2if(begin>=end) 3return; 4int par=paration3(arrayList, begin, end); 5if(begin<par-1) 6 quickSort(arrayList, begin, par-1); 7if (par<end) 8 quickSort(arrayList, par+1, end); 9 }publicstaticint paration(Inte...

PHP基于非递归算法实现先序、中序及后序遍历二叉树操作的示例【图】

这篇文章主要介绍了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作,结合实例形式分析了php采用非递归算法对二叉树进行先序、中序及后序遍历操作的原理与具体实现技巧,需要的朋友可以参考下本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考，具体如下：概述：二叉树遍历原理如下：针对上图所示二叉树遍历：1. 前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。ABDHECFG2....

递归算法 - 相关标签

递归算法

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / PHP如何递归算法？

PHP如何递归算法？

内容导读

内容图文

题目

回答

回复内容：

题目

回答

dp方案

dp方案2

递归方案

内容总结

内容备注

内容手机端

【PHP如何递归算法？】教程文章相关的互联网学习教程文章

JAVA递归算法

递归算法(转)

Java简单递归算法(两种例子)【代码】

递归算法实例【代码】【图】

递归算法，递归复制目录【代码】

python的递归算法学习（2）：具体实现：斐波那契和其中的陷阱【代码】【图】

2的次幂表示 ----递归算法

一个小递归算法【代码】

递归算法——农夫养牛之动归【代码】

递归算法【图】

C/C++ 使用递归算法实现汉诺塔

贪心算法，递归算法，动态规划算法比较与总结【图】

递归算法详细分解例子【代码】

快排的非递归算法和最大子串乘积【代码】

PHP基于非递归算法实现先序、中序及后序遍历二叉树操作的示例【图】

递归算法 - 相关标签

PHP - 相关标签

算法 - 最新教程

算法 - 最热教程