Module: العد العودي


Problem

1 /4


كل PSP

Theory Click to read/hide

في معظم الحالات ، يتم حل مشاكل العد عن طريق التعداد العودي. لسوء الحظ ، لا يوجد نهج عام ، لأنه غالبًا ما تعتمد طرق التكرار بشكل كبير على المهمة نفسها.
ومع ذلك ، يمكن للمرء أن يلاحظ بعض التشابه بين طرق تعداد الكائنات الاندماجية المختلفة. لذلك ، كمثال توضيحي ، ضع في اعتبارك رمزًا يولد جميع التوليفات من n إلى k.
نبسب ؛ int ن ، ك ؛ // مصفوفة تدعم البادئات المركبة. // // تعني البادئة في هذه الحالة أننا اخترنا بعض العناصر في المجموعة. // // بعد ذلك ، سيتم إكمالها إما في المجموعة الصحيحة ، // أو ستقطع العودية الفرع عندما تدرك أن مثل هذه البادئة لا يمكن إكمالها بشكل صحيح ناقلات arr ؛ // دالة التكرار العودية نفسها // // pos - رقم الكائن معًا ، والذي سنحدده في الوقت الحالي (من 0 إلى k - 1) // // prev - قيمة العنصر الذي تم التقاطه في الخطوة السابقة // // في المجموعات ، ترتيب العناصر ليس مهمًا ([1 ، 2] و [2 ، 1] تعتبر متشابهة ومتشابهة) ، // لذلك نريد فقط إنشاء مجموعات حيث تكون قيم الكائن بترتيب تصاعدي. // // يعد هذا ضروريًا حتى يتم تكرار نفس الخيارات مثل [1 ، 2] و [2 ، 1] مرة واحدة فقط // (في حالتنا ، سننظر فقط في [1 ، 2] ، ولكن ليس [2 ، 1] لأنها ليست مجموعة مرتبة). // // لهذا السبب نحتفظ بالمتغير prev لتقليل عدد التكرارات rec void (int pos، int prev) { // إذا كان رقم العنصر المحدد يساوي k ، فقد حددنا بالفعل جميع العناصر // لأن أعدادهم من 0 إلى k - 1 إذا (نقاط البيع == ك) { // إذا تم استيفاء الشرط ، فسيكون التركيبة الصحيحة الآن في المصفوفة arr // ويمكننا معالجتها بطريقة ما (في هذه الحالة ، فقط اطبعها على وحدة التحكم) لـ (int i = 0 ؛ i & lt ؛ k ؛ i ++) كوت & lt؛ & lt؛ arr [i] + 1 & lt؛ & lt؛ & # 39 ؛ & # 39 ؛؛ كوت & lt؛ & lt؛ & # 39 ؛ \ n & # 39 ؛؛ يعود؛ // قطع فرع العودية ، لأن حصلت بالفعل على مجموعة ولا حاجة لمواصلة المزيد } // هنا نتحقق مما إذا كان بإمكاننا الحصول على التركيبة الصحيحة من العناصر المتبقية // إذا لم يكن هناك ما يكفي من العناصر المتبقية ، فسنقطع فرع العودية هذا إذا (k - pos & gt؛ n - prev - 1) يعود؛ // كرر فوق الكائن الذي وضعناه في الموضع باستخدام مؤشر نقاط البيع // ولكن نريد مجموعة مرتبة ، فإن أدنى قيمة ممكنة هي prev + 1 لـ (int i = prev + 1؛ i & lt؛ n؛ i ++) { arr.push_back (ط) ، // أضف عنصرًا إلى المصفوفة العالمية. يبدو الآن أننا اخترناه rec (نقاط البيع + 1 ، أنا) ؛ // تشغيل بشكل متكرر لتعيين العناصر التالية arr.pop_back () ، // بعد العودة من العودية ، لم يعد العنصر المحدد حاليًا مناسبًا ، // لأن داخل العودية ، مررنا بجميع الخيارات بمثل هذه البادئة ، // لذلك يجب إزالة هذا العنصر } } انت مين() { سينما & GT ؛ & GT. ن & GT ؛ & GT. ك؛ // في البداية سنقوم بتعيين العنصر في الموضع 0 // نفترض أن العنصر -1 قد تم تحديده من قبل ، بحيث يبدأ التكرار مبدئيًا من كائن فارغ rec (0 ، -1) ؛ العودة 0 ؛ }

نفس الكود ولكن بدون تعليقات:
نبسب ؛ int ن ، ك ؛ ناقلات arr ؛ rec void (int pos، int prev) { إذا (نقاط البيع == ك) { لـ (int i = 0 ؛ i & lt ؛ k ؛ i ++) كوت & lt؛ & lt؛ arr [i] + 1 & lt؛ & lt؛ & # 39 ؛ & # 39 ؛؛ كوت & lt؛ & lt؛ & # 39 ؛ \ n & # 39 ؛؛ يعود؛ } إذا (k - pos & gt؛ n - prev - 1) يعود؛ لـ (int i = prev + 1؛ i & lt؛ n؛ i ++) { arr.push_back (ط) ، rec (نقاط البيع + 1 ، أنا) ؛ arr.pop_back () ، } } انت مين() { سينما & GT ؛ & GT. ن & GT ؛ & GT. ك؛ rec (0 ، -1) ؛ العودة 0 ؛ } نبسب ؛
في التكرارات العودية ، يجب دائمًا إيلاء اهتمام خاص لتخفيضات العودية. في الممارسة العملية ، يمكنهم تسريع البرنامج بشكل كبير.

Problem

تم إعطاء الرقم ن. أنت بحاجة إلى إنشاء جميع متواليات الأقواس الصالحة التي تحتوي على n أزواج من الأقواس.

الإدخال:
يحتوي السطر الأول على عدد طبيعي n (1 & lt؛ = n & lt؛ = 8).

الإخراج:
اطبع كل تسلسلات الأقواس الصحيحة بترتيب معجمي تصاعدي. كل على سطر منفصل.

مثال:
نبسب ؛ <الجسم>
إدخال الإخراج
3 ((()))
(() ())
(()) ()
() (())
() () ()