مجموعة من الألغوريثمات الكلاسيكية PHP [مجموعة مفضلة]

هذا المقال جمع أمثلة على خوارزميات PHP الكلاسيكية. يُشارك مع الجميع لتقديم الأفكار، كالتالي:

1、لنبدأ ب رسم شكل مثلث، يرسمه الكثير من الناس في الكتب عند تعلم C، لنرسمه باستخدام PHP، ونحن في منتصف الطريق.

الفكرة: كم عدد الأسطر التي تدور فيها الفوريت، ثم تدور فيها الفراغات والنجوم في الداخل.

<?php
لـ ($الـi=0;الـi<=3;الـi++){
  echo str_repeat(" ",3-$الـi);
  echo str_repeat("*",$الـi*2+1);
  echo '<br/>';
}

2、ترتيب الفقاعات، خوارزمية أساسية في C، ترتب مجموعة من الأرقام من الأصغر إلى الأكبر.

الفكرة: هذا المسابقة من الأصغر إلى الأكبر، الجولة الأولى ترتب الأصغر، الجولة الثانية ترتب الثاني الأصغر، الجولة الثالثة ترتب الثالث الأصغر، و هكذا ...

<?php
$الـarr = array(1,3,5,32,756,2,6);
$len = count($arr);
لـ (الـ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，没有变化，中间是前排一位与左边一排的和，这种算法是用一个二维数组保存，另外有种算法用一维数组也可以实现，一行 一行的输出，有兴趣去写着玩下。

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].' ';
  }
  echo '<br/>';
 }

4、在一组数中，要求插入一个数，按其原来顺序插入，维护原来排序方式。

思路：找到比要插入数大的那个位置，替换，然后把后面的数后移一位。

<?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) {
  إذا (count($array) <= 1) {return $array;}
//تقسيم إلى جزأين باستخدام $key كحد
  $key = $array[0];
  $l = array();
  $r = array();
//تقوم بترتيب مرة أخرى بشكل متكرر، ثم تدمج في مصفوفة واحدة
  للحصول على ($i=1; $i<count($array); $i++) {
  إذا ($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) {
  إذا ($low <= $high) {
  $mid = intval(($low+$high)/2);
    إذا ($array[$mid] == $k) {
    return $mid;
  } آخراً إذا ($k < $array[$mid]) {
    return find($array, $low, $mid-1, $k);
    }
    return find($array, $mid+1, $high, $k);
    }
  }
  die('ليس لدي...');
}
//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);
  للحصول على ($i=0; $i<=$c; $i++) {
    إذا كان (is_array($a[$i])) {
      لـ($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
وظيفة t($n) {
    static $num = 1
    لـ($j=1; $j<=$n; $j++){
        if($j>=4 && $j<15) {$num++;t($n-$j);}
        if($j==20){$num--;}
     }
     return $num;
}
//test
echo t(8);

====================آلات أخرى=========================

ترتيب الفقاعات (bubble sort) — O(n2)

$data = array(3,5,9,32,2,1,2,1,8,5);
dump($data);
BubbleSort($data);
dump($data);
وظيفة BubbleSort(& $arr)
{
$limit = count($arr);
لـ($i=1; $i<$limit; $i++)
{
  لـ($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>';
}

ترتيب إدراجي (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 );
وظيفة InsertionSort(& $arr,$n )
{
لـ( $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>';
}

ترتيب شيل (shell sort) — 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>';
}

كتابة مرتبة سريعة (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
/*
[ترتيب إدراج (مستوى أبعاد واحد)]
[基本思想]：كل مرة يتم إدراج عنصر بيانات غير منظم في الموقع المناسب داخل السلسلة التي تم تنظيمها مسبقًا، مما يضمن أن تكون السلسلة لا تزال منظمًا؛ حتى يتم إدراج جميع عناصر البيانات غير المنظمة.
[مثال]:
[初始关键字] [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 [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].' ';
}
echo '<br />';
}
/*
مقارنة وتحديد خوارزميات الترتيب المختلفة
1. العوامل التي يجب النظر فيها لاختيار طريقة الترتيب:
(1) عدد العناصر المراد ترتيبها n;
(2) حجم المعلومات الموجودة في العنصر;
(3) بنية المفتاح وتوزيعه;
(4) شروط الأدوات اللغوية، حجم المساحة الإضافية، وما إلى ذلك.
2. ملخص:
(1) إذا كان n صغيرًا (n <= 50)، يمكن استخدام الترتيب بالطرح أو الترتيب بالاختيار المباشر. نظرًا لأن عملية نقل السجلات المطلوبة في الترتيب بالطرح أكثر من عملية الاختيار المباشر، فإن الترتيب بالاختيار المباشر أفضل عند وجود معلومات كبيرة للسجلات.
(2) إذا كانت حالة البداية للملف مرتبة بشكل أساسي حسب المفتاح، فإن استخدام الترتيب بالطرح أو الترتيب بالتدفق مناسب.
(3) إذا كان n كبيرًا، يجب استخدام طريقة ترتيب ذات معقدية O(nlog2n): الترتيب السريع أو ترتيب الكومة أو الترتيب بالدمج. يُعتبر الترتيب السريع أفضل طريقة ترتيب داخلي مقارن حاليًا.
(4) في أسلوب الترتيب المقارن، بعد كل مقارنة بين حجم مفتاحين، يحدث فقط نوعان من التحولات الممكنة، لذا يمكن استخدام شجرة ثنائية لوصف عملية التقييم المقارن، وبالتالي يمكن إثبات: عند توزيع n من المفاتيح في ملف عشوائي، أي خوارزمية ترتيب تعتمد على "المقارنة" تحتاج على الأقل إلى زمن O(nlog2n).
(5) عندما تكون معلومات السجل نفسه كبيرة، لتجنب استهلاك الكثير من الوقت في تحريك السجلات، يمكن استخدام قائمة الرابط كنموذج التخزين.
*/
/*اختبار الترتيب*/
$a = array('12','4','16','8','13','20','5','32');
echo 'نتيجة ترتيب التدخل:';
$insert_a = insert_sort($a);
display_arr($insert_a);
echo 'نتيجة ترتيب الاختيار:';
$select_a = select_sort($a);
display_arr($select_a);
echo 'نتيجة ترتيب البوليومر:';
$bubble_a = bubble_sort($a);
display_arr($bubble_a);
echo 'نتيجة ترتيب البوليومر:';
$quick_a = quick_sort($a);
display_arr($quick_a);
?>

/**
 * ترتيب التركيبات
 * تستخدم طريقة البايت الثنائي للتركيب، مثل التعبير عن اختيار 5 من 3، يكفي أن تكون 3 من الأماكن الثلاثة كاملة، لذا يمكن الحصول على التركيبات التالية: 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;
  }
    return $n*f($n-1);
  }
}
//استكشاف الدليل
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'));

للقراء المهتمين بمزيد من المعلومات حول PHP، يمكنهم التحقق من موضوعات هذا الموقع: 'تعليم PHP Data Structures and Algorithms'، 'PHP Program Design Algorithms Summary'، 'PHP Encryption Methods Summary'، 'PHP Encoding and Transcoding Operation Skills Summary'، 'PHP Object-Oriented Programming Tutorial'، 'PHP Mathematical Operation Skills Summary'، 'PHP Array (Array) Operation Skills Summary'، 'PHP String (string) Usage Summary'، 'PHP Regular Expression Usage Summary'، و 'PHP Common Database Operation Skills Summary'.

آمل أن يساعدك ما ذكرته في هذا المقال في تصميم برامج PHP الخاصة بك.

بيان: محتوى هذا المقال تم جمعه من الإنترنت، ملكية المحتوى تخص المالك الأصلي، المحتوى تم جمعه من قبل المستخدمين على الإنترنت بشكل تلقائي، هذا الموقع لا يملك حقوق الملكية، لم يتم تعديل المحتوى بشكل يدوي، ولا يتحمل هذا الموقع أي مسؤولية قانونية. إذا اكتشفت محتوى يشتبه في انتهاك حقوق النسخ، فمرحبًا بك في إرسال بريد إلكتروني إلى: notice#oldtoolbag.com (عند إرسال البريد الإلكتروني، يرجى استبدال # بـ @) لتقديم الشكوى، مع تقديم الدليل المتعلق، إذا تم التحقق من ذلك، سيتم حذف المحتوى المزعوم فورًا.