نستعرض في هذه المقالة ثلاث خوارزميات بسيطة، وهي خوارزمية الحقيبة، وخوارزمية أخرى للتحقق من الألفاظ المقلوبة وخوارزمية لطباعة مثلث باسكال.
مشكلة الحقيبة 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
. هذه خطوات الخوارزمية التي سنعتمدها:
-
أنشئ قاموسًا
hashMap
مفاتيحه تساوي حروفstr1
(غير مكرّرة)، وقيمة كل مفتاح (أو حرف) في القاموس تساوي عدد مرّات تكرار ذلك الحرف. -
امرر على كل حرف من حروف
str2
وتحقّق من أنّه موجود في القاموسhashMap
.- إن وجدت الحرف في القاموس فانقص قيمته في القاموس بواحد.
-
إن لم تجد الحرف في القاموس فذلك يدل على أنّه غير موجود في السلسلة النصية
str1
، وإذن لا يمكن أن تكونstr2
لفضًا مقلوبًا للسلسلةstr1
. تنتهي الخوارزمية هنا وتعيدfalse
.
-
إن كانت جميع قيم مفاتيح القاموس
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.
أفضل التعليقات
لا توجد أية تعليقات بعد
انضم إلى النقاش
يمكنك أن تنشر الآن وتسجل لاحقًا. إذا كان لديك حساب، فسجل الدخول الآن لتنشر باسم حسابك.