استراتيجيات حل المشكلات
الحل الجشع، والبرمجة الديناميكية، والبحث والترتيب: كيف نختار الاستراتيجية المناسبة لطبيعة المشكلة؟
- تستخدم مصفوفة بسيطة لحفظ مجموعة قيم والمرور عليها.
- تطبّق البحث الخطي والبحث الثنائي، وتميّز متى يُستخدم كل منهما.
- ترتّب مجموعة قيم بالترتيب الفقاعي.
- تحل مسألة بالنهج الجشع وتعرف حدوده.
- تشرح فكرة البرمجة الديناميكية وتطبقها على مثال.
- تختار الاستراتيجية المناسبة لطبيعة المشكلة.
١لماذا نحتاج استراتيجيات؟
تعلّمنا في الدرس الثاني أن نصمّم الخوارزمية، وتعرّفنا على التقسيم والفوز والتراجع. لكن بعض أنواع المشكلات تتكرر كثيرًا، ولها طرق حلّ معروفة مجرّبة تُسمّى الاستراتيجيات. عندما تعرفها تختصر وقت التفكير، وتختار الحل الأسرع.
| نوع المشكلة | مثال | الاستراتيجية المناسبة |
|---|---|---|
| إيجاد عنصر | هل اسم الطالب موجود في القائمة؟ | البحث |
| ترتيب | رتّب الدرجات من الأعلى إلى الأدنى | الترتيب |
| أفضل اختيار في كل خطوة | أقل عدد من العملات لدفع مبلغ | النهج الجشع |
| مسألة تتكرر أجزاؤها | عدد طرق صعود درج | البرمجة الديناميكية |
٢تمهيد: حفظ عدة قيم في متغير واحد
البحث والترتيب يعملان على مجموعة من القيم، لذلك نحتاج طريقة لحفظ عدة قيم معًا. في جافا نستخدم المصفوفة Array: متغير واحد فيه عدة خانات مرقّمة تبدأ من 0. نكتفي هنا بما نحتاجه فقط:
int[] marks = {70, 95, 60, 88};System.out.println(marks[0]); // الخانة الأولىSystem.out.println(marks[3]); // الخانة الرابعةSystem.out.println(marks.length); // عدد الخاناتfor (int i = 0; i < marks.length; i++) System.out.print(marks[i] + " ");
| الكتابة | المعنى |
|---|---|
int[] a = {5, 2, 9}; | إنشاء مصفوفة بثلاث قيم |
a[i] | القيمة في الخانة رقم i |
a.length | عدد الخانات |
for (int i = 0; i < a.length; i++) | المرور على كل الخانات |
٣البحث: الخطي والثنائي
١. البحث الخطي Linear Search
نمرّ على العناصر واحدًا واحدًا من البداية حتى نجد المطلوب أو تنتهي المصفوفة. بسيط ويعمل مع أي مصفوفة، مرتّبة أو غير مرتّبة.
public class Main { static int linearSearch(int[] a, int key) { for (int i = 0; i < a.length; i++) { if (a[i] == key) return i; } return -1; } public static void main(String[] args) { int[] ids = {105, 230, 318, 402, 517}; System.out.println(linearSearch(ids, 318)); System.out.println(linearSearch(ids, 999)); }}
٢. البحث الثنائي Binary Search
هو تطبيق التقسيم والفوز الذي جرّبناه في لعبة التخمين: ننظر إلى العنصر الأوسط، فإن كان المطلوب أكبر نكمل في النصف الأيمن فقط، وإلا ففي النصف الأيسر. شرطه: أن تكون المصفوفة مرتّبة.
public class Main { static int binarySearch(int[] a, int key) { int low = 0, high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; System.out.println("نفحص الخانة " + mid + " = " + a[mid]); if (a[mid] == key) return mid; else if (a[mid] < key) low = mid + 1; else high = mid - 1; } return -1; } public static void main(String[] args) { int[] a = {3, 8, 15, 21, 34, 47, 52, 66, 79, 90}; System.out.println("الموقع: " + binarySearch(a, 66)); }}
| البحث الخطي | البحث الثنائي | |
|---|---|---|
| الفكرة | عنصرًا عنصرًا | نستبعد النصف في كل خطوة |
| يتطلب ترتيبًا؟ | لا | نعم |
| أقصى عدد مقارنات لـ 1000 عنصر | 1000 | 10 فقط |
٤الترتيب: الترتيب الفقاعي Bubble Sort
نقارن كل عنصرين متجاورين، فإذا كانا بترتيب خاطئ نبدّلهما. بعد كل جولة «تطفو» أكبر قيمة إلى آخر المصفوفة مثل الفقاعة، فنكرّر حتى يصبح كل شيء مرتّبًا.
public class Main { public static void main(String[] args) { int[] a = {5, 1, 4, 2, 8}; for (int pass = 1; pass < a.length; pass++) { for (int i = 0; i < a.length - pass; i++) { if (a[i] > a[i + 1]) { // جاران بترتيب خاطئ؟ int temp = a[i]; // نبدّلهما a[i] = a[i + 1]; a[i + 1] = temp; } } System.out.print("بعد الجولة " + pass + ": "); for (int x : a) System.out.print(x + " "); System.out.println(); } }}
٥النهج الجشع Greedy
في كل خطوة نأخذ أفضل اختيار متاح الآن دون التفكير في المستقبل، على أمل أن يقودنا ذلك إلى أفضل حل كلّي. مثال: أعطِ الباقي 167 ريالًا بأقل عدد من القطع النقدية: نبدأ دائمًا بأكبر فئة ممكنة.
public class Main { public static void main(String[] args) { int[] coins = {100, 50, 10, 5, 1}; int amount = 167; int count = 0; for (int i = 0; i < coins.length; i++) { int k = amount / coins[i]; // أكبر عدد ممكن من هذه الفئة if (k > 0) { System.out.println(k + " × " + coins[i]); amount = amount - k * coins[i]; count = count + k; } } System.out.println("عدد القطع: " + count); }}
٦البرمجة الديناميكية Dynamic Programming
إذا كانت المشكلة الكبيرة تتكوّن من مشكلات أصغر تتكرر، نحلّ كل مشكلة صغيرة مرة واحدة ونحفظ نتيجتها في جدول، ثم نبني عليها بدل إعادة حسابها.
مثال: صعود الدرج. تستطيع صعود درجة أو درجتين في كل خطوة. بكم طريقة تصعد 6 درجات؟ للوصول إلى الدرجة i إما أن تأتي من i-1 بخطوة واحدة، أو من i-2 بخطوتين، إذن:
ways[i] = ways[i-1] + ways[i-2]
public class Main { public static void main(String[] args) { int n = 6; int[] ways = new int[n + 1]; ways[0] = 1; // الوقوف أسفل الدرج: طريقة واحدة ways[1] = 1; // درجة واحدة: طريقة واحدة for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // نستفيد من نتائج سابقة محفوظة System.out.println("درجات " + i + ": " + ways[i] + " طرق"); } }}
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| ways[i] | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
٧كيف تختار الاستراتيجية المناسبة؟
| اسأل نفسك | إن كانت الإجابة نعم |
|---|---|
| هل أبحث عن عنصر والبيانات مرتّبة؟ | البحث الثنائي |
| هل أبحث عن عنصر والبيانات غير مرتّبة؟ | البحث الخطي، أو رتّب أولًا |
| هل يمكن تقسيم المشكلة إلى نصفين مستقلين؟ | التقسيم والفوز |
| هل الاختيار الأفضل الآن يضمن الأفضل في النهاية؟ | النهج الجشع |
| هل أحتاج تجربة احتمالات والتراجع عن الخاطئ منها؟ | التراجع |
| هل تتكرر المشكلات الصغيرة نفسها؟ | البرمجة الديناميكية |
توقّع وتحقّق
ما شرط استخدام البحث الثنائي؟
ماذا تعيد linearSearch إذا لم تجد القيمة؟
في الترتيب الفقاعي بعد الجولة الأولى، أين تكون أكبر قيمة؟
«خذ أكبر فئة نقدية ممكنة في كل خطوة» مثال على:
حفظ نتائج المشكلات الصغيرة في جدول لإعادة استخدامها هو فكرة:
الخلاصة
- المصفوفة متغير بعدة خانات مرقّمة من 0، وطولها length.
- البحث الخطي يفحص كل عنصر، والثنائي يستبعد النصف لكنه يتطلب ترتيبًا.
- الترتيب الفقاعي يبدّل الجيران المعكوسين حتى تكتمل المصفوفة.
- الجشع يختار الأفضل الآن، وقد لا يعطي الأفضل دائمًا.
- البرمجة الديناميكية تحفظ نتائج المشكلات الصغيرة المتكررة لتبني عليها.
تحدٍّ برمجي: أكبر درجة وموقعها
متوسطلديك مصفوفة درجات. اكتب دالة تبحث عن أكبر درجة وتعيد رقم خانتها، ثم اطبع الدرجة وموقعها.
- اكتب دالة static int maxIndex(int[] a).
- ابدأ بافتراض أن الخانة 0 هي الأكبر، ثم قارن ببقية الخانات.
- مع المصفوفة {70, 95, 60, 88} يجب أن يطبع: أكبر درجة 95 في الخانة 1
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
public class Main { static int maxIndex(int[] a) { // اكتب الحل هنا return 0; } public static void main(String[] args) { int[] marks = {70, 95, 60, 88}; int k = maxIndex(marks); System.out.println("أكبر درجة " + marks[k] + " في الخانة " + k); }}
💡 تلميح 1
💡 تلميح 2
حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
public class Main { static int maxIndex(int[] a) { int best = 0; for (int i = 1; i < a.length; i++) if (a[i] > a[best]) best = i; return best; } public static void main(String[] args) { int[] marks = {70, 95, 60, 88}; int k = maxIndex(marks); System.out.println("أكبر درجة " + marks[k] + " في الخانة " + k); }}