PHP 클래식 알고리즘 모음

不言
풀어 주다: 2023-03-23 20:04:01
원래의
1369명이 탐색했습니다.

이 글은 주로 PHP 고전 알고리즘 모음을 소개하고, 다양한 공통 알고리즘 원리와 정렬, 검색, 순회, 연산 등의 구현 기술을 포함하여 다양한 공통 알고리즘을 정리했습니다. 도움이 필요한 친구들이 참고할 수 있습니다.

이 글은 예 PHP 클래식 알고리즘. 참고를 위해 모두와 공유합니다. 자세한 내용은 다음과 같습니다.

1. 먼저 재미삼아 마름모를 그려보겠습니다. 많은 사람들이 C를 배울 때 책에서 그렸습니다. PHP로 그려서 절반을 그려보겠습니다. .

아이디어: 한 번은 여러 줄에 대해 한 번, 그 다음에는 공백과 별표를 위해 한 번.


<?php
for($i=0;$i<=3;$i++){
  echo str_repeat(" ",3-$i);
  echo str_repeat("*",$i*2+1);
  echo &#39;<br/>&#39;;
}
로그인 후 복사


2. C의 기본 알고리즘인 버블 정렬은 숫자 집합을 작은 것부터 큰 것 순으로 정렬합니다.

생각하기: 이 질문은 가장 작은 것부터 큰 것 순으로 순위가 매겨집니다. 첫 번째 라운드는 두 번째로 작고, 세 번째 라운드는 세 번째로 작습니다...


<?php
$arr = array(1,3,5,32,756,2,6);
$len = count($arr);
for ($i=0;$i<$len-1;$i++){
  for ($j=$i+1;$j<$len;$j++){
    if($arr[$i]>$arr[$j]){//从小到大
      $p = $arr[$i];
      $arr[$i] = $arr[$j];
      $arr[$j]= $p;
    }
  }
}
var_dump($arr);
로그인 후 복사


3. PHP로 작성된 양희삼각형.

아이디어: 각 행의 첫 번째 숫자와 마지막 숫자는 1이며, 가운데는 첫 번째 숫자와 왼쪽 행의 합이 2차원 배열로 저장되는 알고리즘입니다. 차원 배열을 사용하는 것도 구현할 수 있으며 출력은 한 줄씩 표시됩니다. 관심이 있으면 작성하고 재생할 수 있습니다.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1


<?php
//每行的第一个和最后一个都为1,写了6行
 for($i=0; $i<6; $i++) {
  $a[$i][0]=1;
  $a[$i][$i]=1;
 }
//出除了第一位和最后一位的值,保存在数组中
 for($i=2; $i<6; $i++) {
  for($j=1; $j<$i; $j++) {
   $a[$i][$j] = $a[$i-1][$j-1]+$a[$i-1][$j];
  }
 }
//打印
 for($i=0; $i<6; $i++){
  for($j=0; $j<=$i; $j++) {
  echo $a[$i][$j].&#39; &#39;;
  }
  echo &#39;<br/>&#39;;
 }
로그인 후 복사


4. 원래 정렬 방법을 유지하면서 원래 순서대로 삽입합니다.

아이디어: 삽입하려는 숫자보다 큰 위치를 찾아 교체한 후 다음 숫자를 1씩 뒤로 이동하세요.


<?php
$in = 2;
$arr = array(1,1,1,3,5,7);
$n = count($arr);
//如果要插入的数已经最大,直接打印
if($arr[$n-1] < $in) {
  $arr[$n+1] = $in; print_r($arr);
  }
for($i=0; $i<$n; $i++) {
//找出要插入的位置
  if($arr[$i] >= $in){
    $t1= $arr[$i];
    $arr[$i] = $in;
//把后面的数据后移一位
    for($j=$i+1; $j<$n+1; $j++) {
      $t2 = $arr[$j];
      $arr[$j] = $t1;
      $t1 = $t2;
  }
//打印
  print_r($arr);
  die;
  }
}
로그인 후 복사


5. 숫자 집합을 정렬합니다(빠른 정렬 알고리즘).

아이디어: 한 번의 정렬을 통해 두 부분으로 나눈 다음 두 부분을 재귀적으로 정렬하고 최종적으로 병합합니다.


<?php
function q($array) {
  if (count($array) <= 1) {return $array;}
//以$key为界,分成两个子数组
  $key = $array[0];
  $l = array();
  $r = array();
//分别进行递归排序,然后合成一个数组
  for ($i=1; $i<count($array); $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. 배열에서 필요한 요소를 찾습니다(이진 검색 알고리즘).

아이디어: 배열의 특정 값을 경계로 사용하고 끝까지 재귀적으로 검색하세요.


<?php
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(&#39;Not have...&#39;);
}
//test
$array = array(2,4,3,5);
$n = count($array);
$r = find($array,0,$n,5)
로그인 후 복사


7. array_merge() 없이 여러 배열을 병합합니다. 질문은 포럼에서 나왔습니다.

아이디어: 각 배열을 순회하고 새 배열을 다시 구성합니다.


<?php
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<count($a[$i]); $j++){
        $r[] = $a[$i][$j];
      }
    } else {
      die(&#39;Not a array!&#39;);
    }
  }
  return $r;
}
//test
print_r(t(range(1,4),range(1,4),range(1,4)));
echo &#39;<br/>&#39;;
$a = array_merge(range(1,4),range(1,4),range(1,4));
print_r($a);
로그인 후 복사


8. 소의 해에 소 한 마리를 구하라 : 4세가 되면 새끼를 낳을 수 있는 소가 있는데, 1년에 한 마리씩 새끼를 낳는 것은 다 똑같다. 소는 15세가 되면 불임이 되어 더 이상 아이를 가질 수 없게 됩니다. 20세가 되면 죽을 것입니다. n년 후에는 소가 몇 마리나 있을지 물어보십시오. (포럼에서)


<?php
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);
로그인 후 복사


=======================기타 알고리즘============ ==== ==========

버블 정렬(버블 정렬) — O(n2)


$data = array(3,5,9,32,2,1,2,1,8,5);
dump($data);
BubbleSort($data);
dump($data);
function 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 &#39;<pre class="brush:php;toolbar:false">&#39;;
print_r($d);
echo &#39;
'; }
로그인 후 복사


삽입 정렬 — 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 );
function InsertionSort(& $arr,$n )
{
for( $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 &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($d);echo &#39;
'; }
로그인 후 복사


힐 정렬(쉘 정렬) — 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 &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($d);echo &#39;
'; }
로그인 후 복사


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 &#39;<pre class="brush:php;toolbar:false">&#39;;print_r($data);echo &#39;
'; } 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); }
로그인 후 복사


=== === ==========================================

버블링 정렬: 값 교환 쌍으로, 맨 왼쪽에 가장 작은 값이 있고 맨 위에 있는 가장 가벼운 거품과 같습니다. 전체 숫자 열을 가장 왼쪽에 있는 숫자로 한 번 교환합니다. 매번 남은 숫자 중에서 가장 작은 숫자를 얻을 수 있습니다. "팝업된" 숫자는 순서화된 간격을 형성하고 나머지 값은 An을 형성합니다. 순서가 없는 간격이고, 순서가 있는 간격의 각 요소 값은 순서가 없는 간격의 값보다 작습니다.

빠른 정렬: 기본 번호, 왼쪽 및 오른쪽 배열, 재귀 호출, 병합.

삽입 정렬: 정렬 간격이 두 부분으로 나누어져 왼쪽은 순서가 지정되고 오른쪽은 순서가 지정되지 않습니다. 오른쪽 간격에서 첫 번째 요소를 가져와서 이 요소가 가장 오른쪽 간격보다 큰 경우 왼쪽 간격에 삽입합니다. 왼쪽 간격의 요소는 그대로 둡니다. 이 요소가 왼쪽 범위의 가장 오른쪽 요소보다 작으면 가장 오른쪽 요소의 원래 위치에 삽입됩니다. 한 위치 오른쪽으로 이동하면 계산기가 1만큼 줄어들고 이전 요소가 삽입할 요소보다 작아질 때까지 이전 요소와 다시 비교됩니다. 위 단계를 반복합니다.

간격 끝점 값 처리에 주의하세요. 배열의 첫 번째 요소의 첨자는 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 &#39;<hr>&#39;;
function quicksort ($array)
{
$n = count ($array);
if ($n <= 1)
{
return $array;
}
$key = $array[&#39;0&#39;];
$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 &#39;<hr>&#39;;
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
/*
【插 入排序(一维数组)】
【基本思想】:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素 全部插入完为止。
【示例】:
[初始关键字] [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;
}
/*
【选择排序(一维数组)】
【基 本思想】:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
【示例】:
[初 始关键字] [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第 二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第 四趟排序后 13 27 38 49 [49 97 65 76]
第五趟排序后 13 27 38 49 49 [97 97 76]
第 六趟排序后 13 27 38 49 49 76 [76 97]
第七趟排序后 13 27 38 49 49 76 76 [ 97]
最 后排序结果 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;
}
/*
【冒泡排序(一维数组) 】
【基本思想】:两两比较待排序数据元素的大小,发现两个数据元素的次序 相反时即进行交换,直到没有反序的数据元素为止。
【排序过程】:设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据 轻气泡不能在重气泡之下的原则,
从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是 轻者在上,重者在下为止。
【示例】:
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;
}
/*
【快速排序(一 维数组)】
【基本思想】:在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),
用此基准将当前无序区划分为 左右两个较小的无序区:R[1..I-1]和R[I 1..H],且左边的无序子区中数据元素均小于等于基准元素,
右边的无序子区中数据元素均大 于等于基准元素,而基准X则位于最终排序的位置上,即R[1..I-1]≤X.Key≤R[I 1..H](1≤I≤H),
当R[1..I-1] 和R[I 1..H]均非空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。
【示例】:
初始关键字 [49 38 65 97 76 13 27 49]
第一次交换后 [27 38 65 97 76 13 49 49]
第二次交换后 [27 38 49 97 76 13 65 49]
J向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49]
I向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49]
J向左扫描 [27 38 13 49 76 97 65 49]
(一次划分过程)
初始关键字 [49 38 65 97 76 13 27 49]
一趟排序之后 [27 38 13] 49 [76 97 65 49]
二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]
三趟排序之后 13 27 38 49 49 [65]76 97
最后的排序结果 13 27 38 49 49 65 76 97
各趟排序之后的状态
*/
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);
}
/*打印数组全部内容*/
function display_arr($array){
$len = count($array);
for($i = 0; $i<$len; $i++){
  echo $array[$i].&#39; &#39;;
}
echo &#39;<br />&#39;;
}
/*
几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素:
(1) 待排序的元素数目n;
(2) 元素本身信息量的大小;
(3) 关键字的结构及其分布情况;
(4) 语言工具的条件,辅助空间的大小等。
2. 小结:
(1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较 好。
(2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。
(3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件的n个关 键字随机分布时,任何借助于"比较"的排序算法,至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为存储结构。
*/
/*排序测试*/
$a = array(&#39;12&#39;,&#39;4&#39;,&#39;16&#39;,&#39;8&#39;,&#39;13&#39;,&#39;20&#39;,&#39;5&#39;,&#39;32&#39;);
echo &#39;The result of insert sort:&#39;;
$insert_a = insert_sort($a);
display_arr($insert_a);
echo &#39;The result of select sort:&#39;;
$select_a = select_sort($a);
display_arr($select_a);
echo &#39;The result of bubble sort:&#39;;
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo &#39;The result of bubble sort:&#39;;
$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);
//递归算法
//阶乘
function f($n){
  if($n == 1 || $n == 0){
    return 1;
  }else{
    return $n*f($n-1);
  }
}
echo f(5);
//遍历目录
function iteral($path){
  $filearr = array();
  foreach (glob($path.&#39;\*&#39;) as $file){
    if(is_dir($file)){
      $filearr = array_merge($filearr,iteral($file));
    }else{
      $filearr[] = $file;
    }
  }
  return $filearr;
}
var_dump(iteral(&#39;d:\www\test&#39;));
로그인 후 복사

관련 추천:

php 클래식 알고리즘 예제 분석

다리를 건너는 PHP 클래식 알고리즘

위 내용은 PHP 클래식 알고리즘 모음의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!