Maison > Article > développement back-end > structures de données et algorithmes php
<?php class Test implements Iterator{ private $item = array('id'=>1,'name'=>'php'); public function rewind(){ reset($this->item); } public function current(){ return current($this->item); } public function key(){ return key($this->item); } public function next(){ return next($this->item); } public function valid(){ return($this->current()!==false); } } //测试 $t=new Test; foreach($t as $k=>$v){ echo$k,'--->',$v,'<br/>'; }?>
<?php class Deque{ private $queue=array(); public function addFirst($item){ return array_unshift($this->queue,$item); } public function addLast($item){ return array_push($this->queue,$item); } public function removeFirst(){ return array_shift($this->queue); } public function removeLast(){ return array_pop($this->queue); } }?>3. Veuillez utiliser La méthode de tri à bulles trie l'ensemble de données suivant 10 2 36 14 10 25 23 85 99 45.
<?php // 冒泡排序 function bubble_sort(&$arr){ for ($i=0,$len=count($arr); $i < $len; $i++) { for ($j=1; $j < $len-$i; $j++) { if ($arr[$j-1] > $arr[$j]) { $temp = $arr[$j-1]; $arr[$j-1] = $arr[$j]; $arr[$j] = $temp; } } } } // 测试 $arr = array(10,2,36,14,10,25,23,85,99,45); bubble_sort($arr); print_r($arr);?>4. Écrivez un algorithme de tri (écrivez du code) et indiquez comment l'optimiser. (Sina)
<?php //快速排序 function partition(&$arr,$low,$high){ $pivotkey = $arr[$low]; while($low<$high){ while($low < $high && $arr[$high] >= $pivotkey){ $high--; } $temp = $arr[$low]; $arr[$low] = $arr[$high]; $arr[$high] = $temp; while($low < $high && $arr[$low] <= $pivotkey){ $low++; } $temp=$arr[$low]; $arr[$low]=$arr[$high]; $arr[$high]=$temp; } return$low; }function quick_sort(&$arr,$low,$high){ if($low < $high){ $pivot = partition($arr,$low,$high); quick_sort($arr,$low,$pivot-1); quick_sort($arr,$pivot+1,$high); } }?>Cet algorithme est implémenté par récursion diviser pour régner. Son efficacité dépend en grande partie de la sélection des éléments de référence. Vous pouvez choisir l'élément central du tableau, ou vous pouvez en obtenir trois. éléments au hasard, puis sélectionnez l'élément du milieu (méthode médiane à trois nombres).
Un autre point est que lorsque nous divisons, si la longueur de la sous-séquence divisée est très petite (moins de 5 à 20), l'efficacité du tri récursif n'est généralement pas aussi rapide que le tri par insertion ou le tri Hill. Par conséquent, vous pouvez juger de la longueur du tableau si elle est inférieure à 10, utilisez le tri par insertion directement au lieu d'appeler ce tri rapide de manière récursive.
<?php // 方案一,使用php来模拟这个过程 function king($n,$m){ $mokey = range(1, $n); $i = 0; while (count($mokey) >1) { $i += 1; $head = array_shift($mokey);//一个个出列最前面的猴子 if ($i % $m !=0) { #如果不是m的倍数,则把猴子返回尾部,否则就抛掉,也就是出列 array_push($mokey,$head); } // 剩下的最后一个就是大王了 return $mokey[0]; } } // 测试 echo king(10,7); // 方案二,使用数学方法解决 function josephus($n,$m){ $r = 0; for ($i=2; $i <= $m ; $i++) { $r = ($r + $m) % $i; } return $r+1; } // 测试 print_r(josephus(10,7));?>6. Écrivez une fonction d'algorithme de tri de tableau bidimensionnel qui est polyvalente et peut appeler des fonctions intégrées PHP .
<?php//二维数组排序,$arr是数据,$keys是排序的健值,$order是排序规则,1是降序,0是升序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; } //测试 $person=array( array('id'=>2,'name'=>'zhangsan','age'=>23), array('id'=>5,'name'=>'lisi','age'=>28), array('id'=>3,'name'=>'apple','age'=>17) ); $result = array_sort($person,'name',1); print_r($result);?>7. Utilisez la méthode binaire pour trouver un tableau linéaire trié de longueur 10. Lorsque la recherche échoue, le nombre maximum de comparaisons requises est (Xiaomi) 48. Sélectionnez au hasard trois nombres différents parmi ces dix nombres 0,1,2,3,4,5,6,7,8,9, "les trois nombres n'incluent pas 0 et 5" La probabilité est ( Xiaomi) 15/79. Il y a 3 souris aux trois sommets d'un triangle Lorsqu'un coup de feu se fait entendre, les 3 souris commencent à se déplacer à une vitesse constante le long des côtés du triangle. le triangle. Veuillez leur demander. La probabilité de rencontre est (Xiaomi) 75%. Chaque souris a deux sens de mouvement : dans le sens des aiguilles d'une montre et dans le sens inverse. Il y a 8 situations de mouvement pour 3 souris. Uniquement lorsque les 3 souris sont dans le sens des aiguilles d'une montre. ou dans le sens inverse des aiguilles d'une montre, ils ne se rencontreront pas et les 6 situations restantes se rencontreront, donc la probabilité de se rencontrer est de 6/8 = 75 %.
<?php /** * 顺序查找 * @param array $arr 数组 * @param $k 要查找的元素 * @return mixed 成功返回数组下标,失败返回-1 */ function seq_sch($arr,$k){ for ($i=0,$n = count($arr); $i < $n; $i++) { if ($arr[$i] == $k) { break; } } if($i < $n){ return $i; }else{ return -1; } } /** * 二分查找,要求数组已经排好顺序 * @param array $array 数组 * @param int $low 数组起始元素下标 * @param int $high 数组末尾元素下标 * @param $k 要查找的元素 * @return mixed 成功时返回数组下标,失败返回-1 */ 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; } // 测试:顺序查找 $arr1 = array(9,15,34,76,25,5,47,55); echo seq_sch($arr1,47);//结果为6 echo "<br />"; // 测试:二分查找 $arr2 = array(5,9,15,25,34,47,55,76); echo bin_sch($arr2,0,7,47);//结果为5?>
<?php $card_num = 54;//牌数 function wash_card($card_num){ $cards = $tmp = array(); for($i = 0;$i < $card_num;$i++){ $tmp[$i] = $i; } for($i = 0;$i < $card_num;$i++){ $index = rand(0,$card_num-$i-1); $cards[$i] = $tmp[$index]; unset($tmp[$index]); $tmp = array_values($tmp); } return $cards; } // 测试: print_r(wash_card($card_num));?>
冒泡排序,快速排序,插入排序,选择排序。
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!