你应该熟悉的10个PHP常见算法

php基础

浏览数:186

2019-8-26

AD:资源代下载服务

1.猴王算法

一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。

    /**
     * @param $m
     * @param $n
     * @return mixed
     *
     */
    private function monkeysKing($m, $n)
    {
        //创建猴群 - 1到n数组
        $monkeys = range(1, $m);
        //循环条件 - 猴子数量大于1
        $i = 0;//数组下标
        while (count($monkeys) > 1) {
            //$i为数组下标;$i+1为猴子标号
            //余数等于0表示正好第m个,删除,用unset删除保持下标关系
            if (($i + 1) % $n == 0) {
                unset($monkeys[$i]);
            } else {
                //如果余数不等于0,则把数组下标为$i的放最后,形成一个圆形结构,
                array_push($monkeys, $monkeys[$i]);
                //圆形结构,添加一个,就要去掉一个
                unset($monkeys[$i]);
            }
            //$i 循环+1,不断把猴子删除,或 push到数组
            $i++;
        }
        //猴子数量等于1时输出猴子标号,得出猴王
        return current($monkeys);
    }

2.牛群算法

有一头母牛,4岁可生育,每年生一头,所生均是母牛,到15岁绝育不再能生,20岁死亡。问n年后有多少头牛?

/**
 * @param $y
 * @return int
 */
function niu($y){
    static $num= 1;                 //定义静态变量;初始化牛的数量为1
    for ($i=1; $i <=$y ; $i++) {    
        if($i>=4 && $i<15){       //每年递增来算,4岁开始+1,15岁不能生育
        $num++;
            niu($y-$i);             //递归方法计算小牛$num,小牛生长年数为$y-$i
        }else if($i==20){           
        $num--;                          //20岁死亡减一
        }
    }
    return $num;
}

3.杨辉三角

 private function Triangle($n)
    {
        $arr = array();
        $arr[1] = array_fill(0, 3, 0);
        $arr[1][1] = 1;
        echo str_pad(" ", $n * 12, " ");
        printf("%3d", $arr[1][1]);
        echo "<br/>";
        for ($i = 2; $i <= $n; $i++) {
            $arr[$i] = array_fill(0, ($i + 2), 0);
            for ($j = 1; $j <= $i; $j++) {
                if ($j == 1)
                    echo str_pad(" ", ($n + 1 - $i) * 12, " ");
                printf("%3d", $arr[$i][$j] = $arr[$i - 1][$j - 1] + $arr[$i - 1][$j]);
                echo "  ";
            }
            echo "<br/>";
        }
    }

4.冒泡排序

    /**
     * @param $arr
     * @return mixed
     *
     * 冒泡排序算法的原理如下:
     * 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
     * 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
     * 3.针对所有的元素重复以上的步骤,除了最后一个。
     * 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
     */
    private function bubbleSort($arr)
    {
        //获取 长度
        $len = count($arr);
        //循环比较(相邻的两个元素,比较,交换)
        for ($k = 0; $k <= $len; $k++) {
            for ($j = $len - 1; $j > $k; $j--) {
                //比较
                if ($arr[$j] < $arr[$j - 1]) {
                    //交换
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j - 1];
                    $arr[$j - 1] = $temp;
                }
            }
        }
        return $arr;
    }

5.快速排序

/**
     * @param $arr
     * @return array
     *
     * 快速排序算法原理如下:
     *  1.通过设置一个初始中间值,来将需要排序的数组分成3部分:小于中间值的左边,中间值,大于中间值的右边
     *  2.继续递归用相同的方式来排序左边和右边
     *  3.最后合并数组
     */
    private function quickSort($arr)
    {
        //先判断要排序的数据是否符合要求
        $length = count($arr);
        if ($length <= 1) {
            return $arr;
        }
        //选择一个数作为参照
        $base_num = $arr[0];

        //遍历除了参照外的所有元素,按照大小关系放入两个数组内
        //初始化两个数组
        $left_array = array();//存放大于参照的
        $right_array = array();//存放小于参照的

        //遍历分组
        for ($i = 1; $i < $length; $i++) {
            if ($base_num > $arr[$i]) {
                $left_array[] = $arr[$i];
            } else {
                $right_array[] = $arr[$i];
            }
        }

        //在分别对这两个数组进行递归处理
        $left_array = $this->quickSort($left_array);
        $right_array = $this->quickSort($right_array);

        //合并数组并输出
        return array_merge($left_array, array($base_num), $right_array);
    }

6.二分查找算法(折半查找算法)

    /**
     * @param $x
     * @param $a
     * @return bool|int
     *
     * 二分查找,需要数组是一个有序数组
     * 循环实现
     */
    private function binLoop($x, $a)
    {
        $c = count($a);
        $lower = 0;
        $high = $c - 1;
        while ($lower <= $high) {
            //取中间值
            $middle = intval(($lower + $high) / 2);//intval() 函数用于获取变量的整数值
            //比较(一半一半的比),必须是有序数组
            if ($a[$middle] > $x) {
                $high = $middle - 1;//在前一半里查
            } elseif ($a[$middle] < $x) {
                $lower = $middle + 1;//在后一半里查
            } else {
                return $middle;
            }
        }
        return false;
    }

    /**
     * @param $x
     * @param $a
     * @param $lower
     * @param $high
     * @return bool|int
     *
     * 二分查找,需要数组是一个有序数组
     * 递归实现
     */
    private function binRecursive($x, &$a, $lower = 0, $high = 11)
    {
        //$lower开始位置 $high结束位置
        //采用二分法查找
        $c = count($a);
        if ($high > $c) {
            return false;
        }
        if ($lower <= $high) {
            $middle = intval(($lower + $high) / 2);
            if ($a[$middle] == $x) {
                return $middle;
            } elseif ($a[$middle] < $x) {//在后半段里查
                return $this->binSearchRecursive($x, $a, $middle + 1, $high);
            } else {//在前半段里查
                return $this->binSearchRecursive($x, $a, $lower, $middle - 1);
            }
        } else {
            return false;
        }
    }

7.遍历一个文件下的所有文件和子文件夹下的文件

function AllFile($dir){
    if($dh = opendir($dir)){
        while (($file = readdir($dh)) !== false){
            if($file !='..' && $file !='.'){
                if(is_dir($dir.'/'.$file)){
                    AllFile($dir.'/'.$file);    //如果判断还是文件,则递归
                }else{  
                    echo $file;         //输出文件名
                }
            }
        } 
    }
}

8.请写一段PHP代码,确保多个进程同时写入同一个文件成功

<?php
    $fp = fopen("lock.txt","w+");
    if (flock($fp,LOCK_EX)) {
        //获得写锁,写数据
        fwrite($fp, "write something");
 
        // 解除锁定
        flock($fp, LOCK_UN);
    } else {
        echo "file is locking...";
    }
    fclose($fp);
?>

9.无限级分类

function tree($arr,$pid=0,$level=0){
        static $list = array();
        foreach ($arr as $v) {
            //如果是顶级分类,则将其存到$list中,并以此节点为根节点,遍历其子节点
            if ($v['pid'] == $pid) {
                $v['level'] = $level;
                $list[] = $v;
                tree($arr,$v['id'],$level+1);
            }
        }
        return $list;
    }

10.随机输入一个数字能查询到对应的数据区间

//把区间换成数组写法,用二分法查找区间
    function binsearch($x,$a){  
        $c=count($a);  
        $lower=0;  
        $high=$c-1;  
        while($lower<=$high){  
            $middle=intval(($lower+$high)/2);  
            if($a[$middle]>=$x){  
                $high=$middle-1;
            }elseif($a[$middle]<=$x ){  
                $lower=$middle+1;
            }   
        }
 
        return '在区间'.$a[$high].'到'.$a[$lower];  
    }
 
    $array  = ['1','50','100','150','200','250','300'];
    $a = '120';
    echo binsearch($a,$array);

作者:赵客缦胡缨v吴钩霜雪明