تصميم الخوارزميات
نصف خطوات الحل بالسودوكود وخرائط التدفق، ونتعرّف على التقسيم والفوز والتراجع.
- تعرّف الخوارزمية وتذكر خصائصها.
- تكتب خوارزمية بالسودوكود لمسألة بسيطة.
- ترسم خريطة تدفق بأشكالها الصحيحة للتسلسل والقرار والتكرار.
- تحوّل خوارزمية إلى خطوات برنامج.
- تشرح فكرة التقسيم والفوز والتراجع وتطبقهما على مثال.
١ما هي الخوارزمية؟
الخوارزمية (Algorithm) مجموعة من الخطوات المرتّبة والواضحة التي تحلّ مشكلة محددة. بعد أن نفكّك المشكلة (الدرس السابق) نكتب خوارزمية تحدد ترتيب تنفيذ المهام.
وصفة الطبخ خوارزمية، وتعليمات تركيب قطعة أثاث خوارزمية، وخطوات سحب النقود من الصرّاف خوارزمية.
| خاصية الخوارزمية الجيدة | معناها |
|---|---|
| واضحة ومحددة | كل خطوة لها معنى واحد لا يحتمل التأويل |
| مرتّبة | الخطوات تُنفَّذ بتسلسل معروف |
| منتهية | تتوقف بعد عدد محدود من الخطوات |
| لها مدخلات ومخرجات | تستقبل بيانات وتنتج نتيجة |
| فعّالة | كل خطوة يمكن تنفيذها فعلًا |
نصف الخوارزمية بطريقتين رئيسيتين: السودوكود (نص منظم) وخريطة التدفق (رسم).
٢السودوكود Pseudocode
السودوكود كتابة خطوات الحل بلغة قريبة من لغة البشر، لكن بصياغة منظمة تشبه البرمجة. لا يُنفَّذ على الحاسب، بل يساعدك على التفكير قبل الكود. هذه الكلمات التي نستخدمها في المقرر:
| بالعربية | بالإنجليزية | الاستخدام |
|---|---|---|
| ابدأ / توقف | START / END | بداية الخوارزمية ونهايتها |
| اقرأ ... وخزنه في | READ / INPUT | استقبال قيمة من المستخدم |
| اطبع | PRINT / OUTPUT | عرض قيمة أو رسالة |
| احسب أو x = ... | SET / ← | إسناد قيمة إلى متغير |
| إذا كان ... وإلا | IF ... ELSE | اتخاذ قرار |
| طالما / كرّر | WHILE / FOR | تكرار خطوات |
مثال: متوسط ثلاثة أعداد
- ابدأ
- اقرأ ثلاثة أعداد وخزنها في a و b و c
- احسب المجموع: sum = a + b + c
- احسب المتوسط: avg = sum / 3
- اطبع avg
- توقف
- START
- READ a, b, c
- SET sum ← a + b + c
- SET avg ← sum / 3
- PRINT avg
- END
٣خرائط التدفق Flowcharts
خريطة التدفق رسم يوضّح خطوات الخوارزمية بأشكال متفق عليها، تربطها أسهم تبيّن اتجاه التنفيذ.
شكل بيضاوي
متوازي أضلاع: اقرأ أو اطبع
مستطيل: حساب أو إسناد
معيّن: سؤال جوابه نعم أو لا
سهم يحدد اتجاه التنفيذ
دائرة تجمع المسارات
١. التسلسل: متوسط ثلاثة أعداد
٢. القرار: ناجح أم راسب
- ابدأ
- اقرأ الدرجة وخزنها في n
- إذا كان n >= 60 :
- اطبع «ناجح»
- وإلا:
- اطبع «راسب»
- توقف
٣. التكرار: مجموع الأعداد من 1 إلى n
- ابدأ
- اقرأ n
- sum = 0
- i = 1
- طالما i <= n :
- sum = sum + i
- i = i + 1
- اطبع sum
- توقف
لاحظ السهم الراجع إلى المعيّن: هو ما يصنع التكرار. وعندما يصبح الشرط «لا» يخرج التنفيذ من الحلقة.
٤من الخوارزمية إلى البرنامج
بعد أن تكتب الخوارزمية يصبح تحويلها إلى كود عملية ترجمة شبه مباشرة: كل خطوة تقابل سطرًا أو أكثر. قارن الأعمدة الثلاثة لمسألة «زوجي أم فردي»:
السودوكود
- ابدأ
- اقرأ الرقم وخزنه في n
- إذا كان n % 2 == 0 :
- اطبع «زوجي»
- وإلا:
- اطبع «فردي»
- توقف
خريطة التدفق
جافا
Scanner in = new Scanner(System.in);int n = in.nextInt();if (n % 2 == 0) System.out.println("زوجي");else System.out.println("فردي");
٥تقنية التقسيم والفوز Divide and Conquer
فكرتها: قسّم المشكلة إلى أجزاء أصغر من النوع نفسه، حلّ كل جزء، ثم اجمع الحلول. أشهر مثال: البحث عن كلمة في القاموس؛ لا تقرأ الصفحات واحدة واحدة، بل تفتح في المنتصف ثم تستبعد النصف الذي لا يحتوي الكلمة.
جرّب: خمّن الرقم من 1 إلى 100
- ابدأ
- low = 1 ، high = 100
- طالما لم تجد الرقم:
- mid = (low + high) / 2
- إذا كان الرقم السري = mid : اطبع «وجدته» وتوقف
- إذا كان الرقم السري أكبر: low = mid + 1
- وإلا: high = mid - 1
- توقف
في كل خطوة نستبعد نصف الاحتمالات، لذلك لا يحتاج الحاسب أكثر من 7 محاولات لأي رقم من 1 إلى 100، بينما التخمين المتسلسل قد يحتاج 100 محاولة.
٦تقنية التراجع Backtracking
فكرتها: جرّب طريقًا خطوة بخطوة، فإذا وصلت إلى طريق مسدود ارجع إلى آخر نقطة كان فيها خيار آخر، وجرّب الخيار التالي. هكذا يخرج الإنسان من متاهة: يمشي، وإذا اصطدم بجدار عاد وجرّب ممرًا آخر.
جرّب: الخروج من المتاهة
🟩 الطريق الحالي · 🟥 طريق مسدود تراجعنا عنه · 🟨 الموقع الحالي
- ابدأ من الخانة S
- كرّر حتى تصل إلى G:
- إذا وُجدت خانة مجاورة مفتوحة لم تزرها: تحرّك إليها وأضفها إلى الطريق
- وإلا: علّم الخانة الحالية طريقًا مسدودًا وارجع خطوة إلى الخلف
- اطبع الطريق
- توقف
توقّع وتحقّق
أي شكل في خريطة التدفق يمثل «اقرأ العدد»؟
أي شكل يمثل سؤالًا جوابه نعم أو لا؟
خوارزمية لا تتوقف أبدًا تفتقد خاصية:
البحث عن كلمة في قاموس بفتحه من المنتصف ثم استبعاد النصف مثال على:
عند الوصول إلى طريق مسدود في المتاهة، تقنية التراجع:
الخلاصة
- الخوارزمية خطوات مرتبة وواضحة ومنتهية تحل مشكلة.
- السودوكود وصف نصي منظم، وخريطة التدفق وصف بالرسم.
- أشكال خريطة التدفق: البيضاوي للبداية، ومتوازي الأضلاع للإدخال والإخراج، والمستطيل للمعالجة، والمعيّن للقرار.
- التقسيم والفوز يقسّم المشكلة إلى أجزاء أصغر من النوع نفسه.
- التراجع يجرّب الطريق، ويرجع عند الطريق المسدود ليجرّب غيره.