PHP classic interesting algorithm

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

To learn more about PHP, you can click us

1. A group of monkeys line up in a circle, press 1, 2 ,...,n are numbered in sequence. 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 can give birth to children at the age of 4. One cow is born every year. All the offspring are the same cow. She is sterilized at the age of 15 and can no longer bear children. 20 If a person dies at the age of n years, how many cows will he have after n years?

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

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 "
";
    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"
";
    }
  }
}
$yh=new T('3'); //$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 singular algorithm

Versions below PHP7 return 6, and versions below PHP7 return 5, which is really strange. Personally, the underlying algorithm is poor, and I think it is a BUG in versions below PHP7

 8. 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 the characters under a file All files 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. Yes A person wants to go up n steps, but he can only take 1 or 2 steps at a time. Question: How many ways can this person complete the step? For example: There are 3 steps in total. You can take step 1 first and then step 2, or step 2 steps 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 piece of PHP code to ensure that multiple processes can successfully write to the same file at the same time
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 last month
//获取上个月第一天
    date('Y-m-01',strtotime('-1 month'));
 
    //获取上个月最后一天
    date('Y-m-t',strtotime('-1 month'));
15. Randomly input a number to query the corresponding data interval
//把区间换成数组写法，用二分法查找区间
	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);
The above is the detailed content of PHP classic interesting algorithm. For more information, please follow other related articles on the PHP Chinese website!