لعبة البحث الثنائي
مقدمة
تقوم فكرة اللعبة علي ايصال واحد من مفاهيم عملية البحث التي يقوم بها الحاسوب، عن طريق فهم خوارزمية البحث الثنائي.
الأهداف
- التعرف على مفهوم "عملية البحث" و إدراك أهمية هذه العملية في تحقيق البرنامج لأهدافه.
- التعرف على كيفية قيام الحاسوب بعملية البحث.
- التعرف علي الفرق بين القيمة والترتيب.
- استخدام قيمة التعاون بين المتدربين في الوصول للنتيجة النهائية من اللعبة.
المساعدات المطلوبة
- أوراق مرقمة ومقسمة بعدد اللاعبين متتابعين في الترقيم أو غير متتابعين.
- ورقة بها دليل البحث.
شرح اللعبة
هي خوارزمية تستخدم لإيجاد مدخلة في مصفوفة مرتبة تصاعديا أو تنازليا سواء كانت أرقام أو نصوص ولكن الأن سوف يتم تطبيقها علي أرقام فقط.ولان العناصر مرتبة فهنا يمكن الاستفادة من ذلك في تقسيم قائمة العناصر إلى نصفين فيتم تجاهل أحدهما واعتماد الأخرى في عملية البحث بناء على مقارنه هل العنصر الموجود في وسط القائمة أكبر من العنصر الذي نبحث عنه ام اصغر ام يساويه ؟ وتبدا عملية البحث من العنصر الذي يقع في وسط المصفوفة فاذا كان العنصر الذي نبحث عنه يساوي العنصر الذي في الوسط تنتهي عملية البحث اما إذا كانت القيمتان مختلفتان ستقوم الخوارزمية باجراء فحص جديد فاذا كان العنصر الذي نبحث عنه أكبر من العنصر الذي في الوسط سيتم البحث في الجزء الايمن من المصفوفة ويستثنى من البحث الجزء الأيسر اما إذا كان العنصر الذي نبحث عنه اصغر سيتم البحث في الجزء الأيسر من المصفوفة ويستثنى من البحث الجزء الايمن.في كل مرحلة, تقارن الخوارزمية بين قيمة العنصر المدخل (المراد البحث عنه في المصفوفة) مع قيمة العنصر الأوسط في المصفوفة. إذا كانت القيمتان متساويتين, إذن تم العثور على على عنصر مطابق, ويتم ارجاع مؤشر له, أو موقعه في المصفوفة. واذا لما تكن القيمتان متساويتين, إذا كانت قيمة العنصر المدخل اصغر من قيمة العنصر الأوسط, تكرر الخوارزمة هذه العملية على المصفوفة الفرعية على يسار العنصر الأوسط, أو إذا كانت قيمة العنصر المدخل أكبر, على المصفوفة الفرعية على اليمين. إذا تم تقليص المصفوفة لتصبح فارغة, لم يتم العثور على عنصر مطابق, ويتم ارجاع قيمة استثنائية "غير موجود".وسيتم تقسيم الجزء الايمن أو الأيسر إلى نصفين ويتم تكرار عملية البحث حتى الحصول على مصفوفة تتكون من خانة واحدة قيمتها مساوية للعنصر الذي نبحث عنه أو مختلفة عنه وهنا نكون وصلنا إلى النتيجة النهائية والتي تتمثل في تحديد مكان العنصر الذي نبحث عنه عن طريق تحديد رقم الفهرس وهو مكان العنصر . ايجابيات هذه الخوارزمية اننا نقلص عدد عناصر المصفوفة في كل تكرار إلى النصف . سلبياتها انها أكثر تعقيدا من خوارزمية البحث الخطي وتشترط ان تكون العناصر مرتبة عند البحث.
- تتطلب هذه اللعبة من الطلاب اتباع خطوات اللعبة للبحث عن عنصر معين داخل مصفوفة المتدربين، و قد تختلف طريقة البحث في كل مرة (بالترتيب ، بدون ترتيب ، البحث عن قيمة غير موجودة ، البحث عن قيمة مكررة ... الخ) . هذه التعليمات هي أوامر بسيطة يجب أن تنفذ بدقة و طبقا للتتابع المحدد في الورقة حتى نصل إلى نتيجة البحث المطلوبة. و تأخذ هذه الأوامر احد الأشكال التالية:
- يتم توزيع الأرقام علي المتدربين.
- يتم ايقاف المتدربين في شكل صف مرة مرتب للتعبير عن شكل المصفوفة.
- يتم اعطاء متدرب دليل البحث ليقوم بعملية البحث.
- تقوم فكرة البحث الثنائي على تقسيم المصفوفة إلى نصفين واستبعاد النصف الذي لا ينتمي إليه المفتاح key الذي نبحث عنه، كيف ذلك؟
عن طريق تحديد العنصر الذي يقع في منتصف هذه المصفوفة، ثم نقارن هذا العنصر مع المفتاح الذي نبحث عنه كالتالي (تذكر أن مصفوفتنا مرتبة تصاعدياً أو تنازلياً):
- إذا كان يساويه نكون قد وجدنا العنصر الذي نبحث عنه.
- إذا كانت قيمة المفتاح أقل من قيمة العنصر الأوسط في المصفوفة، إذن نحتاج أن نبحث فقط في نصف المصفوفة الأول ونستبعد البحث في نصفها الثاني.
- وفيما عدا ذلك: إذا كانت قيمة المفتاح أكبر من قيمة العنصر الأوسط في المصفوفة، إذن نحتاج أن نبحث فقط في نصف المصفوفة الثاني ونستبعد البحث في نصفها الأول.
بعد ذلك: نعتبر النصف الذي حددنا لأنفسنا البحث فيه مصفوفة قائمة بحد ذاتها، نحدد فيها الـi, j, & k (أي نقوم بتقسيمها إلى قسمين) ونطبق نفس الخطوات من 1 إلى 3 فيها، ثم نقارن المفتاح مع العنصر الأوسط الجديد، بنفس الترتيب الذي ذكر في الخطوات 1 إلى3 السابقة.
يجب على الطالب ملاحظة الأتي:
- بعد تنفيذ أي من أوامر التحرك، يتغير موقع المتدرب حامل الدليل بانتظام مع نصف طول الصف، حتي يتم الوصول اللي دليل البحث ان وجد.
- يٌلَاحظ أيضا أن تسجيل و الاحتفاظ بحالة البرنامج يتعرض لفكرة المتغيرات، التي هي أحد الأفكار المحورية في البرمجة، و قد يكون من المناسب التعرض لها في هذا التوقيت.
- يُلاحظ أيضا الفرق بين مفهوم القيمة اللتي يحملها كل متدرب ورقم ترتيبه في المصفوفة.
الخطوات
- يعطى كل متدرب ورقة بها رقم ويتم وقوفهم في شكل صف مرتب تصاعدي أو تنازلي.
- يعطي متدرب واحد دليل البحث للبحث عنه بين المتدربين.
- يشرح الميسر الارشادات الخاصة باللعبة وكيفية الوصول للنتيجة و كيفية تطبيقها.
- يطلب الميسر من كل المتدرب الذي سيقوم بتنفيذ الخطوات المنصوص عليها في وريقة الإرشادات.
- يعطي الميسر خمس دقائق للمتدربين لتنفيذ التدريب.
- إذا لم يستطيع المتدرب صاحب الدليل العثور علي النتيجة، يبلغه الميسر بالطريقة المطلوبة و يراجع معه الارشادات و يوضح له أسباب الاختلاف.