المكتبة العربية لعلوم الحاسوب
مرحباً بالخوارزميات › التجزئة 8 / 19 السابق التالي

تمارين

مراجعة المفاهيم

البحث بعد تصادم التجزئة

جدول تجزئة فيه 5 دلاء ويستخدم دالة التجزئة h(x)=x mod 5h(x)=x \bmod 5. وعند حدوث تصادم، تُوضع العناصر الواحد تلو الآخر في قائمة داخل ذلك الدلو. أدخل [1, 6, 11, 7] بالترتيب:

  1. اكتب محتويات الدلاء من 0 إلى 4.
  2. عند البحث عن 6، أي دلو يُفحص أولاً، وأي العناصر تُفحص بالترتيب؟
  3. استناداً إلى محتويات الدلاء من السؤال 1، هل تطمس الإدخالات اللاحقة الإدخالات السابقة؟ اشرح باستخدام طريقة حل التصادم هذه.

الإجابة

  1. لأن 1 mod 5=6 mod 5=11 mod 5=11\bmod5=6\bmod5=11\bmod5=1، بينما 7 mod 5=27\bmod5=2، تكون الدلاء كما يلي:

    0: []
1: [1, 6, 11]
2: [7]
3: []
4: []

  2. يذهب البحث عن 6 أولاً إلى الدلو 1، ثم يقارن 1 و6 بالترتيب. ويُعثر على الهدف في المقارنة الثانية.

  3. تساوي قيم التجزئة يعني فقط أن العناصر تدخل الدلو نفسه، لا أن العناصر متساوية. فالسلسلة المنفصلة (separate chaining) تُبقي جميع العناصر المتصادمة في الدلو وتقارنها واحداً تلو الآخر أثناء البحث، لذا لا يطمس أي من 1 و6 و11 الآخر.

إلى أين تذهب العناصر بعد توسّع جدول التجزئة؟

جدول تجزئة يستخدم السلسلة المنفصلة كان في الأصل فيه 5 دلاء ودالة تجزئة h(x)=x mod 5h(x)=x\bmod5. والمفاتيح [1, 6, 11] كلها في الدلو 1.

وقد وُسّع الجدول الآن ليصبح فيه 7 دلاء، وأصبحت دالة التجزئة h(x)=x mod 7h(x)=x\bmod7:

  1. احسب رقم الدلو الجديد لكل من 1 و6 و11.
  2. أي الدلاء تحتوي على عناصر بعد التوسّع؟
  3. أثناء التوسّع، هل يمكن نسخ القائمة من الدلو القديم 1 كما هي إلى الدلو الجديد 1؟ اشرح باستخدام نتائج السؤالين 1 و2.

الإجابة

  1. أرقام الدلاء الجديدة هي:

    • 1 mod 7=11\bmod7=1;
    • 6 mod 7=66\bmod7=6;
    • 11 mod 7=411\bmod7=4.

  2. الدلو 1 يخزّن 1، والدلو 4 يخزّن 11، والدلو 6 يخزّن 6. ولم تعد المفاتيح الثلاثة مزدحمة في الدلو نفسه.

  3. لا يمكن نسخ القائمة كما هي. فرقم الدلو يُحسب بأخذ باقي قسمة المفتاح على عدد الدلاء. وعندما يتغير عدد الدلاء من 5 إلى 7، قد يتغير رقم دلو المفتاح، لذا يجب إعادة حساب موضع كل مفتاح. ولو نُسخ الدلو القديم 1 دون تغيير، لذهبت عمليات البحث اللاحقة باستخدام الصيغة الجديدة إلى الدلو 6 بحثاً عن 6 وإلى الدلو 4 بحثاً عن 11 ولما عثرت عليهما.

هل يمكن العثور على 11 بعد حذف 6؟

جدول تجزئة فيه 5 مواضع بفهارس 0–4 ويستخدم دالة التجزئة h(x)=x mod 5h(x)=x\bmod5. وعند حدوث تصادم، يبحث يميناً انطلاقاً من الفهرس الذي تنتجه دالة التجزئة عن أول موضع فارغ.

أدخل [1, 6, 11] بالترتيب:

  1. عند أي فهرس يُخزَّن كل عدد في النهاية؟
  2. عند البحث عن 11، أي الفهارس تُفحص بالترتيب؟
  3. لنفترض أن حذف 6 يغيّر موضعه مباشرةً إلى «موضع فارغ غير مستخدم»، وأن البحث يتوقف كلما وصل إلى موضع فارغ. فماذا يحدث عند البحث عن 11 بعد ذلك؟ هل نتيجة هذا البحث صحيحة؟ وإن وُجدت مشكلة، فكيف يمكن تجنبها؟

الإجابة

  1. يُخزَّن العدد 1 عند الفهرس 1. ويُربط العدد 6 أيضاً بالفهرس 1، لذا يُخزَّن بعد التصادم عند الفهرس 2. ويبدأ العدد 11 أيضاً من الفهرس 1، ويتجاوز الفهرس 1 و2 المشغولين، ثم يُخزَّن في النهاية عند الفهرس 3.

  2. يفحص البحث عن 11 الفهارس 1, 2, 3 بالترتيب ويجده عند الفهرس 3.

  3. إذا تغيّر معنى الفهرس 2 ليصبح «غير مستخدم قط»، فإن البحث عن 11 يفحص الفهرس 1 ثم يتوقف عند الفهرس 2، مستنتجاً خطأً أن 11 غير موجود. وينبغي أن يترك الحذف علامة «محذوف». والبحث الذي يصل إلى هذه العلامة يواصل إلى الفهرس التالي (بالالتفاف من الفهرس 4 إلى الفهرس 0)، في حين قد يعيد إدخال لاحق استخدام الموضع.

تمارين برمجية

مقارنة عدد الأحرف في سلسلتين نصيتين

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

حدّد ما إذا كانت السلسلة المعاد ترتيبها يمكن أن تشكّل t. أعد true إن أمكن وfalse خلاف ذلك. استخدم جدول تجزئة لتسجيل عدد مرات ظهور كل حرف. ولا ترتّب الأحرف في السلسلتين.

تلميحات

  1. إذا اختلف طول السلسلتين، فلا يمكن أن تحتويا كل حرف بالعدد نفسه من المرات
  2. استخدم جدول تجزئة لتسجيل عدد كل حرف؛ وزد العدد المقابل أثناء مسح s
  3. أنقص العدد المقابل أثناء مسح t؛ ولا تحتوي السلسلتان كل حرف بالعدد نفسه من المرات إلا إذا كان كل عدد مساوياً 0 في النهاية

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي الشجرة