English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
本文实例总结了PHP经典算法。分享给大家供大家参考，具体如下：
1、首先来画个菱形玩玩，很多人学C时在书上都画过，咱们用PHP画下，画了一半。
Pensiero: Quante volte fare un ciclo for, poi dentro a spazi e stelle fare un altro ciclo for.
<?php
for($i=0;$i<=3;$i++){
echo str_repeat(" ",3-$i);
echo str_repeat("*",$i*2+1);
echo '<br/>';
}
2、冒泡排序，C语言中的基本算法，用于对一组数进行从小到大的排序。
Pensiero: Questo problema deve essere ordinato da piccolo a grande, la prima volta ordina il più piccolo, la seconda volta il secondo più piccolo, la terza volta il terzo più piccolo, e così via...
<?php
$arr = array(1,3,5,32,756,2,6);
$len = count($arr);
for ($i=0;$i<$len-1;$i++){
per ($j=$i+1;$j<$len;$j++){}}
se($arr[$i]>$arr[$j]){//ordinato da piccolo a grande
$p = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j]= $p;
}
}
}
stampa_r($arr);
3、 triangolo di Pascal, scritto in PHP.
ragione: la prima e l'ultima colonna di ogni riga sono 1, senza cambiamenti, nel mezzo è la somma del numero di una riga più in alto e della colonna di sinistra, questo algoritmo utilizza una matrice bidimensionale per salvare, c'è anche un altro algoritmo che può implementare con un array unidimensionale, una riga alla volta, scrivere di interesse a provare.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
<?php
//la prima e l'ultima riga sono 1, ho scritto 6 righe
per($i=0; $i<6; $i++) {
$a[$i][0]=1;
$a[$i][$i]=1;
}
//salva i valori tranne il primo e l'ultimo nella matrice
per($i=2; $i<6; $i++) {
per($j=1; $j<$i; $j++) {
$a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
}
}
//stampa
per($i=0; $i<6; $i++){
per($j=0; $j<=$i; $j++) {
stampa $a[$i][$j].' ';
}
echo '<br/>';
}
4、in un insieme di numeri, inserire un numero in ordine e mantenere l'ordine originale.
ragione: trovare la posizione del numero da inserire più grande, sostituire e spostare i numeri successivi di una posizione.
<?php
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = conta($arr);
//se il numero da inserire è già il più grande, stampa direttamente
se($arr[$n-1] < $in) {
$arr[$n+1] = $in; stampa_r($arr);
}
per($i=0; $i<$n; $i++) {
//trova la posizione da inserire
se($arr[$i] >= $in){
$t1= $arr[$i];
$arr[$i] = $in;
//sposta i dati successivi di una posizione
per($j=$i+1; $j<$n+1; $j++) {
$t2 = $arr[$j];
$arr[$j] = $t1;
$t1 = $t2;
}
//stampa
stampa_r($arr);
die;
}
}
5, ordinare un insieme di numeri (algoritmo di sortita veloce).
Pianificazione: dividere in due parti attraverso una sortita e ricorsivamente ordinare queste due parti, infine combinare.
<?php
funzione q($array) {
se (count($array) <= 1) {return $array;}
//dividere in due sottoarray con $key come limite
$key = $array[0];
$l = array();
$r = array();
//eseguire la sortita ricorsiva separatamente e poi combinare un array
per ($i=1; $i<count($array); $i++) {
se ($array[$i] <= $key) { $l[] = $array[$i]; }
altrimenti { $r[] = $array[$i]; }
}
$l = q($l);
$r = q($r);
ritornare array_merge($l, array($key), $r);
}
$arr = array(1,2,44,3,4,33);
stampa_r( q($arr) );
6, cercare l'elemento desiderato in un array (algoritmo di ricerca binaria).
Pianificazione: usare un valore dell'array come limite e ricorsivamente cercare fino alla fine.
<?php
funzione find($array, $low, $high, $k){
se ($low <= $high){
$mid = intval(($low+$high)/2);
se ($array[$mid] == $k){
ritornare $mid;
oppure ($k < $array[$mid]){
ritornare find($array, $low, $mid-1, $k);
}
ritornare find($array, $mid+1, $high, $k);
}
}
morire('Non c'è...');
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,5)
7, unire più array senza array_merge(), il problema è venuto dal forum.
Pianificazione: esplorare ogni array e riorganizzare in un nuovo array.
<?php
funzione t(){
$c = func_num_args()-1;
$a = func_get_args();
//stampa_r($a);
per($i=0; $i<=$c; $i++){
se(is_array($a[$i])){
for($j=0; $j<count($a[$i]); $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 '<br/>';
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
8、牛年求牛：有一母牛，到4岁可生育，每年一头，所生均是一样的母牛，到15岁绝育，不再能生，20岁死亡，问n年后有多少头牛。（来自论坛）
<?php
funzione 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);
===================== altri algoritmi =======================
ordinamento a bolle (bubble sort) — O(n2)
$data = array(3,5,9,32,2,1,2,1,8,5);
dump($data);
BubbleSort($data);
dump($data);
funzione BubbleSort(& $arr)
{
$limit = count($arr);
for($i=1; $i<$limit; $i++)
{
for($p=$limit-1; $p>=$i; $p--)
{
if($arr[$p-1] > $arr[$p])
{
$temp = $arr[$p-1];
$arr[$p-1] = $arr[$p];
$arr[$p] = $temp;
}
}
}
}
function dump( $d )
{
echo '<pre>';
print_r($d);
echo '</pre>';
}
ordinamento a inserimento (insertion sort) — O(n2)
$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data)-1;
dump( $data );
InsertionSort($data,$nums);
dump( $data );
funzione InsertionSort(& $arr,$n )
{
per ($i=1; $i<=$n; $i++)
{
$tmp = $arr[$i];
for( $j = $i; $j>0 && $arr[$j-1]>$tmp; $j-- )
{
$arr[$j] = $arr[$j-1];
}
$arr[$j] = $tmp;
}
}
function dump( $d )
{
echo '<pre>';print_r($d);echo '</pre>';
}
Ordinamento di Shell — O(n log n)
$data = array(6,13,21,99,18,2,25,33,19,84);
$nums = count($data);
dump( $data );
ShellSort($data,$nums);
dump( $data );
function ShellSort(& $arr,$n )
{
for( $increment = intval($n/2); $increment > 0; $increment = intval($increment/2) )
{
for( $i=$increment; $i<$n; $i++ )
{
$tmp = $arr[$i];
for( $j = $i; $j>= $increment; $j -= $increment )
if( $tmp < $arr[ $j-$increment ] )
$arr[$j] = $arr[$j-$increment];
else
break;
$arr[$j] = $tmp;
}
}
}
function dump( $d )
{
echo '<pre>';print_r($d);echo '</pre>';
}
Rapida ordinamento (quicksort) — O(n log n)
$data = array(6,13,21,99,18,2,25,33,19,84);
dump($data);
quicks($data,0,count($data)-1);
dump($data);
function dump( $data){
echo '<pre>';print_r($data);echo '</pre>';
}
function QuickSort(& $arr,$left,$right)
{
$l = $left;
$r = $right;
$pivot = intval(($r+$l)/2);
$p = $arr[$pivot];
do
{
while(($arr[$l] < $p) && ($l < $right))
$l++;
while(($arr[$r] > $p) && ($r > $left))
$r--;
if($l <= $r)
{
$temp = $arr[$l];
$arr[$l] = $arr[$r];
$arr[$r] = $temp;
$l++;
$r--;
}
}
while($l <= $r);
if($left < $r)
QuickSort(&$arr,$left,$r);
if($l < $right)
QuickSort(&$arr,$l,$right);
}
=================================================
冒泡排序：两两交换数值，最小的值在最左边，就如最轻的气泡在最上边。对整列数两两交换一次，最小的数在最左边，每次都能得一个在剩下的数中的最小的 数，“冒”出来的数组成一个有序区间，剩下的值组成一无序区间，且有序区间中每一元素值都比无序区间的小。
快速排序：基准数，左右二个数组，递归调用，合并。
插入排序：排序区间分成二部分，左边有序，右边无序，从右区间取 第一个元素插入左区间，若此元素比左边区间最右边的元素大，留在原处，若此元素比左 边区间最右边的元素小，则插在最右边元素的原位置，同时最右边元素右移一位，计算器减一，重新和前面的元素比较，直到前面的元素比要插入元素小为止，重复 上述步骤。
注意区间端点值的处理，及数组的第一个元素下标为0.
<?php
//PHP常用排序算法
function bubblesort ($array)
{
$n = count ($array);
for ($i = 0; $i < $n; $i++)
{
for ($j = $n - 2; $j >= $i; $j--) //[0,i-1] [i,n-1]
{
if ($array[$j] > $array[$j + 1])
{
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array [$j + 1] = $temp;
}
}
}
return $array;
}
$array = array (3,6,1,5,9,0,4,6,11);
print_r (bubblesort ($array));
echo '<hr>';
function quicksort ($array)
{
$n = count ($array);
if ($n <= 1)
{
return $array;
}
$key = $array['0'];
$array_r = array ();
$array_l = array ();
for ($i = 1; $i < $n; $i++)
{
if ($array[$i] > $key)
{
$array_r[] = $array[$i];
}
else
{
$array_l[] = $array[$i];
}
}
$array_r = quicksort ($array_r);
$array_l = quicksort ($array_l);
$array = array_merge ($array_l, array($key), $array_r);
return $array;
}
print_r (quicksort ($array));
echo '<hr>';
function insertsort ($array)
{
$n = count ($array);
for ($i = 1; $i < $n; $i++) //[0,i-1] [i,n]
{
$j = $i - 1;
$temp = $array[$i];
while ($array[$j] > $temp)
{
$array[$j + 1] = $array[$j];
$array[$j] = $temp;
$j--;
}
}
return $array;
}
print_r (insertsort ($array));
?>
=======================================
<?php
/*
【插入排序（一维数组）】
【基本思想】：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素 全部插入完为止。
[Esempio]:
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
*/
function insert_sort($arr){
$count = count($arr);
for($i=1; $i<$count; $i++){
$tmp = $arr[$i];
$j = $i - 1;
while($arr[$j] > $tmp){
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
$j--;
}
}
return $arr;
}
/*
【选择排序（一维数组）】
【基本思想】：In ogni iterazione, seleziona l'elemento più piccolo (o più grande) dagli elementi dati da ordinare e lo mette alla fine della sequenza già ordinata, fino a quando tutti gli elementi dati da ordinare sono ordinati.
[Esempio]:
[chiave iniziale] [49 38 65 97 76 13 27 49]
Dopo la prima iterazione di ordinamento 13 ［38 65 97 76 49 27 49］
Dopo la seconda iterazione di ordinamento 13 27 ［65 97 76 49 38 49］
Dopo la terza iterazione di ordinamento 13 27 38 [97 76 49 65 49]
Dopo la quarta iterazione di ordinamento 13 27 38 49 [49 97 65 76]
Dopo la quinta iterazione di ordinamento 13 27 38 49 49 [97 97 76]
Dopo la sesta iterazione di ordinamento 13 27 38 49 49 76 [76 97]
Dopo la settima iterazione di ordinamento 13 27 38 49 49 76 76 [ 97]
Risultato finale di ordinamento 13 27 38 49 49 76 76 97
*/
function select_sort($arr){
$count = count($arr);
for($i=0; $i<$count; $i++){
$k = $i;
for($j=$i+1; $j<$count; $j++){
if ($arr[$k] > $arr[$j])
$k = $j;
}
if($k != $i){
$tmp = $arr[$i];
$arr[$i] = $arr[$k];
$arr[$k] = $tmp;
}
}
return $arr;
}
/*
【冒泡排序（一维数组）】
【基本思想】：Confronta a due a due la grandezza degli elementi dati da ordinare, scambia due elementi di dati quando il loro ordine è inverso, fino a quando non ci sono più elementi di dati in ordine inverso.
【排序过程】：Immagina l'array R [1..N] eretto verticalmente, ogni elemento di dati è considerato come una bolla con peso, secondo il principio che le bolle leggere non possono essere sotto le bolle pesanti
Dalla parte inferiore verso l'alto, scansiona l'array R, per ogni bolle leggera che viola questo principio, fa che galleggi verso l'alto, e così via, fino a quando non rimane che qualsiasi due bolle siano le bolle leggere in alto e le bolle pesanti in basso.
[Esempio]:
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
*/
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;
}
/*
[Ordinamento rapido (array uno dimensionale)]
[Idea di base]: Scegliere un elemento di dati qualsiasi dell'area disordinata corrente R[1..H] come "elemento di riferimento" per il confronto (può essere notato X),
Dividere l'area disordinata corrente in due sottoinsiemi disordinati più piccoli di destra e sinistra usando questo elemento di riferimento: R[1..I-1] e R[I 1..H], e gli elementi del sottoinsieme disordinato di sinistra sono tutti minori o uguali all'elemento di riferimento,
Gli elementi del sottoinsieme disordinato di destra sono tutti maggiori o uguali all'elemento di riferimento, mentre l'elemento di riferimento X si trova nella posizione finale dell'ordinamento, ossia R[1..I-1]≤X.Key≤R[I 1..H] (1≤I≤H),
Quando R[1..I-1] e R[I 1..H] non sono vuoti, eseguire la procedura di divisione sopra menzionata per ciascuno di essi, fino a quando tutti gli elementi dei sottoinsiemi disordinati sono ordinati.
[Esempio]:
Parola chiave iniziale [49 38 65 97 76 13 27 49]
Dopo lo scambio primo [27 38 65 97 76 13 49 49]
Dopo lo scambio secondo [27 38 49 97 76 13 65 49]
Scansione a sinistra di J, posizione invariata, dopo lo scambio terzo [27 38 13 97 76 49 65 49]
Scansione a destra di I, posizione invariata, dopo lo scambio第四次 [27 38 13 49 76 97 65 49]
Scansione a sinistra di J [27 38 13 49 76 97 65 49]
(Procedura di divisione)
Parola chiave iniziale [49 38 65 97 76 13 27 49]
Dopo un passaggio di ordinamento [27 38 13] 49 [76 97 65 49]
Dopo due passaggi di ordinamento [13] 27 [38] 49 [49 65] 76 [97]
Dopo tre passaggi di ordinamento 13 27 38 49 49 [65] 76 97
Risultato finale di ordinamento 13 27 38 49 49 65 76 97
Stato dopo ogni fase di ordinamento
*/
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);
}
/*Stampa tutto il contenuto dell'array*/
function display_arr($array){
$len = count($array);
for($i = 0; $i<$len; $i++){
echo $array[$i].' ';
}
echo '<br />';
}
/*
Confronto e selezione di vari algoritmi di ordinamento
1. Fattori da considerare nella selezione del metodo di ordinamento:
(1) Numero di elementi da ordinare n;
(2) Dimensione dell'informazione dell'elemento stesso;
(3) Struttura delle chiavi e loro distribuzione;
(4) Condizioni degli strumenti linguistici, dimensione dello spazio ausiliario, ecc.
2. Conclusione:
(1) Se n è piccolo (n <= 50), può essere utilizzato l'ordinamento diretto o l'ordinamento diretto a selezione. Poiché l'ordinamento diretto richiede più operazioni di spostamento dei record rispetto all'ordinamento diretto a selezione, è meglio utilizzare l'ordinamento diretto a selezione quando l'informazione del record è grande.
(2) Se lo stato iniziale del file è già ordinato per chiave, è consigliabile utilizzare l'ordinamento diretto o il bubble sort.
(3) Se n è grande, allora deve essere utilizzato un metodo di ordinamento con complessità temporale O(nlog2n): ordinamento rapido, ordinamento a coda o ordinamento a fusione. L'ordinamento rapido è considerato il migliore tra i metodi di ordinamento interni basati su comparazione.
(4) Nei metodi di ordinamento basati su comparazione, dopo ogni confronto tra due chiavi, ci sono solo due possibili transizioni, quindi può essere descritto da un albero binario il processo di determinazione della comparazione, di conseguenza si può dimostrare: quando i n chiavi di un file sono distribuiti casualmente, qualsiasi algoritmo di ordinamento che si avvale di "comparazione" richiede almeno O(nlog2n) di tempo.
(5) 当记录本身信息量较大时，为了避免花费大量时间移动记录，可以使用链表作为存储结构。
*/
/*排序测试*/
$a = array('12','4','16','8','13','20','5','32');
echo 'The result of insert sort:';
$insert_a = insert_sort($a);
display_arr($insert_a);
echo 'The result of select sort:';
$select_a = select_sort($a);
display_arr($select_a);
echo 'The result of bubble sort:';
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo 'The result of bubble sort:';
$quick_a = quick_sort($a);
display_arr($quick_a);
?>
/**
* 排列组合
* 使用二进制方法进行组合选择，例如表示5选3时，只需有3位为1即可，因此可得到的组合有 01101 11100 00111 10011 01110 等10种组合
*
* @param 数组需要排列 $arr
* @param 最小个数 $min_size
* @return 新数组组合满足条件
*/
function pl($arr,$size=5) {
$len = count($arr);
$max = pow(2,$len);
$min = pow(2,$size)-1;
$r_arr = array();
for ($i=$min; $i<$max; $i++){
$count = 0;
$t_arr = array();
for ($j=0; $j<$len; $j++){
$a = pow(2, $j);
$t = $i&$a;
if($t == $a){
$t_arr[] = $arr[$j];
$count++;
}
}
if($count == $size){
$r_arr[] = $t_arr;
}
}
return $r_arr;
}
$pl = pl(array(1,2,3,4,5,6,7),5);
var_dump($pl);
//Algoritmo ricorsivo
function f($n){
if($n == 1 || $n == 0){
return 1;
return $n*f($n-1);
}
echo f(5);
}
}
//Eseguire la scansione della directory
function iteral($path){
$filearr = array();
foreach (glob($path.'\*') as $file){
if(is_dir($file)){
$filearr = array_merge($filearr, iteral($file));
else{
}
$filearr[] = $file;
}
}
return $filearr;
}
var_dump(iteral('d:\www\test'));
Per coloro che sono interessati a ulteriori contenuti relativi a PHP, è possibile consultare le sezioni speciali di questo sito: 'Corso di strutture dati e algoritmi PHP', 'Riassunto degli algoritmi di progettazione del programma PHP', 'Riassunto dei metodi di crittografia PHP', 'Riassunto delle tecniche di codifica e decodifica PHP', 'Corso di introduzione alla progettazione orientata agli oggetti PHP', 'Riassunto delle tecniche di calcolo matematico PHP', 'Manuale completo delle operazioni sugli array (Array) PHP', 'Riassunto dell'uso delle stringhe (string) PHP', 'Riassunto dell'uso delle espressioni regolari PHP', 'Riassunto delle tecniche di operazioni sui database più comuni PHP'.
Spero che il contenuto di questo articolo possa essere utile per la progettazione di programmi PHP.
Dichiarazione: il contenuto di questo articolo è stato prelevato da Internet, di proprietà del rispettivo autore. Il contenuto è stato fornito volontariamente dagli utenti di Internet e caricato autonomamente. Questo sito non detiene alcun diritto di proprietà, non ha effettuato alcuna modifica manuale e non assume alcuna responsabilità legale. Se si trovano contenuti sospetti di violazione del copyright, si prega di inviare una e-mail a notice#oldtoolbag.com (sostituire # con @) per segnalare il problema, fornendo prove pertinenti. Una volta verificata la veridicità, il sito rimuoverà immediatamente i contenuti sospetti di violazione del copyright.