في معظم الحالات ، يتم حل مشاكل العد عن طريق التعداد العودي. لسوء الحظ ، لا يوجد نهج عام ، لأنه غالبًا ما تعتمد طرق التكرار بشكل كبير على المهمة نفسها.
ومع ذلك ، يمكن للمرء أن يلاحظ بعض التشابه بين طرق تعداد الكائنات الاندماجية المختلفة. لذلك ، كمثال توضيحي ، ضع في اعتبارك رمزًا يولد جميع التوليفات من 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 ؛
}
نبسب ؛
في التكرارات العودية ، يجب دائمًا إيلاء اهتمام خاص لتخفيضات العودية. في الممارسة العملية ، يمكنهم تسريع البرنامج بشكل كبير.