الخوارزميات البنائية

الخوارزمية البنائية هي خوارزميات تطلب بناء مثال محدد يحقق مجموعة من القواعد، أو إثبات أنه لا يوجد مثل هذا المثال.

على عكس المسائل الخوارزمية العطبيعية حيث قد تحسب أقصر مسار أو أقصى ربح في مثال، فإن المسائل البنائية تطلب المثال نفسه (على سبيل المثال “اطبع المصفوفة التي تحقق الشروط التالية…”).

لننظر إلى بعض الأمثلة لمعرفة كيفية عمل ذلك.

أمثلة لمسائل

Zero Sum Array

Zero Sum Array

لديك عدد صحيح \(N\)، اطبع \(N\) أعدادًا صحيحة مختلفة بحيث يكون مجموعها مساويًا لـ \(0\).

Solution

البناء: بدلًا من البحث عن أعداد عشوائية، يمكننا بناء الإجابة باستخدام نمط ثابت.

نعلم أنه لأي عدد \(x\)، فإن المجموع \(x + (-x) = 0\). يمكننا ببساطة إخراج أزواج من الأعداد الموجبة والسالبة. إذا كان \(N\) فرديًا، نضيف العدد \(0\) إلى المجموعة.

• \(N = 1\): 0
• \(N = 2\): 1 -1
• \(N = 3\): 1 -1 0
• \(N = 4\): 1 -1 2 -2 0

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n / 2; i++) {
        cout << i << " " << -i << " ";
    }

    if (n % 2 != 0) cout << 0;
    cout << endl;
}

Anti-Identity Permutation

Anti-Identity Permutation

أنشئ تبديلًا بطول \(N\) (بترقيم يبدأ من 1) بحيث لكل موقع \(i\)، يكون \(A[i] \neq i\).

على سبيل المثال، إذا كان \(N=3\)، فإن [1, 2, 3] غير صالح لأن \(1\) في الموقع \(1\). ولكن المصفوفة [2, 3, 1] صالحة.

Solution

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

تصبح الصيغة عندئذٍ \(A[i] = i+1\)، لكل \(i < N\) و \(A[N] = 1\).

• \(N=3\): 2 3 1
• \(N=4\): 2 3 4 1
• \(N=5\): 2 3 4 5 1

ملاحظة: عندما يكون \(N=1\)، فمن المستحيل وضع \(1\) في أي مكان غير الموقع \(1\)، لذا لا يوجد حل.

Chessboard Domineering

Chessboard Domineering

لديك رقعة شطرنج طبيعية بحجم \(8 \times 8\) مع إزالة زاويتين متقابلتين (ليتبقى 62 مربعًا). أوجد طريقة لتغطية الرقعة بالكامل بقطع دومينو بحجم \(2 \times 1\)؟

Solution

لقد خدعناك!

أحيانًا يكون “البناء” هو إثبات أن المهمة مستحيلة.

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

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

كيف نحل المسائل البنائية؟

الآن بعد أن رأيت طبيعة هذه المسائل، إليك كيفية التعامل معها. على عكس نظرية الرسوم البيانية أو DP، لا تستخدم خوارزميات مباشرة مثل Dijkstra. بل تعتمد على المنطق والملاحظة.

جرّب قيمًا صغيرة لـ N

هذه أهم استراتيجية. إذا طلبت المسألة حلًا لـ \(N=100000\)، فلا تحاول تخمين معادلة معقدة مباشرة. أحضر قلمًا وحلها للحالات \(N=1, 2, 3, 4\). كثير من المسائل البنائية تُحل باكتشاف نمط في الحالات الصغيرة.

الفردية والزوجية

تعتمد العديد من البُنى على خصائص الأعداد الزوجية والفردية (فردي + فريدي = زوجي).

• مثال: إذا سألت مسألة “هل يمكنك جعل الرقمين التاليين متساويين بأضافة 2؟”، فتحقق من الفردية والزوجية. إذا كان أحد العددين فرديًا والآخر زوجيًا، فلن يتساويا أبدًا، لأن إضافة 2 لا تغيّر الفردية.

مبدأ صندوق الحمام

إذا كان لديك \(N\) عنصر و\(N-1\) صناديق، فلا بد أن يحتوي صندوق واحد على عنصرين على الأقل. يُستخدم هذا كثيرًا لإثبات وجود حل (أو لإثبات الاستحالة).

البناء بالاستقراء

اسأل نفسك: إذا كان لديّ حل صحيح لـ \(N\)، فهل يمكنني بسهولة إضافة عنصر واحد لجعله صحيحًا لـ \(N+1\)؟ هذا يسمح لك ببناء الإجابة تدريجيًا.

تحقق من “أسوأ حالة”

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

• المصفوفة المرتبة 1, 2, 3...
• المصفوفة المرتبة عكسيًا N, N-1, N-2...
• جميعها أصفار أو جميعها آحاد.