الانتقال إلى المحتوى

التفكير الحسابي وحل المشكلات

A-Level علوم الحاسوب · الموضوع 19

درس فيديو لهذا الموضوع افتح صفحة الفيديو
15:32

البحث والفرز

دفتر هاتف بمليون اسم. إذا فحصتها واحداً تلو الآخر، قد تقوم بمليون مقارنة. لكنك تعرف بالفعل الحيل: افتحها في المنتصف…

سرد باللغة الإنجليزية · ترجمة نصية بالإنجليزية و中文 يمكنك التبديل بينهما

19.1

خوارزميات البحث

المنهج
يجب أن يكون المرشحون قادرين على: ملاحظات وإرشادات
إظهار فهم طريقتي البحث الخطي والبحث الثنائي كتابة خوارزمية لتنفيذ البحث الخطي كتابة خوارزمية لتنفيذ البحث الثنائي الشروط اللازمة لاستخدام البحث الثنائي كيف يتغير أداء البحث الثنائي وفقاً لعدد عناصر البيانات
إظهار فهم طريقتي الفرز بالإدراج والفرز الفقاعي كتابة خوارزمية لتنفيذ الفرز بالإدراج كتابة خوارزمية لتنفيذ الفرز الفقاعي قد يعتمد أداء روتين الفرز على الترتيب الأولي للبيانات وعدد عناصر البيانات
إظهار الفهم والاستخدام لـ الأنواع المجردة للبيانات (ADT) كتابة خوارزميات لإيجاد عنصر في كل مما يلي: قائمة مرتبطة، شجرة ثنائية كتابة خوارزميات لإدراج عنصر في كل مما يلي: مكدس، طابور، قائمة مرتبطة، شجرة ثنائية كتابة خوارزميات لحذف عنصر من كل مما يلي: مكدس، طابور، قائمة مرتبطة إظهار الفهم بأن الرسم البياني هو مثال على نوع بيانات مجرد. وصف الخصائص الرئيسية للرسم البياني وتبرير استخدامه لموقف معين. لن يُطلب من المرشحين كتابة كود لهيكلة الرسم البياني
إظهار كيفية إمكانية تنفيذ الأنواع المجردة للبيانات باستخدام نوع abstract آخر وصف الـADTs التالية وإظهار كيفية تنفيذها من أنواع مدمجة مناسبة أو ADTs أخرى: مكدس، طابور، قائمة مترابطة، قاموس، شجرة ثنائية
إظهار الفهم أن الخوارزميات المختلفة التي تؤدي نفس المهمة يمكن مقارنتها باستخدام معايير (مثل الوقت المستغرق لإنجاز المهمة والذاكرة المستخدمة) بما في ذلك استخدام رمزية Big O لتحديد تعقيد الوقت والمساحة

المصدر: منهج كامبريدج الدولي

Big O: how algorithms scale
Insertion sort: slide each card into place
فرز الفقاعات، مررة بمررة
Binary search: halve and conquer

يجد البحث قيمة مستهدفة في مجموعة، غالبًا ما تكون مصفوفة، ويعيد موضعها أو «لم يُعثر عليها».

An open telephone directory
البحث في قائمة مرتبة، مثل دفتر الهاتف، أسرع بكثير من التحقق من كل سجل واحد تلو الآخر

البحث الخطي

البحث الخطي يمر من البداية إلى النهاية، مقارناً كل عنصر بالمستهدف:

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1   // not found

لا يلزم أي إعداد، لذا يعمل على أي قائمة. في أسوأ الحالات O($n$) (عندما يكون الهدف في النهاية أو غير موجود)؛ وفي أفضل الحالات 1 مقارنة. استخدمه مع البيانات غير المرتبة أو القوائم الصغيرة. (القيمة -1 المعادة هي قيمة حارسة، أي موضع مستحيل يعني «لم يُعثر عليه»؛ وتختبر الجهة المستدعية IF result = -1.)

النسخة الامتحانية. يطلب الورق 3 إكمال بحث خطي مكتوب باستخدام علم وحلقة WHILE، والورق 4 كتابة دالة تُرجع الفهرس أو عدداً. كلاهما يبدو هكذا:

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // how many times Target occurs; 0 means not found
ENDFUNCTION

للوقوف عند أول تطابق بدلاً من ذلك، استخدم حلقة WHILE Index <= 100 AND NOT Found تضع Found ← TRUE وتحتفظ بالفهرس. النقاط مخصصة للحلقة على كل عنصر، والمقارنة، وما يُرجع عندما يكون القيمة غائبة.

A row of alphabet cells A to Z; cells A to V are shaded as checked and W is highlighted as the match, with a pointer below W
البحث الخطي يتحقق من كل حرف على التوالي — 23 مقارنة لإيجاد W

البحث الثنائي

يتطلب البحث الثنائي أن تكون البيانات مرتبة. انظر إلى العنصر الأوسط؛ فإن كان هو الهدف انتهى البحث، وإن كان الهدف أصغر فابحث في النصف الأيسر، وإلا ففي النصف الأيمن، مع تنصيف النطاق في كل مرة:

low ← 1
high ← n
WHILE low <= high DO
    MiddleIndex ← (low + high) DIV 2
    IF A[MiddleIndex] = target THEN
        RETURN MiddleIndex
    ENDIF
    IF A[MiddleIndex] < target THEN
        low ← MiddleIndex + 1
    ELSE
        high ← MiddleIndex - 1
    ENDIF
ENDWHILE
RETURN -1

أسوأ حالة O($\log_{2} n$) — لمليون عنصر، حوالي 20 مقارنة. أسرع بكثير من البحث الخطي على مصفوفات كبيرة مرتبة، لكن يجب ترتيبها أولاً (تكلفة O($n \log n$) لمرة واحدة)، يستحق الأمر إذا كنت تبحث مرات عديدة.

«اذكر الشرط اللازم للبحث الثنائي.» يجب أن تكون البيانات مرتبة (تصاعديًا أو تنازليًا حسب المفتاح الذي يجري البحث عنه). «صف كيفية إجراء بحث ثنائي» (ثلاث درجات): (1) أوجد العنصر الأوسط في القائمة أو النطاق الحالي وقارنه بالهدف؛ (2) إذا تطابقا انتهى البحث؛ وإذا كان الهدف أصغر فأعد البحث في النصف الأدنى، وإذا كان أكبر ففي النصف الأعلى؛ (3) استمر في تنصيف النطاق حتى تجد العنصر أو يصبح النطاق فارغًا، مما يعني أنه غير موجود.

النسخة الامتحانية، مع الحدود والعلم، هي ما يجب إعادة إنتاجه عند طلب إكمال الخوارزمية:

DECLARE Lower, Upper, MiddleIndex : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    MiddleIndex ← (Lower + Upper) DIV 2
    IF Names[MiddleIndex] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[MiddleIndex] < Target THEN
            Lower ← MiddleIndex + 1
        ELSE
            Upper ← MiddleIndex - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN
    OUTPUT MiddleIndex
ELSE
    OUTPUT "Not found"
ENDIF

مثال محلول (تتبّع بحث ثنائي). يحتوي Names[0:9] على Ali, Ben, Cai, Dev, Eva, Fay, Gus, Hal, Ivy, Jo. تتبّع نسخة الامتحان للبحث عن Target = "Ivy"، ثم عن Target = "Cat"، مع ذكر Lower وUpper وMiddleIndex في كل خطوة.

بالنسبة إلى «Ivy»:

Lower Upper MiddleIndex Names[MiddleIndex] النتيجة
0 9 4 Eva Eva < Ivy، لذا Lower ← 5
5 9 7 Hal Hal < Ivy، لذا Lower ← 8
8 9 8 Ivy Found ← TRUE

المخرَج هو 8، بعد ثلاث مقارنات. بالنسبة إلى «Cat»: الوسط 4 (Eva > Cat، وUpper ← 3)؛ الوسط 1 (Ben < Cat, Lower ← 2); middle 2 (Cai < Cat, Lower ← 3); middle 3 (Dev > Cat، وUpper ← 2). الآن Lower (3) أكبر من Upper (2)، لذا تنتهي الحلقة ويُخرَج «Not found» بعد أربع مقارنات، وهي أسوأ حالة لعشرة عناصر ($\lceil\log_2 10\rceil = 4$). يقرّب DIV إلى الأسفل، لذا فإن وسط 0 و9 هو 4، وليس 4.5 أو 5. تُقارَن السلاسل وفق الترتيب الأبجدي (ترتيب رموز المحارف).

«اشرح كيف يتغير الأداء بتغير عدد العناصر.» تُنصّف كل مقارنة عدد العناصر المتبقية، لذا فإن الحد الأقصى لعدد المقارنات يقارب $\log_{2} n$: مضاعفة حجم القائمة تضيف مقارنة واحدة فقط. وهذا هو O($\log n$). «قارن بين البحث الخطي والثنائي»: يحتاج البحث الخطي إلى ما يصل إلى $n$ من المقارنات (O($n$))، وإلى نصف ذلك في المتوسط، لكنه يعمل على بيانات غير مرتبة؛ ويحتاج البحث الثنائي إلى $\log_{2} n$ على الأكثر (O($\log n$))، وهو أسرع بكثير للقوائم الكبيرة، لكن يجب أولًا ترتيب البيانات وأن تسمح بالوصول المباشر إلى العنصر الأوسط (مصفوفة، لا قائمة مترابطة). بالنسبة إلى $1000$ عنصرًا: $1000$ مقابل $10$ من المقارنات.

Three rows showing binary search on the sorted alphabet; the active low-to-high range halves each step as the middle letter M, then T, then W is compared with W
البحث الثنائي يُضعف النطاق في كل خطوة (منخفض / وسط / عالي) — مجرد 3 مقاربات لإيجاد W

A library card catalogue: a wall of small wooden drawers, one pulled open to show the cards filed in order *فهرس بطاقات: السجلات المرتبة هي ما يجعل البحث الثنائي ممكناً — ضعّف، انظر، ضعّف مرة أخرى

استكشف

البحث الخطي مقابل الثنائي

البحث عن قيمة. البحث الثنائي ينصف القائمة في كل خطوة (فقط على البيانات المرتبة)؛ بينما البحث الخطي يفحص العناصر واحداً تلو الآخر.

مفردات تدريب
English العربية
insertion sort/ɪnˈsɜːʃn sɔːt/ فرز الإدراج
bubble sort/ˈbʌbl sɔːt/ ترتيب الفقاعة
binary search/ˈbaɪnəri sɜːtʃ/ البحث الثنائي
array/əˈreɪ/ مصفوفة
linear search/ˈlɪnɪə sɜːtʃ/ بحث خطي
19.1

خوارزميات الترتيب

ترتيب الفقاعات

يمر الترتيب الفقاعي على المصفوفة مرارًا، مبدّلًا أزواج العناصر المتجاورة غير المرتبة، بحيث «يطفو» العنصر الأكبر إلى النهاية في كل مرور:

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

أفضل حالة O($n$) (مرتب مسبقاً، مع الخروج المبكر); متوسط/أسوأ O($n^{2}$). بسيط لكن بطيء لـ $n$ كبير.

الترتيب بالإدراج

ترتيب الإدراج يبني بادئاً مرتباً من اليسار، بإدراج كل عنصر جديد في مكانه عن طريق تحريك الأكبر يميناً:

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

أفضل حالة O($n$) (مرتب مسبقاً); أسوأ O($n^{2}$). جيد لـ صغيرة أو قريبة من الترتيب المصفوفات. يرتب محلياً و ثابت (يحافظ على ترتيب العناصر المتساوية).

تتبع الترتيب

مهارة شائعة هي عرض المصفوفة بعد كل مرور خارجي. لـ [D, T, H, R] مع ترتيب الإدراج: المرور 1 (المفتاح T) لا تغيير؛ المرور 2 (المفتاح H) → [D, H, T, R]؛ المرور 3 (المفتاح R) → [D, H, R, T].

لقطات ترتيب الإدراج الاشتقاق (عد العكسات). العكسة هي

تتحرك عناصر المصفوفة نفسها بطريقة مختلفة باستخدام الترتيب الفقاعي: يقارن المرور 1 بين D/T (دون تبديل)، وT/H (تبديل)، وT/R (تبديل)، فينتج [D, H, R, T] مع وجود العنصر الأكبر في النهاية؛ ولا يُجري المرور 2 أي تبديل، لذا توقف الراية الترتيب. اعرض المصفوفة كاملة بعد كل مرور، واحسب المقارنات إذا طُلب منك ذلك: $3$ في المرور 1 و$2$ في المرور 2 (تتوقف النسخة أعلاه قبل موضع إضافي في كل مرور)، أي $5$ إجمالًا.

كتابة خوارزمية ترتيب من البداية. يُجاب عن «اكتب شيفرة كاذبة لترتيب DataArray[1:1000] تصاعديًا» بترتيب فقاعي كامل مع راية للخروج المبكر، أو بترتيب بالإدراج، مع التصريح المناسب ووضع المسافات البادئة؛ ويستحق أي منهما الدرجة الكاملة إذا عمل مع كل مدخل:

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

للترتيب التنازلي غيّر > إلى <؛ ولترتيب السجلات أو مصفوفة ذات 2 أبعاد حسب حقل واحد، قارن ذلك الحقل لكن بدّل السجل كاملًا (أو كل الأعمدة). إذا طُلبت كتابة ترتيب بالإدراج «ينفذ المهمة نفسها» التي ينفذها ترتيب فقاعي معطى، فاحتفظ باسم المصفوفة واتجاه الترتيب نفسيهما وأعد كتابة الترتيب بالإدراج أعلاه مع عكس المقارنة إذا كان الترتيب تنازليًا.

«صف طريقتين يتأثر بهما أداء الترتيب بالبيانات» (درجتان). (1) عدد العناصر: يستغرق ترتيب $O(n^{2})$ أربعة أضعاف الوقت عند مضاعفة عدد العناصر. (2) مدى ترتيب البيانات مسبقًا: ينتهي الترتيب الفقاعي باستخدام راية، أو الترتيب بالإدراج، بمرور واحد على البيانات المرتبة مسبقًا ($O(n)$)، ويبذل أكبر جهد مع البيانات المرتبة عكسيًا؛ ويعتمد عدد التبديلات على عدد الأزواج غير المرتبة. (يُقبل أيضًا: نطاق القيم المكررة أو عددها، وما إذا كانت العناصر سجلات كبيرة مكلفة النقل.) كل من الترتيب الفقاعي والترتيب بالإدراج هو O($n^{2}$) في أسوأ الحالات والحالة المتوسطة وO($n$) في أفضل الحالات؛ أما الترتيب السريع والترتيب بالدمج فهما O($n \log n$)، ولهذا يُستخدمان للبيانات الكبيرة.

صفوف تتبع عملية فرز إدراج للعناصر D, T, H, R عبر ثلاث مراحل؛ تم تظليل البادئة المرتبة وأسهم تشير إلى إزاحة كل عنصر أكبر يميناً لإفساح المجال لسقوط المفتاح
فرز إدراج لـ [D, T, H, R]، حيث يتم إزاحة كل مفتاح إلى مكانه مرحلة تلو الأخرى
استكشف

مشاهدة عملية ترتيب

مرر خوارزمية الترتيب وراقب الأعمدة ترتب نفسها — كيف تعمل خوارزمية الترتيب خطوة بخطوة.

19.1

الأنواع المجردة للبيانات (ADTs) في الخوارزميات

تظهر الأنواع المجردة للبيانات (ADTs) من الموضوع 10 داخل العديد من الخوارزميات: المكدس يقود التمرير العميق وإلغاء الإجراءات؛ القائمة الانتظار تقود التمرير العرضي وترتيب الطباعة؛ القائمة المترابطة تسمح للنمو والتقلص.

يمكن بناء ADTs من أنواع مجردة أخرى وليس فقط من المصفوفات: قائمة انتظار من مكدسين؛ مكدس من قائمة مترابطة (دفع = إضافة رأس عقدة)؛ قائمة انتظار من قائمة مترابطة مع مؤشرات الرأس والذيل؛ شجرة ثنائية من عقد بمؤشرين للطفل؛ قاموس يخزن أزواج المفتاح→القيمة (غالباً على جدول هاش). فصل المهام بهذه الطريقة — لا يحتاج الخوارزم المستخدم للـ ADT إلى معرفة كيفية بنائه.

الـ ADTs التي يطلب منك الامتحان وصفها وتنفيذها

المكدس (آخر يدخل، أول يخرج): تُضاف العناصر (تُضغط) وتُزيل (تُفصح) في نفس النهاية، وهي الأعلى؛ مؤشر TopOfStack يحتفظ بمؤشر العنصر العلوي. يُنفذ باستخدام مصفوفة ذلك المؤشر واحد: يتحقق الدفع من أن المكدس ليس ممتلاً، يزيد المؤشر ويخزن العنصر؛ يتحقق الفصح من أنه ليس فارغاً، يعيد العنصر العلوي وينقص المؤشر.

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN      // full (array 0 to 9)
        RETURN FALSE
    ENDIF
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN      // empty
        RETURN -1
    ENDIF
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

قائمة الانتظار (أدخل أولاً، يخرج أولاً): تنضم العناصر إلى الخلف (دخول) وتخرج من الأمام (خروج)؛ مؤشران وعدد. في قائمة الانتظار الخطية ينزلق مؤشر الأمام عبر المصفوفة حتى تُهدر المساحة في البداية؛ قائمة الانتظار الدائرية تعيد تدوير كلا المؤشرين مع MOD، بحيث يتم إعادة استخدام كل خلية.

قائمة انتظار دائرية ست خلايا مصفوفة تحتوي ثلاثة عناصر في الخلايا 3 إلى 5، مع مؤشر أمامي عند 3 ومؤشر خلفي عند 5، وسهم متقطع يظهر أن العنصر التالي يدور إلى الخلية 0
قائمة انتظار دائرية: يتقدم مؤشرا الخلف والأمام مع MOD، لذا تُعاد استخدام أول خلايا المصفوفة بعد مغادرة عناصرها
FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN      // full
        RETURN FALSE
    ENDIF
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN      // empty
        RETURN ""
    ENDIF
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

القائمة المترابطة: تسلسل من العقد، كل منها يحمل عنصراً ومؤشراً للعقدة التالية؛ مؤشر البدء يعطي العقدة الأولى ومؤشر فارغ (0 أو $-1$) ينتهي القائمة. في تنفيذ المصفوفة تحتفظ مصفوفتان موازيان بالبيانات والمؤشرات، وتُربط الخلايا غير المستخدمة في قائمة حرة بحيث تعرف عملية الإدراج أين تضع العقدة الجديدة.

مصفوفتان موازيان Data و Pointer تنفذان قائمة مترابطة لأسماء Ann, Ben و Dan: مؤشر البدء هو 1، تربط المؤشرات 1 إلى 3 إلى 2 إلى 0، والخلايا غير المستخدمة 4، 5 و 6 تشكل القائمة الحرة
قائمة مترابطة في مصفوفتين: ترتيب القائمة موجود في المؤشرات، وليس في المواقع؛ إدخال اسم يعني أخذ خلية من القائمة الحرة وإعادة ربط مؤشرين
FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // index, or 0 if absent
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN
            RETURN Current
        ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

لـ الإدراج في قائمة مرتبة: خذ أول خلية حرة (NewNode ← FreeList، FreeList ← Pointer[FreeList])، تخزن العنصر، ثم امشِ القائمة مع Previous وCurrent مؤشر حتى Data[Current] > Item أو النهاية؛ ضع Pointer[NewNode] ← Current وPointer[Previous] ← NewNode (أو Start ← NewNode إذا كان الأول). لـ الحذف، أعد ربط العقدة السابقة لتتجاوز المحذوفة وأعد الخلية للقائمة الحرة.

شجرة ثنائية: عقدة جذر، تحمل كل عقدة بيانات، إشارة يسرى لشجرة جزئية بقيم أصغر وإشارة يمنى لشجرة جزئية بقيم أكبر. تُنفذ كمصفوفة 2D (أو ثلاث مصفوعات 1D) Tree[Index, 0..2] للإشارة اليسرى، البيانات، الإشارة اليمنى، مع إشارة للجذر وإشارة للموقع الحر التالي.

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // index, or -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN
            RETURN Current
        ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // go left
        ELSE
            Current ← Tree[Current, 2]      // go right
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

لـ الإدراج: ذخّر العنصر في العقدة الحرة التالية بكلا المؤشرين $-1$؛ إذا كانت الشجرة فارغة اجعلها الجذر؛ وإلا مشِ للأسفل من الجذر، اذهب يميناً أو يساراً بالمقارنة، حتى يصبح المؤشر الذي ستتبعه $-1$، وضع ذلك المؤشر على العقدة الجديدة. ADT من نوع ADT آخر: المكدس هو قائمة مترابطة يعمل فيها الدفع والفصح كلاهما في البداية؛ قائمة الانتظار هي قائمة مترابطة مع مؤشر بداية ومؤشر نهاية؛ يمكن إنشاء قائمة انتظار من مكدسين (دفع على أحدهما، فصح من الآخر، نقل كل شيء عندما يكون الثاني فارغاً)؛ عقد الشجرة الثنائية هي سجلات أو كائنات مربوطة بمؤشرات، لذلك تُبنى من بنية قائمة مترابطة من العقد. قائل أي عمليات النوع المجرد الجديد تتوافق مع أي عمليات النوع المجرد القديم.

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

شجرة بحث ثنائية جذرها 27، وشجرتها الفرعية اليسرى تتكون من 19 و16 و21 و17، واليمنى من 36 و30 و55 و89، مع تسمية الجذر والمؤشرين الأيسر والأيمن وعقدة ورقية
شجرة بحث ثنائية: لكل عقدة ما يصل إلى عقدتين فرعيتين
شجرة بحث ثنائية بجذر 4 (تحت شجرة يسرى 2 فوق 1 و 3، وتحت شرة يمنى 6 فوق 5 و 7)؛ الزيارات المسبقة 4 2 1 3 6 5 7، الترتيبية 1 2 3 4 5 6 7 (مرتبة)، اللاحقة 1 3 2 5 7 6 4
ثلاثة تمريرات عميقة للشجرة الثنائية: المسبقة، الترتيبية (الترتيب المرتب) واللاحقة
مفردات تدريب
English العربية
linked list/lɪŋkt lɪst/ قائمة مرتبطة
in place/ɪn pleɪs/ في الموقع
stable/ˈsteɪbl/ مستقر
stack/stæk/ مكدس
queue/kjuː/ طابور
node/nəʊd/ عُقدَة
pointers/ˈpɔɪntəz/ المؤشرات
binary tree/ˈbaɪnəri triː/ شجرة ثنائية
dictionary/ˈdɪkʃənəri/ قائمة المفردات
circular queue/ˈsɜːkjʊlə kjuː/ طابور دائري
free list/friː lɪst/ قائمة فارغة
time complexity/taɪm kəmˈpleksɪti/ تعقيد الوقت
Big-O notation/bɪɡ əʊ nəʊˈteɪʃn/ رمز بي-أو
space complexity/speɪs kəmˈpleksɪti/ تعقيد المساحة
19.1

مقارنة الخوارزميات

تعقيد الوقت

تعقيد الوقت هو كيفية نمو وقت التشغيل مع حجم الإدخال $n$، يُكتب بـ رمزية بي-أو O (الحد المهيمن): O(1) ثابت، O($\log n$) بحث ثنائي، O($n$) بحث خطي، O($n \log n$) عمليات فرز جيدة، O($n^{2}$) فقاعات/فرز إدراج. الرتبة الأصغر أفضل على النطاق الواسع، حتى لو كان خوارزمية أخرى أسرع لأحجام صغيرة $n$.

لتوضيح ذلك بشكل ملموس: لترتيب مليون عنصر، يكمل ترتيب $O(n \log n)$ في جزء من الثانية، بينما قد يستغرق ترتيب $O(n^{2})$ دقائق.

مثال محلول. قائمة مرتبة تحتوي على $1000$ عنصر. كم عدد المقارنات التي تحتاجها كل عملية بحث في أسوأ حالة؟

يبحث الخطي عن العناصر واحداً تلو الآخر، لذا قد يحتاج إلى ما يصل إلى $1000$ مقارنات — وهذا هو $O(n)$. أما البحث الثنائي فيقسم القائمة إلى نصفين في كل خطوة، لذا يحتاج إلى ما لا يزيد عن $\lceil \log_2 1000 \rceil = 10$ مقارنات — وهذا هو $O(\log n)$. مضاعفة القائمة لتصل إلى $2000$ عنصر تضيف فقط مقارنة واحدة للبحث الثنائي، ولكن ما يصل إلى $1000$ إضافية للبحث الخطي — ولهذا السبب، فإن ترتيب النمو وليس السرعة الخام هو ما يحدد الفائز على النطاق الواسع.

وصف رتبة التعقيد. O(1): الزمن ثابت، ولا يعتمد على عدد العناصر (إضافة عنصر إلى مكدس، أو قراءة عنصر من مصفوفة). O($\log n$): يزداد الزمن مع لوغاريتم عدد العناصر، لذا فإن مضاعفة البيانات تضيف خطوة إضافية ثابتة فقط (البحث الثنائي). O($n$): يزداد الزمن بالتناسب مع عدد العناصر (البحث الخطي، والمرور مرة واحدة على قائمة). O($n \log n$): أسوأ قليلًا من الخطي (خوارزميات الترتيب الفعالة). O($n^{2}$): يزداد الزمن مع مربع عدد العناصر، لذا فإن مضاعفة البيانات تضاعف الزمن أربع مرات (الترتيب الفقاعي والترتيب بالإدراج). يُجاب عن «اذكر تعقيد Big O للبحث الثنائي في Names[0:99]» بـ$O(\log n)$، ويُوصف معناه كما سبق؛ تقيس Big O كيفية تغير الزمن أو الذاكرة مع حجم البيانات، لا الزمن الفعلي.

مثال محلول (رتبة تعقيد مقطع برمجي). اذكر التعقيد الزمني لكل مقطع، حيث n هو عدد العناصر.

// Fragment A
FOR i ← 1 TO n
    FOR j ← 1 TO n
        Total ← Total + Grid[i, j]
    NEXT j
NEXT i

// Fragment B
Count ← 0
WHILE n > 1
    n ← n DIV 2
    Count ← Count + 1
ENDWHILE

// Fragment C
FOR i ← 1 TO n
    Total ← Total + A[i]
NEXT i
FOR i ← 1 TO n
    OUTPUT A[i] / Total
NEXT i

تعقيد A هو $O(n^{2})$: تُنفذ التعليمة الداخلية $n$ مرة لكل مرور من مرات المرور الخارجية البالغ عددها $n$، أي $n \times n$ إجمالًا. وتعقيد B هو $O(\log n)$: يُنصَّف $n$ في كل مرور، لذا تُنفذ الحلقة نحو $\log_2 n$ مرة (عند $n = 64$، ست مرات مرور). وتعقيد C هو $O(n)$: تستغرق حلقتان إحداهما بعد الأخرى $n + n = 2n$ خطوة، وتُحذف الثوابت. القاعدة: الحلقات المتداخلة تُضرب، والحلقات المتتابعة تُجمع، ولا يُحتفظ إلا بالحد الأسرع نموًا، لذا فإن $3n^{2} + 5n + 2$ هو $O(n^{2})$.

رسم بياني لوقت التنفيذ مقابل حجم الإدخال n للترتيبات الشائعة: O(1) و O(log n) تظل مسطحة تقريباً، O(n) ترتفع بلطف، O(n log n) أكثر انحداراً، و O(n squared) تصعد بسرعة أكبر
كيف تقارن الترتيبات الشائعة للنمو: الترتيب الأصغر يفوز على النطاق الواسع
A line graph of running time against the number of elements n: bubble sort and insertion sort rise steeply as O(n squared), while quick sort stays low as O(n log n)
كيف ينمو وقت الترتيب مع عدد العناصر $n$: ترتبط الترتيبات $O(n^2)$ بعيداً عن ترتيب $O(n\log n)$

تعقيد المساحة

تعقيد المساحة هو الذاكرة الإضافية المطلوبة. يستخدم ترتيب الفقاعة والإدراج O(1) إضافياً (في المكان)؛ يستخدم ترتيب merge sort O($n$)؛ تستخدم الاستدعاءات المتكررة ذاكرة مكدس تتناسب مع عمقها. غالباً ما يكون هناك توازن بين الوقت والذاكرة.

معايير أخرى

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

استكشف

كيف ينمو وقت التنفيذ مع n

ارفع n للأعلى وقارن المنحنيات: O(1) و O(log n) تظل مسطحة تقريبًا، O(n) ترتفع باستمرار، O(n²) تنفجر. ولهذا السبب تُستخدم Big-O — وليس ساعة إيقاف — للمقارنة بين الخوارزميات على المدخلات الكبيرة.

استكشف

نمو Big-O

غيّر حجم الإدخال n وقارن مدى سرعة نمو عمل كل خوارزمية — وهو المبدأ وراء التعقيد الزمني.

19.2

الاستدعاء المتكرر

المنهج
يجب أن يكون المرشحون قادرين على: ملاحظات وإرشادات
إظهار فهم الاستدعاء الذاتي الميزات الأساسية لـالاستدعاء الذاتي كيف يتم التعبير عن الاستدعاء الذاتي في لغة برمجة كتابة وتتبع الخوارزميات الاستدعاء الذاتي متى يكون استخدام الاستدعاء الذاتي مفيداً
إظهار الوعي بما يجب على المترجم فعله لترجمة كود البرمجة الاستدعاء الذاتي استخدام المكدسات وإزالة الاستدعاءات

المصدر: منهج كامبريدج الدولي

الاستدعاء المتكرر: المكدس يلتف ثم ينفك
أربع صناديق استدعاء، كل منها محاذى أسفل السابق: total([4, 7, 2]) = 4 + total([7, 2]); total([7, 2]) = 7 + total([2]); total([2]) = 2 + total([]); total([]) = 0 هي الحالة الأساسية. القيم تعود للأعلى: 2، ثم 9، ثم 13
تتجه الاستدعاءات للأسفل نحو الحالة الأساسية؛ وتعود النتائج للأعلى

الخوارزميات المتكررة تستخدم الاستدعاء المتكرر: تستدعي الدالة نفسها بإصدار أصغر من نفس المشكلة، حتى تنتهي سلسلة من خلال حالة أساسية. تتكون من جزأين: الحالة الأساسية (صغيرة بما يكفي لحلها مباشرة — بدونها لن يتوقف الاستدعاء المتكرر أبداً) والحالة المتكررة (تقليل المدخلات والاستدعاء لنفسها).

المضروب (Factorial):

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

الاستدعاء المتكرر طبيعي للمشاكل ذاتية التشابه: الأشجار، القسمة والفتح (البحث الثنائي، ترتيب merge)، والبيانات المتداخلة. عندما يكون غير مناسب، تكون الحلقة عادة أنظف.

«صف المقصود بالاستدعاء الذاتي» (درجتان). دالة أو إجراء يُعرَّف بدلالة نفسه: فهو يستدعي نفسه من داخل جسمه، بنسخة أصغر من المسألة في كل مرة، حتى يصل إلى حالة أساس. «اذكر ثلاث سمات أساسية للاستدعاء الذاتي»: (1) حالة أساس (شرط توقف) تعيد قيمة دون استدعاء آخر؛ (2) حالة عامة يستدعي فيها الروتين نفسه؛ (3) يقرّب كل استدعاء المسألة من حالة الأساس (تُخفَّض قيمة المعامل)، حتى ينتهي الاستدعاء الذاتي. تضيف بعض مخططات التصحيح: تُعاد القيم عند تتابع العودة من الاستدعاءات.

«صف متى يكون استخدام الاستدعاء الذاتي مفيدًا، وأعط مثالًا.» عندما تكون المسألة معرّفة طبيعيًا بدلالة نسخ أصغر من نفسها، بحيث يكون الحل بالاستدعاء الذاتي أقصر وأوضح وأقرب إلى التعريف الرياضي من الحلقة: مثل المضروب أو عدد فيبوناتشي، والبحث الثنائي، واجتياز شجرة ثنائية، والترتيب بالدمج أو الترتيب السريع، ومعالجة البنى المتداخلة مثل المجلدات داخل المجلدات. وهو اختيار ضعيف عندما يكون العمق كبيرًا (فقد يفيض المكدس) أو عندما تُحسب المسألة الفرعية نفسها مرات كثيرة (كما في حساب فيبوناتشي بالطريقة المباشرة).

تتبع استدعاء متكرر

بالنسبة لـ Factorial(4): تذهب الاستدعاءات نزولاً حتى Factorial(1)=1، ثم الانفكاك يضرب صعوداً: 2*1=2، 3*2=6، 4*6=24. النتيجة النهائية 24. تتبع كل استدعاء معلق على المكدس.

مثال محلول. الدالة أدناه معطاة بدون شرح. تتبع Unknown(3, 5) واذكر مخرجاتها وقيمتها المُرجعة.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

الاستدعاء 1: $X = 3, Y = 5$: $3 < 5$، الإخراج 8، استدعاء Unknown(4, 4). الاستدعاء 2: $4 < 4$ غير صحيح، إرجاع 0. الانفكاك: يعود الاستدعاء 1 بـ $0 + 1 = 1$. إخراج 8، القيمة المُرجعة 1. اكتب التتبع كجدول بصف لكل استدعاء (المعاملات، الشرط، الإخراج، ما يُرجعه)، وقم بإرجاعات الاستدعاء الأعمق صعوداً: هذا هو الانفكاك الذي يبحث عنه مفتاح التصحيح.

مثال محلول (فيبوناتشي). Fib(n) يُرجع n عندما n < 2، وإلا Fib(n - 1) + Fib(n - 2). أوجد Fib(5).

Fib(5) = Fib(4) + Fib(3)؛ Fib(4) = Fib(3) + Fib(2)؛ Fib(3) = Fib(2) + Fib(1)؛ Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. لذا Fib(3) = 1 + 1 = 2، Fib(4) = 2 + 1 = 3، Fib(5) = 3 + 2 = 5. يتم الوصول إلى الحالة الأساسية مرات كثيرة (يتم حساب Fib(2) ثلاث مرات)، وهو سبب بطء هذه النسخة: فهي تقوم بـ 15 استدعاءً لـ $n = 5$ وتضاعف تقريباً عدد الاستدعاءات لكل زيادة في $n$.

تحويل الاستدعاء الذاتي إلى تكرار. يمكن إعادة كتابة كل إجراء استثنائي باستخدام حلقة، والتي تستهلك ذاكرة أقل وتكون أسرع: احتفظ بنتيجة متراكمة وكرر من الحالة الأساسية للأعلى. المضروب كحلقة:

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

عند الطلب لتحويل ترتيب إدراج استثنائي أو بحث إلى شكل تكراري، استبدل الاستدعاء الذاتي بحلقة على الفهرس الذي كان يتدرج خلاله الاستدعاء الذاتي، وحول الحالة الأساسية إلى شرط خروج الحلقة.

مكدس الاستدعاءات لمضرب(4): كل استدعاء يدفع إطارًا للأسفل نحو الحالة الأساسية مضرب(1)=1، ثم ينفك المكدس، مُعيدًا 2 = 2 × 1، و6 = 3 × 2 و24 = 4 × 6
يستخدم الاستدعاء الذاتي مكدس الاستدعاءات: تدفع الاستدعاءات أطرًا للأسفل نحو الحالة الأساسية، ثم تنفك العودات للأعلى

المخاطر

  • الاستدعاء الذاتي اللانهائي إذا تم تفادي الحالة الأساسية — يتوقف البرنامج بسبب انفجار المكدس.
  • استخدام ذاكرة مرتفع للاستدعاءات العميقة.
  • بطيء إذا كان يعيد العمل (فيبوناتسي بدائي أسّي — استخدم حلقة أو التخزين المؤقت).
استكشف

تتراجع العودية من الأوراق صعوداً

مرر عبر fib(4) بالترتيب الذي تنتهي فيه المكالمات فعليًا: تتحلل الأوراق (الحالات الأساسية) أولاً، ثم يجمع كل أب أبنائه. لاحظ أن fib(2) يتم حسابه مرتين — هذا العمل المكرر هو السبب في بطء العودية البدائية.

مفردات تدريب
English العربية
recursion/rɪˈkɜːʃn/ التكرار الذاتي
call stack/kɔːl stæk/ مكدس الاستدعاء
base case/beɪs keɪs/ الحالة الأساسية
recursive case/rɪˈkɜːsɪv keɪs/ الحالة التكرارية
factorial/fækˈtɔːrɪəl/ المضروب
divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ فرز وحل
general case/ˈdʒenərəl keɪs/ الحالة العامة
parameters/pəˈræmɪtəz/ المُعاملات
stack overflow/stæk ˌəʊvəˈfləʊ/ تجاوز سعة المكدس
memoisation/ˌmeməʊaɪˈzeɪʃn/ الترميز التذكاري
local variables/ˈləʊkl ˈveərɪəblz/ المتغيرات المحلية
stack frame/stæk freɪm/ إطار المكدس
return address/rɪˈtɜːn əˈdres/ عنوان الإرجاع
19.2

ما يفعله المترجم للكود الاستثنائي

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

مكدس الاستدعاء لـ factorial(3): كل استدعاء ينتظر، ثم يعود بالترتيب العكسي
مكدس الاستدعاءات لـ factorial(3): كل استدعاء ينتظر ثم يُعيد النتيجة بالعكس

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

«اشرح لماذا يُعد المكدس مناسبًا لتنفيذ الاستدعاء الذاتي» (ثلاث درجات). يجب على كل استدعاء ذاتي حفظ عنوان العودة ومعاملاته ومتغيراته المحلية، وتكتمل الاستدعاءات بترتيب معاكس لترتيب إجرائها (فآخر استدعاء يُجرى هو أول استدعاء ينتهي)، وهذا يطابق تمامًا سلوك المكدس آخر داخل، أول خارج: كل استدعاء جديد يدفع إطارًا إلى المكدس، وكل عودة تسحب أحدث إطار، فتستعيد حالة المستدعي وتحدد له موضع استئناف التنفيذ. وهذه مهمة المترجم عند ترجمة الشيفرة ذات الاستدعاء الذاتي: فهو يولّد تعليمات دفع إطار إلى المكدس عند كل استدعاء وسحبه عند كل عودة، وتتتابع إزالة الإطارات مع عودة النتائج.

19.2

التعريفات التي يقبلها المصحح

تُصنّف أسئلة التعريف بناءً على صياغة ثابتة. احفظ هذه التعريفات بدقة، وقدم إجابة واحدة فقط.

مصطلح تعريف
البحث الخطي فحص كل عنصر بالتتابع من البداية حتى العثور على الهدف أو الوصول إلى النهاية
البحث الثنائي مقارنة الهدف بشكل متكرر مع العنصر الأوسط لقائمة مرتبة والتخلص من النصف الذي لا يمكن أن يحتوي عليه
ترتيب الفقاعات المرور المتكرر عبر القائمة، وتبادل العناصر المتجاورة التي تقع في الترتيب الخاطئ، حتى لا تقوم أي مرور بتبادلات
ترتيب الإدراج أخذ كل عنصر بالتتابع وإدخاله في مكانه الصحيح بين العناصر المرتبة مسبقًا
نوع البيانات المجرد مجموعة من البيانات والعمليات التي يمكن تنفيذها عليها، يتم تعريفها بشكل مستقل عن طريقة تخزينها
مكدس هيكل الأخير دخولاً، الأول خروجاً مع الدفع والرفع في الأعلى
طابور هيكل الأول دخولاً، الأول خروجاً مع إضافة العناصر من الخلف وإزالتها من الأمام
قائمة مربوطة تسلسل من العقد، كل منها يحمل بيانات ومؤشرًا للعقدة التالية، مع مؤشر بداية
شجرة ثنائية عقد تحمل كل منها بيانات ومؤشرات إلى شجرة فرعية يسرى لقيم أصغر وشجرة فرعية يمنى لقيم أكبر
ترميز بي-أو طريقة لتصنيف الوقت (أو الذاكرة) الذي يحتاجه خوارزمية بناءً على نموها مع حجم المدخلات
الاستدعاء الذاتي إجراء يستدعي نفسه بنسخة أصغر من المشكلة حتى توقف حالتان أساسية الاستدعاءات
الحالة الأساسية الشرط الذي يعود فيه الإجراء الاستثنائي دون استدعاء نفسه
الانفك عودات سلسلة من الاستدعاءات الاستثنائية، من أعمق استدعاء إلى الأول، أثناء رفع إطارات المكدس
19.2

نصائح للامتحان

  • البحث: لا يحتاج البحث الخطي إلى ترتيب وتعقيده O($n$)؛ أما الثنائي فيحتاج إلى مصفوفة مرتبة وينصّف النطاق في كل مرة وتعقيده O($\log n$). احفظ الخوارزميتين جيدًا، بما في ذلك الحدود والراية.
  • أنواع الترتيب: الفقاعة مع علم تبديل، والإدراج بمفتاح يُزيح العناصر الأكبر يمينًا؛ كلاهما O($n^{2}$) في أسوأ الحالات، وO($n$) على البيانات المرتبة. يعتمد الأداء على عدد العناصر ومدى ترتيبها.
  • تطبيقات ADT هي إدارة مؤشرات: مؤشر علوي؛ أمامي وخلفي وعدد مع MOD؛ بداية ومؤشرات وقائمة حرة؛ جذر مع مؤشرات يسرى ويمنى. تحقق دائمًا من الامتلاء والفراغ.
  • تتعلق Big O بكيفية تغير التعقيد: ثابت، أو لوغاريتمي، أو خطي، أو تربيعي. قل «تضيف مضاعفة البيانات مقارنة واحدة» بالنسبة إلى البحث الثنائي.
  • الاستدعاء الذاتي: الحالة الأساسية، الحالة العامة، التقدم نحو الحالة الأساسية؛ مفيد عندما يتم تعريف المشكلة بدورها؛ تحتفظ المكدس بعناوين الإرجاع والمتغيرات لأن الاستدعاءات ترجع بالترتيب المعكوس. تتبع باستخدام جدول وفك الأعمدة من أعمق استدعاء.

أخطاء شائعة

  • كتابة $O(2n)$ أو $O(n^{2} + n)$: احذف الثوابت والحدود الأصغر لتحصل على $O(n)$ و$O(n^{2})$.
  • حساب فهرس الوسط على صورة $(Lower + Upper) / 2$ في تتبّع التنفيذ: تستخدم نسخة الامتحان DIV، لذا قرّب إلى الأسفل.
  • استخدام البحث الثنائي على بيانات غير مرتبة، أو على قائمة مترابطة؛ وضبط Lower ← MiddleIndex بدلاً من MiddleIndex + 1، مما يسبب حلقة لا نهائية.
  • حلقة داخلية لترتيب الفقاعة تعمل حتى نهاية المصفوفة في كل مرور، أو تبديل بدون متغير مؤقت.
  • دفع أو إضافة لا يختبران الامتلاء، أو سحب أو إزالة لا يختبران الفراغ.
  • تحريك مؤشر الأمامي للطابور بدون MOD في طابور دائري، أو اعتبار front = rear تعني دائمًا الفراغ.
  • الإدراج في قائمة مترابطة عن طريق إزاحة محتويات المصفوفة؛ تتغير فقط المؤشرات.
  • دالة ذاتية ببدون حالة أساسية، أو واحدة يكون فيها الاستدعاء الذاتي لا يصغر المشكلة.
  • تتبع استدعاء متكرر ولكن نسيان إضافة العمل المعلق أثناء العودة للأعلى.
  • الإجابة عن «لماذا يُستخدم المكدس» بعبارة «لأنه سريع»؛ السبب هو ترتيب العودة وفق مبدأ آخر داخل، أول خارج.

دروس تفاعلية حول هذا الموضوع

ا-working عليه خطوة بخطوة، مع تمارين تحقق فوري.

أوراق الامتحانات السابقة

المزيد من المواضيع في A-Level علوم الحاسوب

تسجيل الدخول أو إنشاء حساب

IGCSE, A-Level & AP