PHP interesting classic algorithms

Many people have written some interesting algorithms when learning C language. In fact, these algorithms can also be implemented in PHP, and even the codes of some algorithms are longer than those in C language. concise.

1. A group of monkeys line up in a circle and number them sequentially according to 1, 2,...,n. Then start counting from the 1st one, count to the mth one, kick it out of the circle, start counting from behind it, count to the mth one, kick it out..., and continue in this way until the end. Until there is only one monkey left, that monkey is called the king. Programming is required to simulate this process, input m, n, and output the number of the last king.

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

2. There is a cow that becomes fertile at the age of 4. One cow is born every year. All the offspring are the same. The cow is sterilized at the age of 15 and can no longer bear children. It dies at the age of 20. How many cows will there be in n years? Cow.

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. Yang Hui Triangle

<?php
/* 默认输出十行，用T(值)的形式可改变输出行数 */
class T{
  private $num;
  public function __construct($var=10) {
    if ($var<3) die("值太小啦！");
    $this->num=$var;
  }
  public function display(){
    $n=$this->num;
    $arr=array();
  //$arr=array_fill(0,$n+1,array_fill(0,$n+1,0));
    $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/>";
    }
  }
}
$yh=new T(&#39;3&#39;); //$yh=new T(数量);
$yh->display();
?>

4. Bubble sort

function maopao($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. Quick sort

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 = quickSort($left_array);
    $right_array = quickSort($right_array);
    //合并
  
    return array_merge($left_array, array($base_num), $right_array);
}

6. Binary search algorithm (half search algorithm )

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;
        } else{
            return $middle;
        }
    }
    return false;
}

7.PHP strange algorithm

<?php
function test(){
 $a=1;
 $b=&$a;
 echo (++$a)+(++$a);
}
test();

Versions below PHP7 return 6, and versions below PHP7 return 5, which is really strange. Personally, the underlying algorithm is poor, so I think it is a version below PHP7. BUG8. Character set: Enter a string, find the character set contained in the string, and sort it in order (English)

function set($str){
    //转化为数组
    $arr = str_split($str);
    //去除重复
    $arr = array_flip(array_flip($arr));
    //排序
    sort($arr);
    //返回字符串
    return implode('', $arr);
}

9. Traverse all files under a file and files under subfolders

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;         //输出文件名
                }
            }
        } 
    }
}

10. Extract the file extension from a standard Url

function getExt($url)
 {
 $arr = parse_url($url);
 $file = basename($arr['path']);// basename函数返回路径中的文件名部分
 $ext = explode('.', $file);
 return $ext[count($ext)-1];
 }

11. Someone wants to go up to n levels, but he can only take 1 or 2 steps at a time. Stairs, ask: How many ways can this person complete the steps? For example: There are 3 steps in total. You can take step 1 first and then step 2, or step 2 first and then step 1, or step 1 level 3 times for a total of 3 ways.

function jieti($num){   //实际上是斐波那契数列
 return $num<2?1:jieti($num-1)+jieti($num-2);
 }

12. Please write a PHP paragraph Code to ensure that multiple processes write to the same file successfully at the same time

<?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);
?>

13. Unlimited classification

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;
 }

14. Get the first and last day of the previous month // Get the previous month The first day

date('Y-m-01',strtotime('-1 month'));
  
 //获取上个月最后一天
 date('Y-m-t',strtotime('-1 month'));复制代码15.随机输入一个数字能查询到对应的数据区间//把区间换成数组写法，用二分法查找区间
 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 &#39;在区间&#39;.$a[$high].&#39;到&#39;.$a[$lower];  
 }
  
 $array = [&#39;1&#39;,&#39;50&#39;,&#39;100&#39;,&#39;150&#39;,&#39;200&#39;,&#39;250&#39;,&#39;300&#39;];
 $a = &#39;120&#39;;
 echo binsearch($a,$array);

Recommended tutorial: "PHP Tutorial"

The above is the detailed content of PHP interesting classic algorithms. For more information, please follow other related articles on the PHP Chinese website!