Collection of php classic algorithms_php skills

The examples in this article describe several classic algorithms in PHP. Share it with everyone for your reference, the details are as follows:

5 people stole a bunch of apples and planned to divide the spoils the next day. In the evening, a man walked out and divided all the vegetables and fruits into 5 parts, but there was an extra one. He threw this to the monkey in the tree and hid 1/5 first. Unexpectedly, the other four people also thought the same way. They all divided it into 5 parts like the first person and threw the extra piece to the monkey, stealing 1/5. The next day, everyone divided the spoils, and they also divided it into 5 parts and threw one more to the monkey. The last person got a share. Question: How many apples are there?

for ($i = 1; ; $i++)
{
  if ($i%5 == 1) {
    //第一个人取五分之一，还剩$t
    $t = $i - round($i/5) - 1;
    if($t % 5 == 1)
    {
      //第二个人取五分之一，还剩$r
      $r = $t - round($t/5) - 1;
      if($r % 5 == 1)
      {
        //第三个人取五分之一，还剩$s
        $s = $r - round($r/5) - 1;
        if($s % 5 == 1)
        {
          //第四个人取五分之一，还剩$x
          $x = $s - round($s/5) - 1;
          if($x % 5 == 1)
          {
            //第五个人取五分之一，还剩$y
            $y = $x - round($x/5) - 1;
            if ($y % 5 == 1) {
              echo $i;
              break;
            }
          }
        }
      }
    }
  }
}

A group of monkeys line up in a circle and are numbered 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);
  $i=0;
  $k=$n;
  while (count($monkeys)>1) {
    if(($i+1)%$m==0) {
      unset($monkeys[$i]);
    } else {
      array_push($monkeys,$monkeys[$i]);
      unset($monkeys[$i]);
    }
    $i++;
  }
  return current($monkeys);
}
$a = king(5, 2);
var_dump($a);

The Tower of Hanoi (also known as the Tower of Hanoi) is an ancient legend in India. Brahma, the god who created the world, left three diamond rods in a temple. The first one was covered with 64 round gold pieces. The largest one was at the bottom, and the others were smaller than the other. They were stacked up one after another. In the temple The monks tirelessly moved them one by one from one stick to another. It was stipulated that the middle stick could be used as a help, but only one could be moved at a time, and the big one could not be placed on top of the small one. . Please run the calculation yourself to find the answer. See the program at the end. Faced with the huge number (the number of times the disk has been moved) 18446744073709551615, it seems that even if the monks spend their entire lives, it is impossible to complete the movement of the gold disk.

Later, this legend evolved into the Tower of Hanoi game:

1. There are three poles A, B and C. There are several plates on pole A
2. When moving one plate at a time, the smaller one can only be stacked on top of the larger one
3. Move all the dishes from pole A to pole C

After research, it was found that the solution to the Tower of Hanoi is very simple, just move the gold pieces in one direction according to the movement rules:
For example, the movement of the third-order Tower of Hanoi: A→C,A→B,C→B,A→C,B→A,B→C,A→C

In addition, the Tower of Hanoi problem is also a classic recursion problem in programming.

function hanoi($n,$x,$y,$z){
  if($n==1){
    echo 'move disk 1 from '.$x.' to '.$z."\n";
  }else{
    hanoi($n-1,$x,$z,$y);
    echo 'move disk '.$n.' from '.$x.' to '.$z."\n";
    hanoi($n-1,$y,$x,$z);
  }   
}
hanoi(3,'A','B','C');

Use PHP to describe bubble sort and quick sort algorithms, the object can be an array

//对数组冒泡排序
function bubble_sort($array){
  $count = count($array);
  if ($count <= 0) 
    return false;
    for($i=0; $i<$count; $i++){
      for($j=$count-1; $j>$i; $j–){
      if ($array[$j] < $array[$j-1]){
        $tmp = $array[$j];
        $array[$j] = $array[$j-1];
        $array[$j-1] = $tmp;
    }
  }
}
return $array;
}
function quick_sort($array) {
  if (count($array) <= 1) return $array;
  $key = $array[0];
  $left_arr = array();
  $right_arr = array();
  for ($i=1; $i<count($array); $i++){
  if ($array[$i] <= $key)
    $left_arr[] = $array[$i];
  else
    $right_arr[] = $array[$i];
  }
  $left_arr = quick_sort($left_arr);
  $right_arr = quick_sort($right_arr);
  return array_merge($left_arr, array($key), $right_arr);
}

Use PHP to describe sequential search and binary search algorithms. Sequential search must consider efficiency. The object can be an ordered array

//使用二分查找数组中某个元素
function bin_sch($array, $low, $high, $k){
  if ($low <= $high){
    $mid = intval(($low+$high)/2);
    if ($array[$mid] == $k){
      return $mid;
    }elseif ($k < $array[$mid]){
    return bin_sch($array, $low, $mid-1, $k);
  }else{
    return bin_sch($array, $mid+1, $high, $k);
  }
  }
  return -1;
}

Write a two-dimensional array sorting algorithm function, which can call PHP built-in functions and has universality

function array_sort($arr, $keys, $order=0) {
  if (!is_array($arr)) {
    return false;
  }
  $keysvalue = array();
  foreach($arr as $key => $val) {
    $keysvalue[$key] = $val[$keys];
  }
  if($order == 0){
    asort($keysvalue);
  }else {
    arsort($keysvalue);
  }
  reset($keysvalue);
  foreach($keysvalue as $key => $vals) {
    $keysort[$key] = $key;
  }
  $new_array = array();
  foreach($keysort as $key => $val) {
    $new_array[$key] = $arr[$val];
  }
  return $new_array;
}

I hope this article will be helpful to everyone in PHP programming.