قد يحتوي سطر على أربعة أقواس فتح وأربعة إغلاق، ومع ذلك يضع إغلاقًا قبل وجود فتح يخصه. نقرأ في هذا التمرين سلاسل من الأقواس الدائرية وحدها، من اليسار إلى اليمين. سنراجع سطرين من ثمانية رموز، ثم نعد الترتيبات الصحيحة لجميع مواضع الفتح الأربعة.
الخلاصة السريعة
لتوازن نوع واحد من الأقواس، يجب ألا يصبح عدد الفتح ناقص عدد الإغلاق سالبًا في أي جزء يبدأ من أول السطر، وأن ينتهي الفرق عند 0. تساوي العددين في النهاية وحده لا يكفي. [1]
- افحص كل بادئة، أي كل جزء يبدأ من أول السطر: عدد الفتح فيها لا يقل عن عدد الإغلاق، والعددان يتساويان في السطر الكامل. [1]
- ابدأ رصيدًا عند 0، وأضف 1 عند الفتح واطرح 1 عند الإغلاق. اقرأ من اليسار إلى اليمين؛ أي رصيد سالب يرفض السطر. [1]
- في مثالنا ()())(()، الرصيد بعد الرموز هو 1، 0، 1، 0، −1، 0، 1، 0. يفشل عند الموضع 5، رغم تساوي أربعة فتح وأربعة إغلاق.
- المثال ()(())() يعطي 1، 0، 1، 2، 1، 0، 1، 0؛ فلا ينخفض عن 0 وينتهي عنده. لمس الصفر أثناء القراءة مسموح.
- لأربعة أزواج اخترنا كل مواضع الفتح الممكنة في ثمانية أماكن:70 ترتيبًا، منها 14 صحيحًا و 56 مرفوضًا. الصورة الرئيسية تعرض المسارات الصحيحة الأربعة عشر كاملة.
- النهاية الموجبة تعني فتحًا لم يغلق؛ مثال (( ينتهي عند 2 فيفشل. السلسلة الفارغة تحقق الشرطين. نقتصر على نوع واحد ورمزيه؛ لا نحكم بهذا العد على تعبير حسابي كامل أو أقواس من أنواع مختلطة.
البادئة ليست أي قطعة من السطر
تعرف MathWorld كلمة Dyck بسلسلة ذات عدد متساوٍ من الفتح والإغلاق، ولا يزيد الإغلاق على الفتح في أي جزء أولي. [1] نسمي هذا الجزء بادئة.
في سطرنا ذي الثمانية رموز، تشمل البادئات أول رمز، ثم أول رمزين، وهكذا حتى السطر كله. لا نختار قطعة من وسط السطر ونطلب لها الشرط نفسه. فقد تكون القطعة الوسطى إغلاقًا لفتح موجود قبلها.
نكتب رمز الفتح ( ورمز الإغلاق ) باتجاه ثابت من اليسار إلى اليمين في السلاسل المعروضة. مهمتنا سلامة ترتيب الأقواس نفسها؛ لا توجد أعداد أو عمليات داخلها لنحسب قيمتها، ولا نبدل اتجاه القراءة تبعًا لاتجاه الفقرة العربية.
رصيد واحد يكشف الإغلاق المبكر
اجعل الرصيد هو عدد الفتح المقروء ناقص عدد الإغلاق المقروء. يبدأ 0، ويزيد 1 مع الفتح، وينقص 1 مع الإغلاق؛ هذا تسجيل عددي لشرط كل بادئة. [1]
في ()())(() نجد بعد أول أربعة رموز الرصيد 0. الرمز الخامس إغلاق، فيهبط إلى−1: هناك إغلاق إضافي لم يسبقه فتح متاح. الرمز السادس فتح يعيد الرصيد إلى 0، لكن هذا لا يمحو خطأ الموضع الخامس؛ الشرط يجب أن يصح في كل بادئة.
يقارن الجدول السطر المرفوض بسطر ()(())() المقبول. الموضع يبدأ من 1 عند الرمز الأيسر. قيم الجدول هي الرصيد بعد قراءة الرمز، أما قبل القراءة فهو 0. لاحظ اختلاف الموضع 4 أيضًا؛ السطر الصحيح يفتح قوسًا إضافيًا، ثم يغلقه تدريجيًا.
| الموضع من اليسار | رمز الصحيح | رصيده | رمز المرفوض | رصيده |
|---|---|---|---|---|
| 1 | ( | 1 | ( | 1 |
| 2 | ) | 0 | ) | 0 |
| 3 | ( | 1 | ( | 1 |
| 4 | ( | 2 | ) | 0 |
| 5 | ) | 1 | ) | −1 |
| 6 | ) | 0 | ( | 0 |
| 7 | ( | 1 | ( | 1 |
| 8 | ) | 0 | ) | 0 |
عدم السالب شرط، والنهاية الصفرية شرط آخر
السطر ()(())() لا ينخفض عن 0 وينتهي عند 0، فيقبل. العودة إلى الصفر بعد الموضع 2 أو 6 تعني أننا أغلقنا كل ما فتح حتى تلك اللحظة، ويمكن أن تبدأ مجموعة أخرى بعد ذلك. لا نطلب أن يبقى الرصيد موجبًا حتى النهاية.
أما (( فرصيداه 1 و 2. لم ينخفض تحت الصفر، لكنه انتهى عند 2، أي بقي قوسا فتح دون إغلاق. لذلك نرفضه. وإذا كان أول رمز إغلاقًا فالرصيد−1 منذ البداية، فيرفض ولو أتى فتح لاحق.
السلسلة الفارغة تحقق هذا الاختبار: ليس فيها إغلاق سابق لفتح، والرصيد الابتدائي 0 هو النهائي أيضًا. هذا قبول للسلسلة الفارغة في تمرين الأقواس وحده، وليس حكمًا بأنها تعبير حسابي صالح.
حوّل كل رمز إلى خطوة في الرسم
يمثل الفتح خطوة صاعدة، والإغلاق خطوة هابطة. [1] نرسم الموضع أفقيًا والرصيد رأسيًا؛ يظهر الرصيد السالب أسفل خط الصفر، وتظهر النهاية على الخط عندما يتساوى العددان.
الصورة الداخلية ترسم مثالينا. السطر المرفوض ينخفض تحت الخط بعد الخطوة 5، ثم يعود إلى الخط عند الخطوة 6 وينتهي عليه. السطر المقبول يلامس الخط بعد الخطوات 2 و 6 و 8 دون النزول تحته. وجود نقطة نهاية على الصفر لا يكفي إذا هبط المسار قبله.
كل رسم في الصورة الرئيسية له 8 خطوات؛ أربع صاعدة وأربع هابطة. العرض يسجل مواضع الرموز، والارتفاع يسجل عدد الأقواس المفتوحة التي لم تغلق حتى تلك اللحظة. هذه رسوم بيانات التمرين، وليست قياسات أطوال أو مسارات حركة لجسم.
أربعة أزواج تعطي أربعة عشر ترتيبًا صحيحًا
ثبتنا ثمانية مواضع، واخترنا أربعة منها للفتح. المواضع الأربعة الأخرى للإغلاق. مررنا على جميع الاختيارات دون تكرار، فوجدنا 70 سلسلة ذات عددين متساويين، ثم فحصنا رصيد كل بادئة. نجح 14 ترتيبًا، ورفض 56؛ وهذا تعداد كامل لمثالنا.
تعرض الصورة الرئيسية الترتيبات الأربعة عشر، ومنها ()(())() و()()()(). الترتيب الأول يتضمن جزءًا متداخلًا، والثاني مجموعات منفصلة؛ كلاهما يحقق الشرطين. لا نحصر القبول في التداخل الكامل (((()))).
المواضع ثابتة والرموز من نوع واحد، ولا نحسب تبديل أسماء الأقواس كترتيب آخر. لم نختبر أنواعًا مختلفة أو لغة برمجة أو محتوى بين الأقواس. عند مراجعة سطر في هذا التمرين، سجل أول رصيد سالب إن وجد، ثم راجع النهاية؛ لا تكتفِ بعد الفتح والإغلاق في السطر كله.
اقرأ أيضًا: تمارين على ترتيب العمليات الحسابية: حل مترابط خطوة بخطوة
المراجع
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.