اكتشاف الدورات في المحاكاة
تخطّي الخطوات عندما تتكرر الحالة
اكتشاف الدورات في المحاكاة درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
عندما تتكرر الخطوات
تطلب بعض عمليات المحاكاة الحالة بعد عدد ضخم من الخطوات، مثل تريليون خطوة. لن تنتهي المحاكاة في الوقت المناسب إذا نفذت خطوة واحدة في كل مرة. ⏳
الحالات محدودة
إذا كان عدد الحالات الممكنة محدودًا، فلا بد أن تعود المحاكاة في النهاية إلى حالة سبق أن رأتها. ومن هناك تتكرر إلى ما لا نهاية في دورة.
كيف تبدو الدورة
للمسار ذيل يقود إلى الداخل، ثم حلقة تتكرر. يتيح اكتشاف الحلقة تجاوز مليارات الخطوات بسرعة.
تذكّر الأماكن التي مررت بها
خزّن كل حالة في قاموس يربطها برقم الخطوة التي رأيتها فيها أول مرة. ويكشف ظهورها مجددًا عن الدورة.
seen = {}اكتشف التكرار
قبل كل خطوة، تحقق مما إذا كانت الحالة الحالية موجودة بالفعل في seen. إذا كانت موجودة، فقد أغلقت الحلقة للتو.
if state in seen:
start = seen[state]قِس طول الدورة
يُحسب الطول بطرح رقم الخطوة التي رأيت فيها هذه الحالة أول مرة من رقم الخطوة الحالي. ويعيد هذا العدد من الخطوات الحالة إلى موضعها تمامًا.
length = step - seen[state]تجاوز الخطوات باستخدام modulo
اطرح طول الذيل، ثم خذ الخطوات المتبقية modulo طول الدورة. والآن لا تحتاج إلا إلى محاكاة عدد صغير من الخطوات المتبقية.
rem = (N - start) % lengthأكمل الخطوات المتبقية
شغّل المحاكاة لتلك الخطوات المتبقية فقط بدءًا من بداية الدورة. وستطابق الحالة النهائية الحالة عند الخطوة N تمامًا.
for _ in range(rem):
state = step_fn(state)حافظ على قابلية تجزئة الحالة
يجب أن تكون مفاتيح القاموس قابلة للتجزئة، لذا حوّل القوائم إلى صفوف قبل تخزينها. ولا يمكن أن تكون الحالة القابلة للتغيير مفتاحًا.
key = tuple(row)خوارزمية Floyd من دون ذاكرة
إذا كانت الحالات كبيرة جدًا بحيث يتعذر تخزينها، فتكتشف خوارزمية Floyd للسلحفاة والأرنب الدورة باستخدام مؤشرين وذاكرة إضافية تكاد تكون معدومة.
لماذا ينقذ هذا الموقف
يحوّل اكتشاف الدورة حلقة من تريليون خطوة مستحيلة إلى بضعة آلاف من الخطوات. فالتعرف على التكرار هو الحيلة كلها.
فحص سريع
رأيت الحالة الحالية أول مرة عند الخطوة s، وأنت الآن عند الخطوة t.
مراجعة
عندما تتكرر الحالات، سجّل كل حالة في خريطة، واعثر على طول الدورة، وتجاوز الخطوات باستخدام modulo، ولا تحاكِ إلا الخطوات المتبقية. 🚀
الأسئلة الشائعة
هل درس «اكتشاف الدورات في المحاكاة» مجاني؟
نعم — نص درس «اكتشاف الدورات في المحاكاة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «اكتشاف الدورات في المحاكاة»؟
تخطّي الخطوات عندما تتكرر الحالة تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «اكتشاف الدورات في المحاكاة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- نمذجة الحالة والتقدم خطوة إلى الأمام
- الجولات على الشبكة ومتجهات الاتجاه
- اكتشاف الدورات في المحاكاة
- ترويض الحالات الطرفية المراوغة