خوارزميات المحكمة الخاصة بلبنان

low_bound و upper_bound وظائف بحث ثنائية مضمنة.

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

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

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

أمثلة:
نبسب ؛ المتجه a = {0، 1، 3، 5، 7} ؛ متجه :: مكرره ؛ it = lower_bound (a.begin () ، a.end () ، 4) ؛ // * هو == 5 it = low_bound (a.begin () ، a.end () ، 5) ؛ // * هو == 5 it = low_bound (a.begin () ، a.end () ، 8) ؛ // it == a.end () it = upper_bound (a.begin ()، a.end ()، 4) ؛ // * هو == 5 it = upper_bound (a.begin ()، a.end ()، 5) ؛ // * هو == 7 it = upper_bound (a.begin () ، a.end () ، -1) ؛ // * هو == 0 // عن طريق طرح التكرارات ، يمكنك الحصول على فهرس العنصر الذي تم العثور عليه int ind = lower_bound (a.begin () ، a.end () ، 4) - a.begin () ؛ // ind == 3 // تحتاج إلى استخدام طرق بدلاً من وظائف للمجموعات والمجموعات المماثلة ضبط s {1، 3، 5} ؛ ضبط :: iterator sit؛ الجلوس = s.lower_bound (3) ؛ // * الجلوس == 3 الجلوس = s.upper_bound (3) ؛ // * الجلوس == 5 نبسب ؛

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

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

أمثلة:
نبسب ؛ المتجه a = {3، 3، 3، 2، 3، 3، 1، 1، 4، 5، 5} ؛ فريد (a.begin () ، a.end ()) ؛ // a = [3، 2، 3، 1، 4، 5،؟،؟،؟،؟،؟] // استخدام الوظيفة الفريدة مناسب للقيام به // مجموعة مساعدة لتنسيق الضغط أ = {235 ، 10 ، 41 ، 10 ، 41 ، 41 ، 235 ، 500 ، 500} ؛ فرز (a.begin () ، a.end ()) ؛ // أ = [10 ، 10 ، 41 ، 41 ، 41 ، 235 ، 235 ، 500 ، 500] a.resize (فريد (a.begin () ، a.end ()) - a.begin ()) ؛ // أ = [10 ، 41 ، 235 ، 500] نبسب ؛

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

أمثلة: // يجب فرز مصفوفات المصدر المتجه a = {1، 3، 5، 7} ؛ المتجه b = {2، 4، 6} ؛ // بحاجة إلى أن تكون الوجهة كبيرة بما يكفي ناقلات ج (7) ؛ دمج (a.begin () ، a.end () ، b.begin () ، b.end () ، c.begin ()) ؛ // ج = [1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7] // يمكن تكرار العناصر أ = {1، 2، 4، 4} ؛ ب = {2 ، 3 ، 3 ، 3 ، 4 ، 4} ؛ c.resize (10) ؛ دمج (a.begin () ، a.end () ، b.begin () ، b.end () ، c.begin ()) ؛ // ج = [1 ، 2 ، 2 ، 3 ، 3 ، 3 ، 4 ، 4 ، 4 ، 4] على & nbsp ؛ هذه الوظيفة مفيدة جدًا في سياق فرز الدمج.

nth_element هي وظيفة تسمح لك بالعثور على العنصر n في المصفوفة بترتيب مرتب في الوقت الخطي.
تأخذ الوظيفة الطرف الأيسر من المصفوفة ، ومكررًا إلى الموضع الذي سيتم العثور على قيمته بالترتيب الفرز ، والنهاية اليمنى للمصفوفة.
بعد تطبيق الوظيفة ، سيتم تحديد القيمة المطلوبة في المكان الذي يشير إليه المكرر ، بينما تحصل القيم المتبقية على ترتيب فوضوي ، ولكن على يسار الرقم n ، لن تكون هناك قيم أكثر من ذلك ، و إلى اليمين لا أقل. بمعنى ، يجب أن نفهم أن هذه الوظيفة تدمر الترتيب الأصلي للعناصر.
يمكنك قراءة المزيد في الوثائق (https://www.cplusplus.com/reference/algorithm/nth_element/).

مثال: المتجه a = {4 ، 0 ، 3 ، 9 ، 2 ، 1 ، 8 ، 5 ، 6 ، 7} ؛ // ابحث عن عنصر في الفهرس 4 // انتبه لترتيب الحجج nth_element (a.begin ()، a.begin () + 4، a.end ()) ؛ // a = [# ، # ، # ، # ، 4 ، $ ، $ ، $ ، $ ، $] // حيث # & lt ؛ = 4 و 4 & lt ؛ = $ نبسب ؛

التقليب في الطول n هو مجموعة مرتبة بدون تكرار الأرقام 1 ، 2 ، ... ، n. على سبيل المثال ، [3 ، 1 ، 2] و [5 ، 4 ، 3 ، 2 ، 1] هي تبديلات ، لكن [1 ، 2 ، 1 ، 3] و [1 ، 2 ، 4] ليست كذلك.

إذا تم تقليل المهمة إلى حقيقة أنه من الضروري التكرار على جميع التباديل للطول n ، فيمكنك استخدام آلية ملائمة في C ++ ، والتي تسمى "next_permutation".

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

لاستخدام next_permutation ، تحتاج إلى تضمين مكتبة الخوارزمية (على سبيل المثال ، اكتب #include & lt؛ algorithm & gt؛ في بداية البرنامج)

أمثلة: ناقلات arr ؛ arr = {1، 2، 3} ؛ // المصفوفة هي [1 ، 2 ، 3] next_permutation (arr.begin ()، arr.end ()) ، // قم بتمرير المصفوفة بأكملها إلى الوظيفة // المصفوفة هي الآن [1 ، 3 ، 2] arr = {2، 3، 1} ؛ // المصفوفة هي [2 ، 3 ، 1] next_permutation (arr.begin ()، arr.end ()) ، // قم بتمرير المصفوفة بأكملها إلى الوظيفة // المصفوفة هي الآن [3 ، 1 ، 2] next_permutation (arr.begin () + 1، arr.begin () + 3) ، // من الممكن تطبيق دالة على جزء من مصفوفة ، ولكن نادرًا ما تكون هناك حاجة إلى ذلك عمليًا // المصفوفة هي الآن [3 ، 2 ، 1]
في هذه الحالة ، تحتوي الوظيفة على قيمة إرجاع منطقية تكون صحيحة إذا تم إنشاء التقليب التالي وخطأ إذا لم يكن هناك تالي (الحالة التي يتم فيها تمرير الحد الأقصى للتبديل في الترتيب المعجمي إلى الوظيفة).
هذا يجعل من الممكن استخدام الوظيفة في حلقة ، مما سيسمح لنا بالتكرار عبر جميع التباديل مرة واحدة. بسبب الفهرسة 0 ، من الناحية العملية ، غالبًا ما يكون العمل مع تبديل الأرقام من 0 إلى n - 1 أكثر ملاءمة ، على الرغم من أن التقليب يحتوي رسميًا على أرقام من 1 إلى n. لكن لحسن الحظ ، هذا لا يؤدي إلى تراكبات إضافية في الكود ، لأن تم تكييف وظيفة next_permutation مع التباديل ذي الصفر المفهرس (وحتى العناصر المكررة في المصفوفة ، ولكن يمكنك معرفة المزيد بنفسك).

بشكل عام ، يبدو رمز التكرار على جميع التباديل كما يلي: & nbsp؛ إنتن. // حجم التقليب متجه perm (n) ؛ // perm هي اختصار لـ "التقليب" ، أي "التقليب" لـ (int i = 0 ؛ i & lt ؛ n ؛ i ++) بيرم [i] = أنا ؛ // تهيئة التقليب الأولي 0 ، 1 ، ... ، ن - 1 يفعل { // داخل الحلقة نقوم بمعالجة التقليب الحالي } while (next_permutation (perm.begin ()، perm.end ())) ؛ // إذا لم يكن هناك تبديل تالٍ ، فقم بإنهاء الحلقة

يعمل هذا الرمز في O (n! * f (n)) ، حيث f (n) هو الوقت الذي تستغرقه في معالجة تبديل واحد معين.