المحاكاة

مشاكل المحاكاة تتعلق بتقليد عمليات حقيقية أو منطقية خطوة بخطوة. يُطلب منك أن “تحاكي” ما يحدث — تمامًا مثل تشغيل برنامج صغير داخل برنامجك!

ماذا تعني المحاكاة؟

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

لست بحاجة لخوارزمية معقدة — فقط قم بتكرار ما يحدث عادةً باستخدام الحلقات.

هنا مثال بسيط لمشكلة تُحل باستخدام المحاكاة.

Collatz conjecture

Collatz conjecture

اعتبر العملية التالية.

• ابدأ بعدد معين \(n\).

• في كل خطوة:

  • إذا كان \(n\) زوجيًا، استبدله بـ \(n/2\).
  • إذا كان \(n\) فرديًا، استبدله بـ \(3n+1\).

• اطبع عدد الخطوات التي استغرقتها العملية قبل أن يصبح \(n\) مساويًا لـ 1.

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

Solution

#include <iostream>
using namespace std;

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

    int steps = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3*n + 1;
        }
        steps++;
    }

    cout << steps << "\n";
    return 0;
}

If n = 3, the program goes like this:

step	n
0	3
1	10
2	5
3	16
4	8
5	4
6	2
7	1

لذا الإجابة هي 7.

متى نستخدم المحاكاة

المحاكاة ممتازة عندما:

• تعطيك المشكلة قائمة خطوات أو أفعال مفصلة.
• لا يوجد اختصار رياضي.
• يمكنك فقط اتباع العملية مباشرة.

أمثلة شائعة:

• الألعاب (مثل tic-tac-toe، snake، إلخ)
• التحرك على شبكة (روبوتات، سيارات، أشخاص يمشون)
• التحويلات النصية (تحرير نص، تدوير)
• إدارة العناصر (طوابير، مكدسات، أو مهام مع الوقت)

نمط المحاكاة

معظم مشاكل المحاكاة تتبع نفس النمط:

initialize variables
while (there are still actions left) {
    read next action
    update variables according to rules
}
print final result

أنت basically تقوم “بتشغيل” القواعد خطوة بخطوة.

أمثلة مسائل

Robot on a grid

Robot on a grid

روبوت يبدأ عند \((0, 0)\). يستقبل سلسلة من الحركات مكونة من N, S, E, W. اطبع إحداثياته النهائية.

Solution

#include <iostream>
#include <string>
using namespace std;

int main() {
    string moves;
    cin >> moves;

    int x = 0, y = 0;
    for (char c : moves) {
        if (c == 'N') y++;
        else if (c == 'S') y--;
        else if (c == 'E') x++;
        else if (c == 'W') x--;
    }
    cout << x << " " << y;
}

إذا كان الإدخال NNEEWS، ينتهي الروبوت عند (1, 1).

Game simulation

Game simulation

يوجد عدة أبطال في اللعبة، ولكلٍّ منهم قوة خاصة به. في كل ثانية، يقوم أضعف بطل، A، بإلحاق ضرر بأقوى بطل، B، ويُقلّل من قوة B بمقدار قوة A. تنتهي اللعبة عندما تصل قوة أحد الأبطال إلى 0. اطبع عدد الثواني التي استمرت فيها اللعبة.

Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> strength(n);
    for (int &x : strength) cin >> x;

    int seconds = 0;
    while (true) {
        sort(strength.begin(), strength.end());
        if (strength[0] == 0) break;
        strength[n-1] -= strength[0];
        seconds++;
    }
    cout << seconds;
}

هذه تحاكي العملية بالكامل كما هي موصوفة.

Noteملحوظة

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

نصائح لمشاكل المحاكاة

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

نصيحة أداء

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

على سبيل المثال:

• إذا كانت العملية تتكرر بعد عدد معين من الخطوات، استخدم الرياضيات لتجاوز الدورات.
• إذا لم يعد الناتج يتغير بعد فترة، توقف مبكرًا.

المزايا

• مباشرة جدًا — لا حاجة لخوارزميات معقدة
• سهلة التنفيذ والفهم
• تعمل مع أي عملية تعتمد على قواعد تقريبًا

العيوب

• قد تكون بطيئة للمدخلات الكبيرة
• سهل ارتكاب أخطاء صغيرة عند اتباع العديد من الخطوات
• التصحيح قد يستغرق وقتًا إذا لم تطبع النتائج الوسيطة

خلاصة سريعة

• المحاكاة تعني تقليد العملية خطوة بخطوة.
• ممتازة للمشاكل التي تصف قواعد أو أفعالًا دقيقة.
• ركّز على الحلقات، الشرطيات، وتحديث المتغيرات.
• تحقق دائمًا من أمثلة صغيرة يدويًا.
• عندما تكون بطيئة جدًا — ابحث عن أنماط متكررة!