PHP写的几个基础算法 (转载)-阿里云开发者社区

开发者社区> 数字技术前瞻> 正文
登录阅读全文

PHP写的几个基础算法 (转载)

简介:

 

这里是用PHP写的几个基础算法,算法的重要性貌似对于PHP程序员不怎么重要,其实是非常重要的,经典名句:算法+数据结构=程序。作为一名真正的高级PHP程序员,我认为应该熟悉C,如果你想成为真正的程序员,请好好学C,学好数据结构与算法。这里仅仅只是几个基础算法,还有很多东东要学……

1、首先来画个菱形玩玩,很多人学C时在书上都画过,咱们用PHP画下,画了一半。

思路:多少行for一次,然后在里面空格和星号for一次。

<?php
for($i=0;$i<=3;$i++){
    for($j=0;$j<=3-$i;$j++){
        echo '&nbsp;';  
    }
    for($k=0;$k<=2*$i;$k++){
        echo '*';   
    }
    echo '<br/>';       
}

2、冒泡排序,C里基础算法,从小到大对一组数排序。

思路:这题从小到大,第一轮排最小,第二轮排第二小,第三轮排第三小,依次类推……

<?php
$arr = array(3, 2, 1);
$n = count($arr);

//每循环一次,就跑一趟后面的排序
for($j=0; $j<$n-1; $j++) {
//对后面没排好的,循环查找出最大(最小)的,进行一趟排序
    for($i=$j; $i<$n-1; $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

<?php
//每行的第一个和最后一个都为1,写了6行
for($i=0; $i<6; $i++) {
    $a[$i][0]=1;
    $a[$i][$i]=1;
}

//出除了第一位和最后一位的值,保存在数组中
for($i=2; $i<6; $i++) {
    for($j=1; $j<$i; $j++) {
      $a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
    }
}

//打印
for($i=0; $i<6; $i++){
    for($j=0; $j<=$i; $j++) {
    echo $a[$i][$j].'&nbsp;';
    }
    echo '<br/>';
}

4、在一组数中,要求插入一个数,按其原来顺序插入,维护原来排序方式。

思路:找到比要插入数大的那个位置,替换,然后把后面的数后移一位。

<?php
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//如果要插入的数已经最大,直接打印
if($arr[$n-1] < $in) {
    $arr[$n+1] = $in; print_r($arr);
    }

for($i=0; $i<$n; $i++) {
//找出要插入的位置
    if($arr[$i] >= $in){
        $t1= $arr[$i];
        $arr[$i] = $in;
//把后面的数据后移一位
        for($j=$i+1; $j<$n+1; $j++) {
            $t2 = $arr[$j];
            $arr[$j] = $t1;
            $t1 = $t2;
    }
//打印
    print_r($arr);
    die;
    }
}

5、对一组数进行排序(快速排序算法)。

思路:通过一趟排序分成两部分,然后递归对这两部分排序,最后合并。

<?php
function q($array) {
    if (count($array) <= 1) {return $array;}
//以$key为界,分成两个子数组
    $key = $array[0];
    $l = array();
    $r = array();

//分别进行递归排序,然后合成一个数组
    for ($i=1; $i<count($array); $i++) {
    if ($array[$i] <= $key) { $l[] = $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、在一个数组查找你所需元素(二分查找算法)。

思路:以数组中某个值为界,再递归进行查找,直到结束。

<?php
function find($array, $low, $high, $k){
    if ($low <= $high){
    $mid = intval(($low+$high)/2);
        if ($array[$mid] == $k){
        return $mid;
    }elseif ($k < $array[$mid]){
        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(),题目来于论坛。

思路:遍历每个数组,重新组成一个新数组。

<?php
function t(){
    $c = func_num_args()-1;
    $a = func_get_args();
    //print_r($a);
    for($i=0; $i<=$c; $i++){
        if(is_array($a[$i])){
            for($j=0; $j<count($a[$i]); $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 '<br/>';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);

8、牛年求牛:有一母牛,到4岁可生育,每年一头,所生均是一样的母牛,到15岁绝育,不再能生,20岁死亡,问n年后有多少头牛。(来自论坛)

<?php
function t($n) {
        static $num = 1
        for($j=1; $j<=$n; $j++){
                if($j>=4 && $j<15) {$num++;t($n-$j);}
                if($j==20){$num--;}
         }
          return $num;
}

//test
echo t(8);

 

原文地址:http://www.cnblogs.com/justforfun/archive/2009/04/27/1444346.html

版权说明

  如果标题未标有<转载、转>等字则属于作者原创,欢迎转载,其版权归作者和博客园共有。
  作      者:温景良
  文章出处:http://wenjl520.cnblogs.com/  或  http://www.cnblogs.com/

posted @ 2009-04-27 14:54 温景良(Jason) Views(90) Comments(0) Edit 收藏
 

公告

 
本文转自我的程序人生博客园博客,原文链接:http://www.cnblogs.com/wenjl520/archive/2009/04/27/1444606.html,如需转载请自行联系原作者
 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: