الخوارزميات للمحترفين أمثلة على خوارزميات لحل مشكلات بسيطة

نستعرض في هذه المقالة ثلاث خوارزميات بسيطة، وهي خوارزمية الحقيبة، وخوارزمية أخرى للتحقق من الألفاظ المقلوبة وخوارزمية لطباعة مثلث باسكال.

مشكلة الحقيبة Knapsack Problem

في مشكلة الحقيبة، نفترض أنّ لدينا مجموعة من العناصر، لكل منها قيمة ووزن، وعليك اختيار مجموعة من تلك العناصر بحيث يكون وزنها الإجمالي أقلّ من حدّ معيّن أو يساويه، وتكون قيمتها الإجمالية أكبر ما يمكن.

هذا مثال توضيحي لحل مشكلة الحقيبة:

• v: مصفوفة تمثّل قيم العناصر.
• w: مصفوفة تمثّل أوزان العناصر.
• n: مصفوفة تحتوي العناصر غير المكررة.
• W: تمثّل سعة Capacity الحقيبة.

for j from 0 to W do:
   m[0, j] := 0
for i from 1 to n do:
   for j from 0 to W do:
       if w[i] > j then:
           m[i, j] := m[i-1, j]
       else:
           m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

هذا تطبيق implementation للشيفرة السالفة بلغة بايثون:

def knapSack(W, wt, val, n):
   K = [[0 for x in range(W+1)] for x in range(n+1)]
   for i in range(n+1):
       for w in range(W+1):
           if i==0 or w==0:
               K[i][w] = 0
           elif wt[i-1] <= w:
               K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
           else:
               K[i][w] = K[i-1][w]
   return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

احفظ هذه الشيفرة في ملفّ يُسمّى knapSack.py، ثمّ نفّذه على النحو التالي:

$ python knapSack.py
220

التعقيد الزمني: يساوي تعقيد الشيفرة السابقة ‎O(nW)‎، حيث يمثّل n عدد العناصر، وتمثّل W سعة الحقيبة.

هذا تطبيق آخر بلغة C#‎‎:

public class KnapsackProblem
{
   private static int Knapsack(int w, int[] weight, int[] value, int n)
   {
       int i;
       int[,] k = new int[n + 1, w + 1];
       for (i = 0; i <= n; i++)
       {
           int b;
           for (b = 0; b <= w; b++)
           {
               if (i==0 || b==0)
               {
                   k[i, b] = 0;
               }
               else if (weight[i - 1] <= b)
               {
                   k[i, b] = Math.Max(value[i - 1] + k[i - 1, b - weight[i - 1]], k[i - 1, b]);
               }
               else
               {
                   k[i, b] = k[i - 1, b];
               }
           }
       }
       return k[n, w];
   }
   public static int Main(int nItems, int[] weights, int[] values)
   {
       int n = values.Length;
       return Knapsack(nItems, weights, values, n);
   }
}

التحقق من العبارات المقلوبة

لتكن س سلسلة نصية، ولتكن ع سلسلة نصية أخرى نحصل عليها بتغيير مواضع بعض حروف س، فتُسمّى السلسلة النصية ع لفظًا مقلوبًا anagram للسلسلة النصية س. مثلًا، تعدّ الكلمتان لكم و كلم لفظان مقلوبان للكلمة ملك. بتعبير آخر، تكون سلسلة نصية لفظًا مقلوبًا من سلسلة نصية أخرى إن كانت السلسِلتان مؤلّفتان من مجموعة الحروف نفسها، وبالتردّدات نفسها.

لتكن str1 و str2 سلسلتين نصيتين، نريد أن نتحقّق ممّا إذا كانت str2 لفضًا مقلوبًا للسلسلة str1. هذه خطوات الخوارزمية التي سنعتمدها:

1. أنشئ قاموسًا hashMap مفاتيحه تساوي حروف str1 (غير مكرّرة)، وقيمة كل مفتاح (أو حرف) في القاموس تساوي عدد مرّات تكرار ذلك الحرف.
2. امرر على كل حرف من حروف str2 وتحقّق من أنّه موجود في القاموس hashMap.
   • إن وجدت الحرف في القاموس فانقص قيمته في القاموس بواحد.
   • إن لم تجد الحرف في القاموس فذلك يدل على أنّه غير موجود في السلسلة النصية str1، وإذن لا يمكن أن تكون str2 لفضًا مقلوبًا للسلسلة str1. تنتهي الخوارزمية هنا وتعيد false.
3. إن كانت جميع قيم مفاتيح القاموس hashMap تساوي الصفر بعد المرور على كل حروف str2، فذلك يدل على أنّ str2 لفظًا مقلوبًا للسلسلة str1، نعيد إذن true. خلاف ذلك نعيد false.

انظر المثال التالي:

let str1 = 'stackoverflow';
let str2 = 'flowerovstack';

هاتان السلسِلتان النصيتَان مُتقالبتان. وهذا هو قاموس الترددات خاصّتها:

hashMap = {
    s : 1,
    t : 1,
    a : 1,
    c : 1,
    k : 1,
    o : 2,
    v : 1,
    e : 1,
    r : 1,
    f : 1,
    l : 1,
    w : 1
}

لاحظ أنّ القيمة المرتبطة بالمفتاح o تساوي 2، ذلك أنّ o تكرّرت مرّتين في السلسلة النصية.

سنمرّ على كل حرف من حروف str2 لنتحقق من أنّه موجود في hashMap، فإن كان كذلك نقصنا قيمة الحرف في hashMap واحدًا، وإلا أعدنا false دلالة على أنّ str2 ليست لفظًا مقلوبًا عن str1.

hashMap = {
    s : 0,
    t : 0,
    a : 0,
    c : 0,
    k : 0,
    o : 0,
    v : 0,
    e : 0,
    r : 0,
    f : 0,
    l : 0,
    w : 0
}

نمرّ الآن على كل قيم hashMap ونتحقق من أنّها تساوي جميعًا 0. وبما أن جميع قيم hashMap تساوي 0 في المثال الذي ضربناه آنفًا، فإنّ str2 لفظٌ مقلوب عن str1.

إليك مثال توضيحي لخوارزمية التحقق من الألفاظ المقلوبة:

(function(){
   var hashMap = {};

   function isAnagram (str1, str2) {

       if(str1.length !== str2.length){
           return false;
       }

       createStr1HashMap(str1);

       var valueExist = createStr2HashMap(str2);

       return isStringsAnagram(valueExist);
   }

   function createStr1HashMap (str1) {
       [].map.call(str1, function(value, index, array){
           hashMap[value] = value in hashMap ?  (hashMap[value] + 1) : 1;
           return value;
       });
   }

   function createStr2HashMap (str2) {
       var valueExist = [].every.call(str2, function(value, index, array){
           if(value in hashMap) {
               hashMap[value] = hashMap[value] - 1;
           }
           return value in hashMap;
       });
       return valueExist;
   }

   function isStringsAnagram (valueExist) {
       if(!valueExist) {
           return valueExist;
       } else {
           var isAnagram;
           for(var i in hashMap) {
               if(hashMap[i] !== 0) {
                   isAnagram = false;
                   break;
               } else {
                   isAnagram = true;
               }
           }

           return isAnagram;
       }
   }

   isAnagram('stackoverflow', 'flowerovstack'); // true
   isAnagram('stackoverflow', 'flowervvstack'); // false
})();

التعقيد الزمني: 3n أو O (n)‎‎.

مثلث باسكال

مثلث باسكال هو منظومة عددية تُرتّب على هيئة مثلث، ولها استخدامات كثيرة في الرياضيات.

هذه شيفرة مكتوبة بلغة C لطباعة مثلث باسكال:

int i, space, rows, k=0, count = 0, count1 = 0;
row=5;
for(i=1; i<=rows; ++i)
{
   for(space=1; space <= rows-i; ++space)
   {
       printf("  ");
       ++count;
   }
   while(k != 2*i-1)
   {
       if (count <= rows-1)
       {
           printf("%d ", i+k);
           ++count;
       }
       else
       {
           ++count1;
           printf("%d ", (i+k-2*count1));
       }
       ++k;
   }
   count1 = count = k = 0;
   printf("\n");
}

الخرج الناتج:

           1
        2 3 2
      3 4 5 4 3
  4 5 6 7 6 5 4
5 6 7 8 9 8 7 6 5

ترجمة -بتصرّف- للفصول 45 و 49 و 50 من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقال السابق: خوارزميات حل المعادلات الرياضية
• المرجع الشامل إلى: تعلم الخوارزميات للمبتدئين
• أمثلة على أشهر خوارزميات المخططات والأشجار
• خوارزميات البحث وآلية عملها
• حل المشكلات وأهميتها في احتراف البرمجة