📘 شرح الدرس الوحدة 4: الدوال واستراتيجيات الحل · الدرس 10 من 17
الدرس 10
📋 في الخطة: الوحدة 3. استراتيجيات حل المشكلات

استراتيجيات حل المشكلات

الحل الجشع، والبرمجة الديناميكية، والبحث والترتيب: كيف نختار الاستراتيجية المناسبة لطبيعة المشكلة؟

int[] grades 90[0]85[1]70[2]100[3] length = 4 · آخر فهرس = 3
بعد هذا الدرس ستستطيع أن:
  • تستخدم مصفوفة بسيطة لحفظ مجموعة قيم والمرور عليها.
  • تطبّق البحث الخطي والبحث الثنائي، وتميّز متى يُستخدم كل منهما.
  • ترتّب مجموعة قيم بالترتيب الفقاعي.
  • تحل مسألة بالنهج الجشع وتعرف حدوده.
  • تشرح فكرة البرمجة الديناميكية وتطبقها على مثال.
  • تختار الاستراتيجية المناسبة لطبيعة المشكلة.

١لماذا نحتاج استراتيجيات؟

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

نوع المشكلةمثالالاستراتيجية المناسبة
إيجاد عنصرهل اسم الطالب موجود في القائمة؟البحث
ترتيبرتّب الدرجات من الأعلى إلى الأدنىالترتيب
أفضل اختيار في كل خطوةأقل عدد من العملات لدفع مبلغالنهج الجشع
مسألة تتكرر أجزاؤهاعدد طرق صعود درجالبرمجة الديناميكية

٢تمهيد: حفظ عدة قيم في متغير واحد

البحث والترتيب يعملان على مجموعة من القيم، لذلك نحتاج طريقة لحفظ عدة قيم معًا. في جافا نستخدم المصفوفة Array: متغير واحد فيه عدة خانات مرقّمة تبدأ من 0. نكتفي هنا بما نحتاجه فقط:

snippet
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] + " ");
Output – JavaApplication (run)×
run:
70
88
4
70 95 60 88
BUILD SUCCESSFUL (total time: 0 seconds)
الكتابةالمعنى
int[] a = {5, 2, 9};إنشاء مصفوفة بثلاث قيم
a[i]القيمة في الخانة رقم i
a.lengthعدد الخانات
for (int i = 0; i < a.length; i++)المرور على كل الخانات

٣البحث: الخطي والثنائي

١. البحث الخطي Linear Search

نمرّ على العناصر واحدًا واحدًا من البداية حتى نجد المطلوب أو تنتهي المصفوفة. بسيط ويعمل مع أي مصفوفة، مرتّبة أو غير مرتّبة.

Main.java
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));    }}
Output – JavaApplication (run)×
run:
2
-1
BUILD SUCCESSFUL (total time: 0 seconds)

٢. البحث الثنائي Binary Search

هو تطبيق التقسيم والفوز الذي جرّبناه في لعبة التخمين: ننظر إلى العنصر الأوسط، فإن كان المطلوب أكبر نكمل في النصف الأيمن فقط، وإلا ففي النصف الأيسر. شرطه: أن تكون المصفوفة مرتّبة.

Main.java
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));    }}
Output – JavaApplication (run)×
run:
نفحص الخانة 4 = 34
نفحص الخانة 7 = 66
الموقع: 7
BUILD SUCCESSFUL (total time: 0 seconds)
البحث الخطيالبحث الثنائي
الفكرةعنصرًا عنصرًانستبعد النصف في كل خطوة
يتطلب ترتيبًا؟لانعم
أقصى عدد مقارنات لـ 1000 عنصر100010 فقط

٤الترتيب: الترتيب الفقاعي Bubble Sort

نقارن كل عنصرين متجاورين، فإذا كانا بترتيب خاطئ نبدّلهما. بعد كل جولة «تطفو» أكبر قيمة إلى آخر المصفوفة مثل الفقاعة، فنكرّر حتى يصبح كل شيء مرتّبًا.

شاهد الترتيب خطوة بخطوة

Main.java
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();        }    }}
Output – JavaApplication (run)×
run:
بعد الجولة 1: 1 4 2 5 8
بعد الجولة 2: 1 2 4 5 8
بعد الجولة 3: 1 2 4 5 8
بعد الجولة 4: 1 2 4 5 8
BUILD SUCCESSFUL (total time: 0 seconds)

٥النهج الجشع Greedy

في كل خطوة نأخذ أفضل اختيار متاح الآن دون التفكير في المستقبل، على أمل أن يقودنا ذلك إلى أفضل حل كلّي. مثال: أعطِ الباقي 167 ريالًا بأقل عدد من القطع النقدية: نبدأ دائمًا بأكبر فئة ممكنة.

Main.java
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);    }}
Output – JavaApplication (run)×
run:
1 × 100
1 × 50
1 × 10
1 × 5
2 × 1
عدد القطع: 6
BUILD SUCCESSFUL (total time: 0 seconds)

٦البرمجة الديناميكية Dynamic Programming

إذا كانت المشكلة الكبيرة تتكوّن من مشكلات أصغر تتكرر، نحلّ كل مشكلة صغيرة مرة واحدة ونحفظ نتيجتها في جدول، ثم نبني عليها بدل إعادة حسابها.

مثال: صعود الدرج. تستطيع صعود درجة أو درجتين في كل خطوة. بكم طريقة تصعد 6 درجات؟ للوصول إلى الدرجة i إما أن تأتي من i-1 بخطوة واحدة، أو من i-2 بخطوتين، إذن:

ways[i] = ways[i-1] + ways[i-2]

Main.java
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] + " طرق");        }    }}
Output – JavaApplication (run)×
run:
درجات 2: 2 طرق
درجات 3: 3 طرق
درجات 4: 5 طرق
درجات 5: 8 طرق
درجات 6: 13 طرق
BUILD SUCCESSFUL (total time: 0 seconds)
i0123456
ways[i]11235813

٧كيف تختار الاستراتيجية المناسبة؟

اسأل نفسكإن كانت الإجابة نعم
هل أبحث عن عنصر والبيانات مرتّبة؟البحث الثنائي
هل أبحث عن عنصر والبيانات غير مرتّبة؟البحث الخطي، أو رتّب أولًا
هل يمكن تقسيم المشكلة إلى نصفين مستقلين؟التقسيم والفوز
هل الاختيار الأفضل الآن يضمن الأفضل في النهاية؟النهج الجشع
هل أحتاج تجربة احتمالات والتراجع عن الخاطئ منها؟التراجع
هل تتكرر المشكلات الصغيرة نفسها؟البرمجة الديناميكية

توقّع وتحقّق

ما شرط استخدام البحث الثنائي؟

البحث الثنائي يعتمد على الترتيب ليستبعد النصف.

ماذا تعيد linearSearch إذا لم تجد القيمة؟

اصطلحنا على -1 لأنه ليس رقم خانة صحيحًا.

في الترتيب الفقاعي بعد الجولة الأولى، أين تكون أكبر قيمة؟

تطفو أكبر قيمة إلى النهاية.

«خذ أكبر فئة نقدية ممكنة في كل خطوة» مثال على:

اختيار الأفضل الآن هو النهج الجشع.

حفظ نتائج المشكلات الصغيرة في جدول لإعادة استخدامها هو فكرة:

هذا جوهر البرمجة الديناميكية.

الخلاصة

تحدٍّ برمجي: أكبر درجة وموقعها

متوسط

لديك مصفوفة درجات. اكتب دالة تبحث عن أكبر درجة وتعيد رقم خانتها، ثم اطبع الدرجة وموقعها.

المطلوب:
  • اكتب دالة static int maxIndex(int[] a).
  • ابدأ بافتراض أن الخانة 0 هي الأكبر، ثم قارن ببقية الخانات.
  • مع المصفوفة {70, 95, 60, 88} يجب أن يطبع: أكبر درجة 95 في الخانة 1

ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:

Main.java
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);    }}
Output – المطلوب×
أكبر درجة 95 في الخانة 1
💡 تلميح 1
متغير best = 0 يحفظ رقم خانة الأكبر حتى الآن.
💡 تلميح 2
داخل الحلقة: إذا كان a[i] > a[best] فاجعل best = i.

حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.

Main.java
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);    }}
انتقل إلى تقييم الدرسأسئلة الاختيار، وصح وخطأ، وأكمل الفراغات، والأسئلة العملية.ابدأ التقييم ←