Problem

11/12

التكرار فوق السطور # 1

Theory Click to read/hide

مهمة
في أبجدية لغة القبيلة "Tumba-Yumba" ؛ أربعة أحرف: "K" ، "L" ، "M" و & quot؛ N & quot ؛. تحتاج إلى عرض جميع الكلمات التي تتكون من أحرف n التي يمكن إنشاؤها من أحرف هذه الأبجدية.

المشكلة هي مشكلة القوة الغاشمة العادية التي يمكن اختزالها إلى مشكلة أصغر.
سنقوم باستبدال الأحرف بالتسلسل.
يمكن أن يكون الموضع الأول للكلمة واحدًا من الأحرف الأربعة للأبجدية (K. L ، M ، N).
لنضع الحرف K أولاً. بعد ذلك ، من أجل الحصول على جميع المتغيرات التي تحتوي على الحرف الأول K ، تحتاج إلى تعداد جميع مجموعات الأحرف الممكنة & nbsp؛ في المواضع المتبقية n - 1 & nbsp؛ وما إلى ذلك. (انظر الصورة).
وهكذا ، يتم تقليل المشكلة إلى حل أربع مسائل طولها n - 1 .
نبسب ؛
تكرار أكثر من n حرفًا بشكل متكرر w [0] = & # 39؛ K & # 39 ؛؛ // كرر خلال آخر أحرف L-1 ث [0] = & # 39 ؛ L & # 39 ؛؛ // كرر خلال آخر أحرف L-1 ث [0] = & # 39 ؛ M & # 39 ؛؛ // كرر خلال آخر أحرف L-1 ث [0] = & # 39 ؛ N & # 39 ؛؛ // كرر خلال آخر أحرف L-1 w - سلسلة أحرف تخزن كلمة العمل.
وهكذا ، حصلنا على العودية. & nbsp ؛ يمكننا ترتيب حل المشكلة في شكل إجراء تكراري. & nbsp ؛
يبقى لتحديد متى سينتهي العودية؟ عندما يتم تعيين جميع الأحرف ، أي أن عدد الأحرف المحددة هو n . في هذه الحالة ، تحتاج إلى عرض الكلمة الناتجة على الشاشة والخروج من الإجراء.

سيبدو برنامج C ++ بهذا الشكل.
# include & lt؛ iostream & gt؛ استخدام اسم للمحطة؛ Void TumbaWords (سلسلة A ، string & amp؛ w ، int N) // w - معلمة قابلة للتغيير (سلسلة-نتيجة) // يتم تمرير إجراء TumbaWords الأبجدية كسلسلة أحرف ، // الكلمة word وعدد الأحرف التي تم تعيينها بالفعل (السابقة & ndash ؛ 0). { إنت أنا إذا (N == w.size ()) { نبسب ؛ // إذا تم بالفعل تعيين جميع الأحرف للكلمة ، & nbsp؛ نبسب ؛ // ثم من الضروري إخراج سلسلة وإنهاء الإجراء كوت & lt؛ & lt؛ & lt؛ & lt؛ نهاية. يعود؛ } لـ (i = 1 ؛ i & lt ؛ A.size () ؛ i ++) { نبسب ؛ // إذا كان الشرط أعلاه خاطئًا (أي أنه لا توجد مسافات بين جميع الأحرف ، نبسب ؛ // ثم في الحلقة نمر بجميع أحرف الأبجدية و // ضع الحرف بالتناوب على أول مساحة خالية w [N] = A [i] ؛ TumbaWords (A، w، N + 1) ؛ } } رئيسي() { إنت. سلسلة. إنتن. سينما & GT ؛ & GT. ن؛ word.resize (n) ؛ // زيادة السلسلة إلى الحجم n TumbaWords ("KLMN" ، كلمة ، 0) ؛ }
لاحظ أن w معلمة قابلة للتغيير (سلسلة نتيجة)!

Problem

في الأبجدية من لغة القبيلة "tumba-yumba" أربعة أحرف: "K" ، "L" ، "M" و & quot؛ N & quot ؛. تحتاج إلى عرض جميع الكلمات التي تتكون من أحرف n التي يمكن إنشاؤها من أحرف هذه الأبجدية.
(c) K.Yu. بولياكوف