كيفية بكالوريوس (البحث الثنائي) في CS

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

معظم الناس عندما يواجهون تحديًا غير معروف ، فإنهم يميلون إلى الرعب ، وهذا أمر طبيعي ولكن نأمل أن تقرأ بعد أن تقرأ هذا عندما تكون في مواجهة تحدٍ جديد.

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

الخطوة 1 - تقييم معرفتك الحالية حول هذا الموضوع.

عندما تواجه مشكلة ، التراجع وتحليل المشكلة.

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

الاستجواب التفصيلي هو أسلوب رائع لبدء عملية التفكير.

الخطوة 2 - رسم / كتابة المشكلة.

هل سمعت أو رأيت هذا الاقتباس الشهير الذي يدور حول "لإنجاز أشياء عظيمة ، يجب علينا ألا نتصرف فحسب ، بل نحلم أيضًا ، لا نخطط فحسب بل نؤمن أيضًا". يساعد وجود صورة أو رسم أو كتابة المشكلة في فهم بعض الاستراتيجيات والتوصل إليها.

الخطوة 3 - التحدث بها.

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

الخطوة 4 - كسرها.

تمامًا كما نفعل الآن ، خذ خطوة بخطوة.

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

دعنا ننتقل إلى ذلك

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

التكرار والإعادة

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

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

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

إن إجراء العودية الشائعة الذي نقوم به على أساسنا اليومي هو عندما يقوم عدد من الصناديق بحساب عدد من الصناديق تبدأ من البداية إلى النهاية ، ولكن من أجل التحقق من أنك تحصي أنت تعد أيضًا من النهاية إلى البداية.

اختيار نوع

فكرة هذه الخوارزمية هي العثور على أصغر عنصر في القائمة غير المصنفة وتبديلها في بداية القائمة المصنفة.

دعنا الزائفة:

تخيل أنك انتهيت للتو من غسل الملابس ، وبينما تطوي ملابسك ، وجدت 8 أزواج مختلفة من الجوارب بأحجام مختلفة من 1 إلى 12 ولكن تجدها غير مصنفة [5 ، 7 ، 1 ، 8 ، 5 ، 2 ، 12] في جميع أنحاء منزلك أرضية غرفة النوم ، والآن تحتاج إلى استلامها حتى تتمكن من وضعها في خزانتك. عليك أن تبدأ بالجورب الأول الذي أمامك. الجورب الأول الذي التقطته كان الجورب رقم 5 وافتراض أن الجورب الأول الذي حصلت عليه مصنَّف ، انظر على الأرض لأصغر حجم جوارب تراه أمامك ، في هذه الحالة ، رقم 1 ، قارن الآن إذا كان الجورب الأول كنت قد التقطت أكبر أو أقل من الرقم الذي كان لديك من قبل ، إذا كان الرقم أقل ، فتبادل أصغر قيمة للحجم مع الجورب الأول الذي التقطته. بمجرد الانتهاء من ذلك ، تحصل على الجورب التالي أمامك 7 ، تحقق مرة أخرى من أصغر حجم الجوارب الذي تراه أمامك ، والذي سيكون 2 ، هو 2 <7؟ نعم! لذا قم بتبديل أصغر حجم للحجم الحالي الذي تتم مقارنته [1 ، 2 ، 5 ، 8 ، 5 ، 12]. استمر بالتجوال خلال الجوارب حتى يتم فرز كل شيء. تذكر أن قائمة الفرز بترتيب تصاعدي ، مما يعني بقاء الأرقام الأدنى على الجانب الأيسر وأرقام أكبر في الجانب الأيمن.

فقاعة الفرز

فكرة هذه الخوارزمية هي نقل القيم الأكبر عمومًا نحو اليمين وأدنى القيم عمومًا نحو اليسار.

دعنا الزائفة:

تخيل أنك في مكتبة وتبحث عن كتاب معين لهاري بوتر ، لكن من الصعب عليك العثور على الكتاب الذي تبحث عنه لأن رف الكتب شديد الفوضى وليس بالترتيب [1 ، 4 ، 5 ، 2] ، 6 ، 3 ، 7] ، لذلك عليك أن تقرر تنظيمها حسب حجم كل كتاب ، أصغر الكتب في اتجاه الكتب الأيسر والأكبر باتجاه اليمين.

إذاً نظرتم أولاً إلى بداية رف الكتب وقارنت الكتاب الأول والثاني ببعضهم البعض ، هل 1> 4؟ لا! لذلك فهذا يعني أن العنصر الأول في تلك القائمة قد تم فرزه بالفعل ، لذلك الآن قارن الزوج التالي ، 4> 5؟ لا! لذلك قارن بين الزوج التالي ، هل 5> 2؟ نعم! لذا ، يمكنك الآن مقايضتهم [1 ، 4 ، 2 ، 5 ، 6 ، 3 ، 7] ، وتواصل التفكير باستمرار حتى يتم فرز جميع الكتب [1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7].

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

تتمثل الفكرة وراء هذه الخوارزمية في إنشاء مجموعة مصنفة في مكانها ، مع إزاحة العناصر بعيدًا إذا لزم الأمر لإفساح المجال كما تذهب.

دعنا الزائفة:

إنها ليلة الجمعة وتحتفل أنت وأصدقاؤك بعطلة نهاية الأسبوع ويقضون وقتًا ممتعًا. قرر أصدقاؤك لعب أونو ، حيث أن اللعبة بدأت ستحصل على 7 بطاقات ، لأنك تقوم بتحليل البطاقات الخاصة بك لاحظت أنها ليست بالترتيب [5 ، 7 ، 2 ، 4 ، 3 ، 8 ، 9] ، لإعادة ترتيب البطاقات التي تبدأها من البداية ، سنقوم أولاً بتعيين البطاقة كما لو تم فرزها ، والآن انظر إلى البطاقة التي لم يتم فرزها التالية ، وأدخلها الآن إلى الجزء الذي تم فرزه عن طريق تحويل العدد المطلوب من البطاقات.

البحث الخطي

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

دعنا الزائفة:

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

بحث ثنائي

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

دعنا الزائفة:

إنك تبحث عن تعريف كلمة ما في القاموس ، يتم دومًا تصنيف القاموس حسب الترتيب الأبجدي ، دعنا نقول أنك تبحث عن كلمة Rainbow ، بحيث تذهب في منتصف القاموس وستحصل على الحرف G ، إذا كانت R (والذي هو الحرف الأول من الكلمة التي نبحث عنها) هو <(أقل) من G نذهب إلى اليسار وإذا كنا> (أكبر) فإننا نتحرك يمينًا. في هذه الحالة تكون أكبر ، لذلك نتجاهل الجانب الأيسر ونذهب نحو منتصف الجزء الأيمن ونكرر العملية حتى تجد كلمة RAINBOW.

ملخص

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

موارد متابعة كبيرة:
 Ones and Zeros ، الأبطال السحريون الذين يذهبون إلى العالم
 معادلات جيثب العودية المعقدة
 جيثب الترميز مقابلة الجامعة
 تكسير مقابلة الترميز ، الطبعة السادسة
 راجع تحليل خوارزمية "جعل المدرسة"
 اقرأ مقال Interview Cake حول الفكرة وراء ترميز O الكبير
 اقرأ مقال Interview Cake حول اللوغاريتمات والبحث الثنائي
شاهد فيديو الخوارزميات المتكرّرة لـ HackerRank ، فيديو خوارزمية البحث الثنائي ، والفيديو التدوين الكبير O
شاهد فيديو العودية القديم الخاص بجامعة هارفارد ، ومقاطع الفيديو العودية الجديدة ، ومقاطع فيديو الإطارات المكدسة ، ومقاطع الفيديو ذات البحث الخطي ، ومقاطع الفيديو ذات البحث الثنائي ، ومقاطع الفيديو المقننة ، ومقاطع الفيديو المعقدة
تم إنشاء العنوان بواسطة TJ King
 رمز اليقطين
 نقطة دروس