php分治法

任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。 分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 如果原问题可分割成k个子问题(1<k≤n),且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。 分治法所能解决的问题一般具有以下几个特征: (1)该问题的规模缩小到一定的程度就可以容易地解决; (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出的子问题的解可以合并为该问题的解; (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。 分治法在每一层递归上都有三个步骤: (1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题; (2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题; (3)合并:将各个子问题的解合并为原问题的解。 php代码示例: $b ? $a : $b; } function getMax( $ary, $l, $u ) { if ( $u === $l ) { return $ary[$u]; } else { return mymax( getMax( $ary, $l, intval( ( $u + $l ) / 2 ) ), getMax( $ary, intval( ( $u + $l ) / 2 ) + 1, $u ) ); } } $ary = array(1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17); echo getMax( $ary, 0, count( $ary ) - 1 ); ?> 原文 http://home.51.com/chenjiuchuan/diary/item/10049599.html

php 贪婪算法

贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。 例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。 【问题】 装箱问题 问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。 若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下: { 输入箱子的容积; 输入物品种数n; 按体积从大到小顺序,输入各物品的体积; 预置已用箱子链为空; 预置已用箱子计数器box_count为0; for (i=0;i<n;i++) { 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j; if (已用箱子都不能再放物品i) { 另用一个箱子,并将物品i放入该箱子; box_count++; } else 将物品i放入箱子j; } } 上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。 若每只箱子所装物品用链表来表示,链表首结点指针存于一个结构中,结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。 } 附php示例:

php递归无限级分类

<?php
/**
 * 递归无限级分类【先序遍历算】,获取任意节点下所有子孩子
 * @param array $arrCate 待排序的数组
 * @param int $parent_id 父级节点
 * @param int $level 层级数
 * @return array $arrTree 排序后的数组
 */
function getMenuTree($arrCat, $parent_id = 0, $level = 0)
{
    static  $arrTree = array(); //使用static代替global
    ifempty($arrCat)) return FALSE;
    $level++;
    foreach($arrCat as $key => $value)
    {
        if($value['parent_id' ] == $parent_id)
        {
            $value[ 'level'] = $level;
            $arrTree[] = $value;
            unset($arrCat[$key]); //注销当前节点数据,减少已无用的遍历
            getMenuTree($arrCat, $value[ 'id'], $level);
        }
    }
    return $arrTree;
}
/**
 * 测试数据
 */
$arrCate = array(  //待排序数组
  array( 'id'=>1, 'name' =>'顶级栏目一', 'parent_id'=>0),
  array( 'id'=>2, 'name' =>'顶级栏目二', 'parent_id'=>0),
  array( 'id'=>3, 'name' =>'栏目三', 'parent_id'=>1),
  array( 'id'=>4, 'name' =>'栏目四', 'parent_id'=>3),
  array( 'id'=>5, 'name' =>'栏目五', 'parent_id'=>4),
  array( 'id'=>6, 'name' =>'栏目六', 'parent_id'=>2),
  array( 'id'=>7, 'name' =>'栏目七', 'parent_id'=>6),
  array( 'id'=>8, 'name' =>'栏目八', 'parent_id'=>6),
  array( 'id'=>9, 'name' =>'栏目九', 'parent_id'=>7),
);
header('Content-type:text/html; charset=utf-8'); //设置utf-8编码
echo '<pre>';
print_r(getMenuTree($arrCate, 0, 0));
echo '</pre>';
?>

PHP快速排序算法

[php] <?php function quickSort($arr){ $len = count($arr); if($len <= 1) { return $arr; } $key = $arr[0]; $left_arr = array(); $right_arr = array(); for($i=1; $i<$len; $i++){ if($arr[$i] <= $key){ $left_arr[] = $arr[$i]; } else{ $right_arr[] = $arr[$i]; } } $left_arr = quickSort($left_arr); $right_arr = quickSort($right_arr); return array_merge($left_arr, array($key), $right_arr); } $arr = array(49,38,65,97,103,76,13,27); print_r(quickSort($arr)); //输出:Array( [0] => 13 [1] => 27 [2] => 38 [3] => 49 [4] => 65 [5] => 76 [6] => 97) ?> [/php]

进制转换算法 2转10 10转2

十进制与二进制转换之相互算法 十进制转二进制: 用2辗转相除至结果为1 将余数和最后的1从下向上倒序写 就是结果 例如192 192%2=0; 96%2=0 48%2=0 24%2=0 12%2=0 6%2=0 3%2=1 1%2=1 192的进制 11000000 二进制转十进制 从最后一位开始算,依次列为第0、1、2...位 第n位的数(0或1)乘以2的n次方 得到的结果相加就是答案 例如:01101011.转十进制: 第0位:1乘2的0次方=1 忽略前面6个0   从第7位开始1*2 的7次方    1*2 的8次方 结果相加64+128=192