PHP basic algorithm_PHP tutorial

PHP basic algorithm
Here are several basic algorithms written in PHP. The importance of algorithms seems not to be important to PHP programmers
Yes, it is actually very important. The classic saying: Algorithm + data structure = program. As a true advanced PHP
Programmers, I think you should be familiar with C. If you want to become a real programmer, please learn C and data structure well
Structure and algorithm. Here are just a few basic algorithms, there is still a lot to learn...
1. First, let’s draw a rhombus for fun. Many people have drawn it in books when they were learning C. Let’s use PHP to draw it. Draw
Half done.
Idea: How many lines do for once, and then use spaces and asterisks for once in it.
Code snippet
for($i=0;$i<=3;$i++){
for($j=0;$j<=3-$i;$j++){
echo ' ';
}
for($k=0;$k<=2*$i;$k++){
echo '*';
}
echo '
';
}
2. Bubble sorting, the basic algorithm in C, sorts a set of numbers from small to large.
Idea: This question is arranged from smallest to largest. The first round ranks the smallest, the second round ranks the second smallest, the third round ranks the third smallest, in order
Analogy...
Code snippet
$arr = array(3, 2, 1);
$n = count($arr);
//Every time it loops, run the subsequent sorting
for($j=0; $j<$n-1; $j++) {
// For those that are not sorted, loop through to find the largest (smallest) one, and perform a sorting
for($i=$j; $i<$n-1; $i++) {
if($arr[$j] > $arr[$i+1]) {
$t = $arr[$j];
$arr[$j] = $arr[$i+1];
$arr[$i+1] = $t;
}
}
}
print_r($arr);
3. Yang Hui Triangle, written in PHP.
Idea: The first and last digits of each row are 1, there is no change, the middle is the front row digit and the left row
The sum of One line of output, if you are interested, write it and play with it.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Code snippet
//The first and last characters of each line are both 1, and 6 lines are written
for($i=0; $i<6; $i++) {
$a[$i][0]=1;
$a[$i][$i]=1;
}
//Extract the first and last values ​​and save them in the array
for($i=2; $i<6; $i++) {
for($j=1; $j<$i; $j++) {
$a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
}
}
// print
for($i=0; $i<6; $i++){
for($j=0; $j<=$i; $j++) {
echo $a[$i][$j].' ';
}
echo '
';
}
4. In a set of numbers, if a number is required to be inserted, insert it in its original order and maintain the original sorting method.
Idea: Find the position that is larger than the number to be inserted, replace it, and then move the following number back by one.
Code snippet
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//If the number to be inserted is already the maximum, print directly
if($arr[$n-1] < $in) {
$arr[$n+1] = $in; print_r($arr);}
for($i=0; $i<$n; $i++) {
//Find out where to insert
if($arr[$i] >= $in){
$t1= $arr[$i];
$arr[$i] = $in;
//Move the following data one digit
for($j=$i+1; $j<$n+1; $j++) {
$t2 = $arr[$j];
$arr[$j] = $t1;
$t1 = $t2;
}
// print
print_r($arr);
die;
}
}
5. Sort a set of numbers (quick sort algorithm).
Idea: divide it into two parts through one sorting, then recursively sort the two parts, and finally merge them.
Code snippet
function q($array) {
if (count($array) <= 1) {return $array;}
//Using $key as the boundary, divide it into two sub-arrays
$key = $array[0];
$l = array();
$r = array();
//Carry out recursive sorting separately, and then synthesize an array
for ($i=1; $i if ($array[$i] <= $key) { $l[] = $array[$i]; }
else { $r[] = $array[$i]; }
}
$l = q($l);
$r = q($r);
return array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
print_r( q($arr) );
6. Find the element you need in an array (binary search algorithm).
Idea: Use a certain value in the array as the boundary, and then search recursively until the end.
Code snippet
function find($array, $low, $high, $k){
if ($low <= $high){
$mid = intval(($low+$high)/2);
if ($array[$mid] == $k){
return $mid;
}elseif ($k < $array[$mid]){
return find($array, $low, $mid-1, $k);
}else{
return find($array, $mid+1, $high, $k);
}
}
die('Not have...');
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,
7. Merge multiple arrays without array_merge(). The question comes from the forum.
Idea: Traverse each array and reconstruct a new array.
Code snippet
function t(){
$c = func_num_args()-1;
$a = func_get_args();
//print_r($a);
for($i=0; $i<=$c; $i++){
if(is_array($a[$i])){
for($j=0; $j $r[] = $a[$i][$j];
}
} else {
die('Not a array!');
}
}
return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4)));
echo '
';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
8. Ask for a cow in the Year of the Ox: There is a cow that can give birth to 4 years old, one cow every year, and all the offspring will be the same cow, until
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? (from forum) code snippet
function t($n) {
static $num = 1
for($j=1; $j<=$n; $j++){
if($j>=4 && $j<15) {$num++;t($n-$j);}
if($j==20){$num--;}
}
return $num;
}
//test
echo t(8);