Differences between classic algorithm questions in PHP

PHP’s algorithm can be said to be very powerful. Some people say that if you want to learn programming languages ​​​​such as PHP, you must have good logical thinking. Then all programmers should take a look at the following question!

Five 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 dishes on pole A
2. Move one dish at a time, and 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 cracking of 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 Tower of Hanoi at level 3: 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, you can Calling PHP built-in functions can be universal

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

Have you done it? If you haven't done it yet, just use the PHP algorithm and follow the above method to complete this question.

The above is the detailed content of Differences between classic algorithm questions in PHP. For more information, please follow other related articles on the PHP Chinese website!