المحاضرة 14 · 100 دقيقة

خوارزميات المصفوفات

كيف نجمع ونبحث ونفرز، وكيف نخزّن جدولًا كاملًا؟

عرض المدرّس

في نهاية هذه المحاضرة ستكون قادرًا على

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

محتويات المحاضرة

المجموع والمعدل: متغير يتراكم أثناء المرور
أكبر عنصر وموقعه: احفظ أفضل ما رأيته حتى الآن
العدّ: عدّاد يزيد حين يتحقق الشرط
البحث الخطي يفحص العناصر بالترتيب ويتوقف عند أول تطابق
العكس في المكان: بدّل الطرفين واقترب من المنتصف
في الإزاحة يحدد اتجاه الحلقة هل تضيع القيم أم تبقى
في كل مرور يطفو الأكبر إلى نهاية الجزء غير المرتب
الحلقة الخارجية تعدّ المرورات والداخلية تقارن الجيران
الصنف Arrays يطبع ويفرز بسطر واحد
copyOf تنشئ صفًا جديدًا وfill تملأ كل الصناديق
== تسأل هل هو الصف نفسه، وArrays.equals تقارن المحتوى
المصفوفة ذات البعدين صفوف وأعمدة، والموقع الأول للصف
مجموع الصف يثبّت الصف، ومجموع العمود يثبّت العمود
جدول علامات مرتب: printf يحدد عرض كل عمود
الصفوف يمكن أن تختلف أطوالها، فاستخدم m[row].length دائمًا
أسئلة المراجعة

الجزء الأول: حلقة واحدة ومتغير أو اثنان

المجموع والمعدل: متغير يتراكم أثناء المرور

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

مجموع العلامات ومعدلها

اضغط «تتبّع سطرًا سطرًا» وراقب sum يكبر. أضف علامة خامسة وتوقّع المعدل الجديد قبل التشغيل.

public class SumAverage {
    public static void main(String[] args) {
        int[] marks = {80, 75, 90, 64};
        int sum = 0;
        for (int mark : marks) {
            sum += mark;
        }
        double average = (double) sum / marks.length;
        System.out.println("Sum: " + sum);
        System.out.println("Average: " + average);
    }
}

الناتج

Sum: 309
Average: 77.25

نسينا `(double)` هذه المرة. ما المعدل المطبوع؟

public class AverageBug {
    public static void main(String[] args) {
        int[] a = {1, 2, 2};
        int sum = 0;
        for (int x : a) {
            sum += x;
        }
        double average = sum / a.length;
        System.out.println(average);
    }
}

أظهر الناتج

الناتج

1.0

لماذا؟ sum وa.length عددان صحيحان، فتكون القسمة صحيحة وتعطي 1، ثم تتحول النتيجة إلى 1.0 عند وضعها في double. فات الأوان: الكسر ضاع قبل الإسناد.

معدل العلامات

اقرأ n ثم n علامة في مصفوفة. اطبع المعدل بمنزلتين عشريتين باستخدام printf.

import java.util.Scanner;

public class AverageMarks {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the marks, then print the average with printf

    }
}

stdin

3
70 80 90

الناتج المتوقع

80.00

تلميح 1

حوّل قبل القسمة: (double) sum / n.

تلميح 2

صيغة الطباعة: "%.2f%n".

الحل

import java.util.Scanner;

public class AverageMarks {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] marks = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            marks[i] = in.nextInt();
            sum += marks[i];
        }
        System.out.printf("%.2f%n", (double) sum / n);
    }
}

أكبر عنصر وموقعه: احفظ أفضل ما رأيته حتى الآن

أكبر علامة وأصغرها مع الموقع

اضغط «تتبّع سطرًا سطرًا» وراقب maxPos يتغير فقط حين نجد قيمة أكبر. لاحظ أن 95 تتكرر ويبقى الموقع الأول. غيّر > إلى >=: ما الموقع الآن؟

public class MaxMin {
    public static void main(String[] args) {
        int[] marks = {72, 95, 60, 95, 81};
        int maxPos = 0;
        int minPos = 0;
        for (int i = 1; i < marks.length; i++) {
            if (marks[i] > marks[maxPos]) {
                maxPos = i;
            }
            if (marks[i] < marks[minPos]) {
                minPos = i;
            }
        }
        System.out.println("Max " + marks[maxPos] + " at " + maxPos);
        System.out.println("Min " + marks[minPos] + " at " + minPos);
    }
}

الناتج

Max 95 at 1
Min 60 at 2

هنا نبدأ `max` من 0 بدل العنصر الأول. ماذا يطبع؟

public class MaxFromZero {
    public static void main(String[] args) {
        int[] temps = {-5, -2, -9};
        int max = 0;
        for (int t : temps) {
            if (t > max) {
                max = t;
            }
        }
        System.out.println(max);
    }
}

أظهر الناتج

الناتج

لماذا؟ لا يوجد عنصر أكبر من 0، فيبقى max على قيمته الأولى، وهذه القيمة ليست في المصفوفة أصلًا. لذلك نبدأ دائمًا من العنصر الأول.

أكبر عنصر وموقعه

اقرأ n ثم n عددًا. اطبع Max: X at position P. إذا تكرر أكبر عنصر فاطبع موقعه الأول.

import java.util.Scanner;

public class MaxPosition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, then find the largest element and its position

    }
}

stdin

5
3 9 2 7 4

الناتج المتوقع

Max: 9 at position 1

تلميح 1

يكفي متغير واحد للموقع، فالقيمة هي a[pos].

تلميح 2

استخدم > لا >=، حتى يبقى الموقع الأول عند التكرار.

الحل

import java.util.Scanner;

public class MaxPosition {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int pos = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] > a[pos]) {
                pos = i;
            }
        }
        System.out.println("Max: " + a[pos] + " at position " + pos);
    }
}

العدّ: عدّاد يزيد حين يتحقق الشرط

كم طالبًا نجح؟

المجموع يضيف القيمة، أما العدّاد فيضيف 1. عدّل البرنامج ليعدّ الراسبين، ثم ليعدّ العلامات الأعلى من 60.

public class CountPassing {
    public static void main(String[] args) {
        int[] marks = {45, 80, 50, 30, 99};
        int count = 0;
        for (int mark : marks) {
            if (mark >= 50) {
                count++;
            }
        }
        System.out.println(count);
    }
}

الناتج

كم مرة تكررت القيمة؟

اقرأ n ثم n عددًا، ثم عددًا target. اطبع عدد مرات ظهور target في المصفوفة.

import java.util.Scanner;

public class CountValue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array and target, then count the matches

    }
}

stdin

6
1 2 3 2 2 5
2

الناتج المتوقع

تلميح 1

العدّاد يبدأ من 0، فإذا لم توجد القيمة طبع 0 دون أي شرط خاص.

الحل

import java.util.Scanner;

public class CountValue {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int target = in.nextInt();
        int count = 0;
        for (int x : a) {
            if (x == target) {
                count++;
            }
        }
        System.out.println(count);
    }
}

البحث الخطي يفحص العناصر بالترتيب ويتوقف عند أول تطابق

دالة تعيد الموقع أو -1

نعيد -1 إذا لم نجد القيمة، لأنه لا يوجد موقع سالب في المصفوفة. تتبّع الاستدعاءين سطرًا سطرًا، ولاحظ كم عنصرًا فحصت الدالة في كل مرة.

public class LinearSearch {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20, 30, 20};
        System.out.println(indexOf(ids, 20));
        System.out.println(indexOf(ids, 99));
    }
}

الناتج

1
-1

خطأ شائع جدًا: أضفنا `else` داخل الحلقة. ماذا يطبع البرنامج؟

public class SearchBug {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            } else {
                return -1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20, 30};
        System.out.println(indexOf(ids, 30));
    }
}

أظهر الناتج

الناتج

-1

لماذا؟ تنتهي الدالة في أول دورة دائمًا، لأن أحد الفرعين يحوي return. فهي لا تفحص إلا العنصر الأول. لا يمكن الحكم بأن القيمة غير موجودة إلا بعد انتهاء الحلقة.

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

public class MissingReturn {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
    }

    public static void main(String[] args) {
        int[] ids = {10, 20};
        System.out.println(indexOf(ids, 20));
    }
}

رسالة المترجمmissing return statement

أظهر التصحيح

public class MissingReturn {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] ids = {10, 20};
        System.out.println(indexOf(ids, 20));
    }
}

الناتج

لماذا؟ يرى المترجم مسارًا تنتهي فيه الحلقة دون تنفيذ return، فيرفض البرنامج. والجواب الصحيح لهذا المسار هو -1.

ابحث عن القيمة

اكتب الدالة static int indexOf(int[] arr, int target). في main اقرأ n ثم n عددًا ثم target. اطبع Found at position P لأول ظهور، أو Not found.

import java.util.Scanner;

public class FindFirst {
    // Write indexOf here

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the input, call indexOf, print the result

    }
}

stdin

4
5 8 2 9
2

الناتج المتوقع

Found at position 2

تلميح 1

return -1; يأتي بعد الحلقة، لا داخلها.

تلميح 2

خزّن ناتج الدالة في متغير، ثم افحصه بـ if.

الحل

import java.util.Scanner;

public class FindFirst {
    static int indexOf(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int pos = indexOf(a, in.nextInt());
        if (pos == -1) {
            System.out.println("Not found");
        } else {
            System.out.println("Found at position " + pos);
        }
    }
}

العكس في المكان: بدّل الطرفين واقترب من المنتصف

موقعان يقترب أحدهما من الآخر

«في المكان» تعني أننا لا ننشئ مصفوفة ثانية. اضغط «تتبّع سطرًا سطرًا» وراقب i وj يقتربان. ماذا يحدث للعنصر الأوسط؟ جرّب مصفوفة من 4 عناصر.

public class ReverseInPlace {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        for (int i = 0; i < a.length / 2; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

الناتج

5 4 3 2 1

نسينا `/ 2` في شرط الحلقة. ماذا يطبع البرنامج؟

public class ReverseTwice {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        for (int i = 0; i < a.length; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3]);
    }
}

أظهر الناتج

الناتج

1 2 3 4

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

دالة تعكس المصفوفة

اكتب الدالة static void reverse(int[] a) التي تعكس المصفوفة في مكانها. في main اقرأ n ثم n عددًا، واستدعِ الدالة، واطبع العناصر في سطر واحد بينها مسافة.

import java.util.Scanner;

public class ReverseMethod {
    // Write reverse here

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, call reverse, print the elements

    }
}

stdin

5
1 2 3 4 5

الناتج المتوقع

5 4 3 2 1

تلميح 1

المسافة بعد آخر عنصر لا تؤثر، فالفحص يتجاهل المسافات في نهاية السطر.

الحل

import java.util.Scanner;

public class ReverseMethod {
    static void reverse(int[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            int j = a.length - 1 - i;
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        reverse(a);
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

في الإزاحة يحدد اتجاه الحلقة هل تضيع القيم أم تبقى

الإزاحة إلى اليسار تنسخ كل عنصر إلى الصندوق الذي قبله. نمشي من اليسار، فنكتب فوق قيمة انتهينا منها. وفي الإزاحة إلى اليمين نمشي من اليمين للسبب نفسه.

الإزاحة إلى اليسار

تتبّع البرنامج وراقب العناصر تتحرك. لاحظ أن الحلقة تتوقف عند a.length - 1، لأنها تقرأ a[i + 1]. عدّلها لتزيح إلى اليمين: ابدأ من الآخر واكتب a[i] = a[i - 1].

public class ShiftLeft {
    public static void main(String[] args) {
        int[] a = {10, 20, 30, 40, 50};
        for (int i = 0; i < a.length - 1; i++) {
            a[i] = a[i + 1];
        }
        a[a.length - 1] = 0;
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

الناتج

20 30 40 50 0

نريد الإزاحة إلى اليمين، لكننا مشينا من اليسار. ماذا يطبع؟

public class ShiftBug {
    public static void main(String[] args) {
        int[] a = {10, 20, 30, 40};
        for (int i = 0; i < a.length - 1; i++) {
            a[i + 1] = a[i];
        }
        System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3]);
    }
}

أظهر الناتج

الناتج

10 10 10 10

لماذا؟ الدورة الأولى تكتب 10 فوق 20 قبل أن ننسخ 20. والدورة التالية تقرأ هذه القيمة الجديدة 10، وهكذا تنتشر حتى النهاية.

التدوير إلى اليسار

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

import java.util.Scanner;

public class RotateLeft {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, rotate it left once, print it

    }
}

stdin

4
1 2 3 4

الناتج المتوقع

2 3 4 1

تلميح 1

احفظ a[0] في متغير قبل أن تزيح، فالإزاحة ستكتب فوقه.

تلميح 2

بعد الحلقة ضع القيمة المحفوظة في a[n - 1].

الحل

import java.util.Scanner;

public class RotateLeft {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        int first = a[0];
        for (int i = 0; i < n - 1; i++) {
            a[i] = a[i + 1];
        }
        a[n - 1] = first;
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

الجزء الثاني: الفرز والصنف Arrays

في كل مرور يطفو الأكبر إلى نهاية الجزء غير المرتب

الفرز الفقاعي يقارن كل عنصر بجاره، ويبدلهما إذا كان الأيسر أكبر. بعد المرور الأول يصبح أكبر عنصر في آخر موقع، كفقاعة صعدت إلى السطح، فلا نحتاج إلى فحصه بعد ذلك.

الخطوة	المقارنة	الصف بعدها
البداية	`-`	`5 3 8 1`
المرور 1	5 و3: بدّل	`3 5 8 1`
المرور 1	5 و8: لا تبديل	`3 5 8 1`
المرور 1	8 و1: بدّل	`3 5 1 8`
المرور 2	3 و5: لا تبديل	`3 5 1 8`
المرور 2	5 و1: بدّل	`3 1 5 8`
المرور 3	3 و1: بدّل	`1 3 5 8`

شاهد المرورات في الناتج وفي التتبّع

اضغط «تتبّع سطرًا سطرًا» وقارن كل خطوة بالجدول أعلاه. راقب pass وj والصف. ثم جرّب مصفوفة مرتبة أصلًا مثل {1, 3, 5, 8}.

public class BubblePasses {
    static void show(int pass, int[] a) {
        System.out.print("Pass " + pass + ":");
        for (int x : a) {
            System.out.print(" " + x);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {5, 3, 8, 1};
        for (int pass = 1; pass < a.length; pass++) {
            for (int j = 0; j < a.length - pass; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
            show(pass, a);
        }
    }
}

الناتج

Pass 1: 3 5 1 8
Pass 2: 3 1 5 8
Pass 3: 1 3 5 8

الحلقة الخارجية تعدّ المرورات والداخلية تقارن الجيران

السطر	لماذا هذا الحد؟
`pass < a.length`	بعد `n - 1` مرورًا يصبح العنصر المتبقي في مكانه تلقائيًا
`j < a.length - pass`	العناصر التي طفت في النهاية مرتبة، و`a[j + 1]` يجب أن يبقى داخل المصفوفة
`a[j] > a[j + 1]`	لو غيّرت `>` إلى `<` لصار الترتيب تنازليًا

المصفوفة مرتبة أصلًا. كم مقارنة وكم تبديلًا ينفذ البرنامج؟

public class BubbleCounts {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4};
        int comparisons = 0;
        int swaps = 0;
        for (int pass = 1; pass < a.length; pass++) {
            for (int j = 0; j < a.length - pass; j++) {
                comparisons++;
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swaps++;
                }
            }
        }
        System.out.println(comparisons);
        System.out.println(swaps);
    }
}

أظهر الناتج

الناتج

6
0

لماذا؟ المقارنات 3 + 2 + 1 = 6 مهما كان الترتيب، لأن الحلقتين لا تعتمدان على القيم. والتبديلات صفر لأن كل عنصر أصغر من جاره الأيمن.

فرز تنازلي

اقرأ n ثم n عددًا، ورتبها من الأكبر إلى الأصغر بالفرز الفقاعي دون استخدام Arrays.sort. اطبعها في سطر واحد بينها مسافة.

import java.util.Scanner;

public class SortDescending {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read the array, bubble sort it largest first, print it

    }
}

stdin

5
3 9 1 7 5

الناتج المتوقع

9 7 5 3 1

تلميح 1

البرنامج نفسه الذي رأيته، مع تغيير عامل مقارنة واحد.

الحل

import java.util.Scanner;

public class SortDescending {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        for (int pass = 1; pass < n; pass++) {
            for (int j = 0; j < n - pass; j++) {
                if (a[j] < a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
        for (int x : a) {
            System.out.print(x + " ");
        }
        System.out.println();
    }
}

الصنف `Arrays` يطبع ويفرز بسطر واحد

كتبنا الفرز بأيدينا لنفهمه. أما في برامجك اليومية فاستخدم Arrays من الحزمة java.util، فهو أسرع وأقل عرضة للخطأ.

`toString` و`sort`

أخيرًا نرى المصفوفة كاملة دون حلقة. غيّر القيم إلى double وجرّب مرة أخرى، ثم احذف Arrays.toString من السطر الأول ولاحظ ما يطبعه البرنامج.

import java.util.Arrays;

public class ArraysDemo {
    public static void main(String[] args) {
        int[] a = {5, 3, 8, 1};
        System.out.println(Arrays.toString(a));
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

الناتج

[5, 3, 8, 1]
[1, 3, 5, 8]

نسينا الاستيراد

public class NoImport {
    public static void main(String[] args) {
        int[] a = {2, 1};
        System.out.println(Arrays.toString(a));
    }
}

رسالة المترجمcannot find symbol

أظهر التصحيح

import java.util.Arrays;

public class NoImport {
    public static void main(String[] args) {
        int[] a = {2, 1};
        System.out.println(Arrays.toString(a));
    }
}

الناتج

[2, 1]

لماذا؟ الصنف Arrays موجود في الحزمة java.util، فلا يعرفه المترجم إلا إذا استوردناه، كما نفعل مع Scanner.

`sort` لا تعيد مصفوفة

import java.util.Arrays;

public class SortVoid {
    public static void main(String[] args) {
        int[] a = {2, 1};
        int[] sorted = Arrays.sort(a);
        System.out.println(Arrays.toString(sorted));
    }
}

رسالة المترجمvoid cannot be converted to int[]

أظهر التصحيح

import java.util.Arrays;

public class SortVoid {
    public static void main(String[] args) {
        int[] a = {2, 1};
        Arrays.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

الناتج

[1, 2]

لماذا؟ Arrays.sort من نوع void: إنها ترتب المصفوفة نفسها، تمامًا كما تغيّر دالتنا عناصر المصفوفة التي تصلها في المحاضرة الماضية.

`copyOf` تنشئ صفًا جديدًا و`fill` تملأ كل الصناديق

الاستدعاء	ما يفعله	يعيد
`Arrays.toString(a)`	يصف العناصر في نص واحد	`String`
`Arrays.sort(a)`	يرتب `a` نفسها تصاعديًا	`void`
`Arrays.copyOf(a, n)`	صف جديد طوله `n`	`int[]`
`Arrays.fill(a, v)`	يضع `v` في كل صندوق	`void`
`Arrays.equals(a, b)`	يقارن الأطوال والعناصر	`boolean`

النسخة منفصلة عن الأصل

توقّع الأسطر الأربعة. إذا كان الطول الجديد أكبر فالصناديق الزائدة تأخذ القيمة الافتراضية، وإذا كان أصغر قُطع الباقي. استبدل Arrays.copyOf(a, a.length) بـ a في السطر الأول وشاهد الفرق.

import java.util.Arrays;

public class CopyFill {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = Arrays.copyOf(a, a.length);
        b[0] = 99;
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));

        System.out.println(Arrays.toString(Arrays.copyOf(a, 5)));

        int[] c = new int[4];
        Arrays.fill(c, 7);
        System.out.println(Arrays.toString(c));
    }
}

الناتج

[1, 2, 3]
[99, 2, 3]
[1, 2, 3, 0, 0]
[7, 7, 7, 7]

`==` تسأل هل هو الصف نفسه، و`Arrays.equals` تقارن المحتوى

`a` و`b` فيهما القيم نفسها، و`c` اسم آخر لـ `a`. ماذا يطبع؟

import java.util.Arrays;

public class CompareArrays {
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        int[] b = {1, 2, 3};
        int[] c = a;
        System.out.println(a == b);
        System.out.println(a == c);
        System.out.println(Arrays.equals(a, b));
    }
}

أظهر الناتج

الناتج

false
true
true

لماذا؟ == تقارن السهمين: a وb صفان مختلفان وإن تشابهت قيمهما، أما a وc فيشيران إلى الصف نفسه. وArrays.equals تفتح الصناديق وتقارن العناصر واحدًا واحدًا.

ما قيمة `Arrays.equals(x, y)` إذا كانت `x` هي `{1, 2}` و`y` هي `{2, 1}`؟

لماذا؟ تقارن الدالة كل موقع بالموقع نفسه: x[0] مع y[0]، وهكذا. فالترتيب جزء من المحتوى.

الجزء الثالث: المصفوفات ذات البعدين

المصفوفة ذات البعدين صفوف وأعمدة، والموقع الأول للصف

`marks`	العمود 0	العمود 1	العمود 2
الصف 0	`80`	`70`	`90`
الصف 1	`60`	`75`	`85`

int[][] marks = new int[2][3]; تنشئ صفين في كل منهما ثلاثة أعمدة.
marks[1][2] هو الصف 1 والعمود 2، أي 85.
marks.length عدد الصفوف، وmarks[0].length عدد الأعمدة في الصف 0.
المصفوفة ذات البعدين هي في الحقيقة مصفوفة عناصرها مصفوفات.

حلقتان متداخلتان

اضغط «تتبّع سطرًا سطرًا» وراقب row يتغير ببطء وcol بسرعة، كما رأيت في الأنماط مع الحلقات المتداخلة. أضف عمودًا رابعًا لكل صف: هل تحتاج الحلقتان إلى تعديل؟

public class Traverse2D {
    public static void main(String[] args) {
        int[][] marks = {
            {80, 70, 90},
            {60, 75, 85}
        };
        for (int row = 0; row < marks.length; row++) {
            for (int col = 0; col < marks[row].length; col++) {
                System.out.print(marks[row][col] + " ");
            }
            System.out.println();
        }
    }
}

الناتج

80 70 90
60 75 85

انتبه إلى الترتيب: الصف ثم العمود. ماذا يطبع؟

public class Index2D {
    public static void main(String[] args) {
        int[][] m = {
            {1, 2, 3},
            {4, 5, 6}
        };
        System.out.println(m.length);
        System.out.println(m[0].length);
        System.out.println(m[1][0]);
    }
}

أظهر الناتج

الناتج

2
3
4

لماذا؟ m فيها صفان، وكل صف فيه ثلاثة عناصر. وm[1][0] هو الصف الثاني والعمود الأول، أي 4.

قوسان لكل بعد

بعض اللغات تكتب الأبعاد بفاصلة. في Java لكل بعد قوسان خاصان به.

public class Comma2D {
    public static void main(String[] args) {
        int[][] m = new int[2, 3];
        System.out.println(m.length);
    }
}

رسالة المترجم']' expected

أظهر التصحيح

public class Comma2D {
    public static void main(String[] args) {
        int[][] m = new int[2][3];
        System.out.println(m.length);
    }
}

الناتج

لماذا؟ يتوقع المترجم أن يُغلق القوس بعد العدد الأول، لذلك يشتكي عند الفاصلة.

مجموع الصف يثبّت الصف، ومجموع العمود يثبّت العمود

الحلقة الخارجية هي ما نثبّته

لاحظ أن المجموع يعود إلى صفر عند بداية كل صف أو عمود. انقل السطر int sum = 0; إلى خارج الحلقة الأولى وتوقّع ما يحدث. ثم استخدم «تتبّع سطرًا سطرًا» لتتأكد.

public class RowColumnSums {
    public static void main(String[] args) {
        int[][] m = {
            {80, 70, 90},
            {60, 75, 85}
        };

        for (int row = 0; row < m.length; row++) {
            int sum = 0;
            for (int col = 0; col < m[row].length; col++) {
                sum += m[row][col];
            }
            System.out.println("Row " + row + ": " + sum);
        }

        for (int col = 0; col < m[0].length; col++) {
            int sum = 0;
            for (int row = 0; row < m.length; row++) {
                sum += m[row][col];
            }
            System.out.println("Column " + col + ": " + sum);
        }
    }
}

الناتج

Row 0: 240
Row 1: 220
Column 0: 140
Column 1: 145
Column 2: 175

مجاميع الجدول

اقرأ rows وcols، ثم أعداد الجدول صفًا صفًا. اطبع مجموع كل صف في سطر بالشكل Row 0: 6، ثم مجموع كل عمود بالشكل Column 0: 5.

import java.util.Scanner;

public class TableSums {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // Read rows and cols, fill the table, print the sums

    }
}

stdin

2 3
1 2 3
4 5 6

الناتج المتوقع

Row 0: 6
Row 1: 15
Column 0: 5
Column 1: 7
Column 2: 9

تلميح 1

للقراءة: int[][] m = new int[rows][cols]; ثم حلقتان متداخلتان.

تلميح 2

في مجموع العمود تكون col في الحلقة الخارجية.

الحل

import java.util.Scanner;

public class TableSums {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rows = in.nextInt();
        int cols = in.nextInt();
        int[][] m = new int[rows][cols];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                m[r][c] = in.nextInt();
            }
        }
        for (int r = 0; r < rows; r++) {
            int sum = 0;
            for (int c = 0; c < cols; c++) {
                sum += m[r][c];
            }
            System.out.println("Row " + r + ": " + sum);
        }
        for (int c = 0; c < cols; c++) {
            int sum = 0;
            for (int r = 0; r < rows; r++) {
                sum += m[r][c];
            }
            System.out.println("Column " + c + ": " + sum);
        }
    }
}

جدول علامات مرتب: `printf` يحدد عرض كل عمود

تعلمت في محاضرة printf أن %6d تحجز ستة مواضع وتضع العدد إلى اليمين، وأن %-8s تضع النص إلى اليسار. هذا ما يجعل الأعمدة مستقيمة مهما اختلف طول القيم.

مصفوفة أسماء ومصفوفة علامات

names[r] هو صاحب الصف r في marks، ويسمى هذا مصفوفتين متوازيتين. أضف طالبًا رابعًا، ثم غيّر العروض وشاهد الجدول يتغير. ثم أضف عمودًا للمعدل بالصيغة %8.2f.

public class MarksTable {
    public static void main(String[] args) {
        String[] names = {"Sara", "Ali", "Mona"};
        int[][] marks = {
            {18, 27, 45},
            {15, 20, 38},
            {20, 30, 49}
        };

        System.out.printf("%-8s%6s%6s%6s%8s%n", "Name", "Quiz", "Mid", "Final", "Total");
        for (int r = 0; r < marks.length; r++) {
            int total = 0;
            System.out.printf("%-8s", names[r]);
            for (int c = 0; c < marks[r].length; c++) {
                System.out.printf("%6d", marks[r][c]);
                total += marks[r][c];
            }
            System.out.printf("%8d%n", total);
        }
    }
}

الناتج

Name      Quiz   Mid Final   Total
Sara        18    27    45      90
Ali         15    20    38      73
Mona        20    30    49      99

الصفوف يمكن أن تختلف أطوالها، فاستخدم `m[row].length` دائمًا

مصفوفة غير منتظمة

لأن كل صف مصفوفة مستقلة، يمكن أن يكون لكل صف طول مختلف، كطلاب سجلوا عددًا مختلفًا من المساقات. غيّر quizzes[row].length إلى quizzes[0].length وشغّل: ماذا يحدث؟ وما الموقع في الرسالة؟

public class Jagged {
    public static void main(String[] args) {
        int[][] quizzes = {
            {9, 7, 8},
            {6},
            {10, 5}
        };
        for (int row = 0; row < quizzes.length; row++) {
            for (int col = 0; col < quizzes[row].length; col++) {
                System.out.print(quizzes[row][col] + " ");
            }
            System.out.println();
        }
    }
}

الناتج

9 7 8
6
10 5

في المصفوفة أعلاه، ما قيمة `quizzes[1].length`؟

لماذا؟ الصف 1 هو {6}، وفيه عنصر واحد. والعدد 6 قيمة ذلك العنصر، وليس الطول.

أسئلة المراجعة

لماذا نبدأ `max` من `a[0]` وليس من 0؟

لماذا؟ إذا كانت كل العناصر سالبة بقيت القيمة 0 دون تغيير. أما a[0] فهو دائمًا عنصر حقيقي من المصفوفة.

لماذا تعيد دالة البحث -1 إذا لم تجد القيمة؟

عند حساب مجموع كل صف، أين نصرّح عن `int sum = 0;`؟

هل يغيّر فرز النسخة المصفوفة الأصلية؟

import java.util.Arrays;

public class SortCopy {
    public static void main(String[] args) {
        int[] a = {3, 1, 2};
        int[] b = Arrays.copyOf(a, a.length);
        Arrays.sort(b);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
    }
}

أظهر الناتج

الناتج

[3, 1, 2]
[1, 2, 3]

لماذا؟ copyOf أنشأت صفًا جديدًا، فالفرز وصل إليه وحده. ولو كتبنا int[] b = a; لتغيّر الاثنان.

المجموع والمعدل: متغير يتراكم أثناء المرور

مجموع العلامات ومعدلها

نسينا (double) هذه المرة. ما المعدل المطبوع؟

معدل العلامات

أكبر عنصر وموقعه: احفظ أفضل ما رأيته حتى الآن

أكبر علامة وأصغرها مع الموقع

هنا نبدأ max من 0 بدل العنصر الأول. ماذا يطبع؟

أكبر عنصر وموقعه

العدّ: عدّاد يزيد حين يتحقق الشرط

كم طالبًا نجح؟

كم مرة تكررت القيمة؟

البحث الخطي يفحص العناصر بالترتيب ويتوقف عند أول تطابق

دالة تعيد الموقع أو -1

خطأ شائع جدًا: أضفنا else داخل الحلقة. ماذا يطبع البرنامج؟

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

ابحث عن القيمة

العكس في المكان: بدّل الطرفين واقترب من المنتصف

موقعان يقترب أحدهما من الآخر

نسينا / 2 في شرط الحلقة. ماذا يطبع البرنامج؟

دالة تعكس المصفوفة

في الإزاحة يحدد اتجاه الحلقة هل تضيع القيم أم تبقى

الإزاحة إلى اليسار

نريد الإزاحة إلى اليمين، لكننا مشينا من اليسار. ماذا يطبع؟

التدوير إلى اليسار

في كل مرور يطفو الأكبر إلى نهاية الجزء غير المرتب

شاهد المرورات في الناتج وفي التتبّع

الحلقة الخارجية تعدّ المرورات والداخلية تقارن الجيران

المصفوفة مرتبة أصلًا. كم مقارنة وكم تبديلًا ينفذ البرنامج؟

فرز تنازلي

الصنف Arrays يطبع ويفرز بسطر واحد

toString وsort

نسينا الاستيراد

sort لا تعيد مصفوفة

copyOf تنشئ صفًا جديدًا وfill تملأ كل الصناديق

النسخة منفصلة عن الأصل

== تسأل هل هو الصف نفسه، وArrays.equals تقارن المحتوى

a وb فيهما القيم نفسها، وc اسم آخر لـ a. ماذا يطبع؟

ما قيمة Arrays.equals(x, y) إذا كانت x هي {1, 2} وy هي {2, 1}؟

المصفوفة ذات البعدين صفوف وأعمدة، والموقع الأول للصف

حلقتان متداخلتان

انتبه إلى الترتيب: الصف ثم العمود. ماذا يطبع؟

قوسان لكل بعد

مجموع الصف يثبّت الصف، ومجموع العمود يثبّت العمود

الحلقة الخارجية هي ما نثبّته

مجاميع الجدول

جدول علامات مرتب: printf يحدد عرض كل عمود

مصفوفة أسماء ومصفوفة علامات

الصفوف يمكن أن تختلف أطوالها، فاستخدم m[row].length دائمًا

مصفوفة غير منتظمة

في المصفوفة أعلاه، ما قيمة quizzes[1].length؟

أسئلة المراجعة

لماذا نبدأ max من a[0] وليس من 0؟

لماذا تعيد دالة البحث -1 إذا لم تجد القيمة؟

عند حساب مجموع كل صف، أين نصرّح عن int sum = 0;؟

هل يغيّر فرز النسخة المصفوفة الأصلية؟

نسينا `(double)` هذه المرة. ما المعدل المطبوع؟

هنا نبدأ `max` من 0 بدل العنصر الأول. ماذا يطبع؟

خطأ شائع جدًا: أضفنا `else` داخل الحلقة. ماذا يطبع البرنامج؟

نسينا `/ 2` في شرط الحلقة. ماذا يطبع البرنامج؟

الصنف `Arrays` يطبع ويفرز بسطر واحد

`toString` و`sort`

`sort` لا تعيد مصفوفة

`copyOf` تنشئ صفًا جديدًا و`fill` تملأ كل الصناديق

`==` تسأل هل هو الصف نفسه، و`Arrays.equals` تقارن المحتوى

`a` و`b` فيهما القيم نفسها، و`c` اسم آخر لـ `a`. ماذا يطبع؟

ما قيمة `Arrays.equals(x, y)` إذا كانت `x` هي `{1, 2}` و`y` هي `{2, 1}`؟

جدول علامات مرتب: `printf` يحدد عرض كل عمود

الصفوف يمكن أن تختلف أطوالها، فاستخدم `m[row].length` دائمًا

في المصفوفة أعلاه، ما قيمة `quizzes[1].length`؟

لماذا نبدأ `max` من `a[0]` وليس من 0؟

عند حساب مجموع كل صف، أين نصرّح عن `int sum = 0;`؟