php基础算法

PHP基础算法
这里是用 PHP 写的几个基础算法，算法的重要性貌 似对于 PHP 程序员不怎么重
要，其实是非常重要的，经典名句：算法+数据结构=程序。作为一名真正的高级PHP
程序员，我认为应该熟悉 C，如果你想成为真正的程序员，请好好学 C，学好数据结
构与算法。这里仅仅只是几个基础算法，还有很多东东要学……
1、首先来画个菱形玩玩，很多人学 C 时在书上都画过，咱们用 PHP 画下，画
了一半。
思 路：多少行for 一次，然后在里面空格和星号 for 一次。
代码片段
for($i=0;$i for($j=0;$j echo ' ';
}
for($k=0;$k echo '*';
}
echo '
';
}
2、冒泡排序，C里基础算法，从小到大对一组数排序。
思路：这题从小到大，第一轮排最小，第二轮 排第二小，第三轮排第三小，依次
类推……
代码片段
$arr = array(3, 2, 1);
$n = count($arr);
//每循环一次，就跑一趟后面的排序
for($j=0; $j // 对后面没排好的，循环查找出最大（最小）的，进行一趟排序
for($i=$j; $i if($arr[$j] > $arr[$i+1]) {
$t = $arr[$j];
$arr[$j] = $arr[$i+1];
$arr[$i+1] = $t;
}
}
}
print_r($arr);
3、杨辉三角，用 PHP写。
思路：每一行的第一位和最后一位是 1，没有变化，中间是前排一位与左边一排
的和，这种算法是用一个二维数组保存，另外有种算法用一维数组也可以实现，一行
一行的输出，有兴趣去 写着玩下。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
代 码片段
//每行的第一个和最后一个都为 1，写了 6 行
for($i=0; $i $a[$i][0]=1;
$a[$i][$i]=1;
}
// 出除了第一位和最后一位的值，保存在数组中
for($i=2; $i for($j=1; $j $a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
}
}
// 打印
for($i=0; $i for($j=0; $j echo $a[$i][$j].' ';
}
echo '
';
}
4、在一组数中，要求插入一个数，按其原来顺序插入，维护原来排序方式。
思路：找到比要插 入数大的那个位置，替换，然后把后面的数后移一位。
代码片段
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//如果要插入的数已经最大，直接打印
if($arr[$n-1] $arr[$n+1] = $in; print_r($arr);}
for($i=0; $i //找出要插入的位置
if($arr[$i] >= $in){
$t1= $arr[$i];
$arr[$i] = $in;
//把后面的数据后移一位
for($j=$i+1; $j $t2 = $arr[$j];
$arr[$j] = $t1;
$t1 = $t2;
}
// 打印
print_r($arr);
die;
}
}
5、对一组数进行排序（快速排序算法） 。
思路：通过一趟排序分成 两部分，然后递归对这两部分排序，最后合并。
代码片段
function q($array) {
if (count($array) //以$key为界，分成两个子数组
$key = $array[0];
$l = array();
$r = array();
//分别进行递归排序，然后合成一个数组
for ($i=1; $i if ($array[$i] else { $r[] = $array[$i]; }
}
$l = q($l);
$r = q($r);
return array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
print_r( q($arr) );
6、在一个数组查找你所需元素（二分查找算法）。
思路：以数组中某个值为 界，再递归进行查找，直到结束。
代码片段
function find($array, $low, $high, $k){
if ($low $mid = intval(($low+$high)/2);
if ($array[$mid] == $k){
return $mid;
}elseif ($k return find($array, $low, $mid-1, $k);
}else{
return find($array, $mid+1, $high, $k);
}
}
die('Not have...');
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,
7、合并多个数组，不用array_merge()，题目来于论坛。
思路：遍历每个数组， 重新组成一个新数组。
代码片段
function t(){
$c = func_num_args()-1;
$a = func_get_args();
//print_r($a);
for($i=0; $i if(is_array($a[$i])){
for($j=0; $j $r[] = $a[$i][$j];
}
} else {
die('Not a array!');
}
}
return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4)));
echo '
';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
8、牛年求牛：有一母牛，到 4 岁可生育，每年一头，所生均是一样的母牛，到
15岁绝育，不再能生，20岁 死亡，问n年后有多少头牛。（来自论坛）代码片段
function t($n) {
static $num = 1
for($j=1; $j if($j>=4 && $j if($j==20){$num--;}
}
return $num;
}
//test
echo t(8);