در بیشتر موارد، مسائل شمارش با شمارش بازگشتی حل می شوند. متأسفانه، هیچ رویکرد کلی وجود ندارد، زیرا اغلب، روش های تکرار به شدت به خود کار وابسته هستند.
با این حال، می توان شباهت هایی را در بین روش های شمارش اشیاء ترکیبی مختلف مشاهده کرد. بنابراین، برای یک مثال گویا، کدی را در نظر بگیرید که همه ترکیبات از n تا k را ایجاد می کند.
int n، k;
// آرایه ای که از پیشوندهای ترکیبی پشتیبانی می کند.
//
// پیشوند در این حالت به این معنی است که ما چند آبجکت را در ترکیب انتخاب کرده ایم.
//
// متعاقباً، آنها یا در ترکیب صحیح تکمیل می شوند،
// یا بازگشت زمانی که متوجه شود که چنین پیشوندی نمی تواند به درستی تکمیل شود، شاخه را قطع می کند
vector arr;
// خود تابع تکرار بازگشتی
//
// pos - تعداد شی در ترکیب، که در لحظه فعلی تعیین می کنیم (از 0 تا k - 1)
//
// prev - مقدار شی که در مرحله قبل گرفته شده است
//
// در ترکیب ها، ترتیب اشیا مهم نیست ([1، 2] و [2، 1] یکسان و مشابه در نظر گرفته می شوند)،
// بنابراین ما فقط می خواهیم مجموعه هایی را تولید کنیم که مقادیر شیء به ترتیب صعودی باشند.
//
// این امر ضروری است تا همان گزینه ها مانند [1، 2] و [2، 1] فقط یک بار تکرار شوند.
// (در مورد ما، ما فقط [1، 2] را در نظر می گیریم، اما [2، 1] را در نظر نمی گیریم زیرا مجموعه ای مرتب شده نیست).
//
// به همین دلیل است که برای کاهش تعداد تکرارها، متغیر prev را نگه می داریم
void rec(int pos, int prev) {
// اگر تعداد عنصر انتخاب شده برابر با k باشد، ما قبلاً همه عناصر را انتخاب کرده ایم
// زیرا اعداد آنها از 0 تا k - 1 است
اگر (pos == k) {
// اگر شرط برقرار باشد، ترکیب صحیح اکنون در آرایه arr است
// و ما می توانیم آن را به نحوی پردازش کنیم (در این مورد، فقط آن را در کنسول چاپ کنید)
برای (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
برگشت؛ // شاخه بازگشت را قطع کنید، زیرا در حال حاضر ترکیبی دریافت کرده است و نیازی به ادامه بیشتر نیست
}
// در اینجا بررسی می کنیم که آیا می توانیم ترکیب صحیح را از عناصر باقی مانده بدست آوریم
// اگر عناصر باقی مانده به اندازه کافی وجود نداشته باشد، این شاخه بازگشتی را قطع می کنیم
اگر (k - pos > n - قبلی - 1)
برگشت؛
// روی شی ای که روی موقعیتی با index pos قرار دادیم تکرار کنید
// اما چون ما یک مجموعه مرتب می خواهیم، سپس حداقل مقدار ممکن prev + 1 است
برای (int i = prev + 1; i < n; i++) {
arr.push_back(i); // یک عنصر به آرایه جهانی اضافه کنید. حالا به نظر می رسد که ما او را انتخاب کرده ایم
rec(pos + 1, i); // برای تنظیم موارد زیر به صورت بازگشتی اجرا شود
arr.pop_back(); // پس از بازگشت از بازگشت، عنصر انتخابی ما دیگر مرتبط نیست،
// زیرا در داخل بازگشت، همه گزینه ها را با چنین پیشوندی مرور کردیم،
// بنابراین این عنصر باید حذف شود
}
}
int main()
{
cin>> n>> k;
// در ابتدا عنصر را در موقعیت 0 قرار می دهیم
// فرض می کنیم که عنصر -1 قبلا انتخاب شده است، به طوری که تکرار در ابتدا از یک شی تهی شروع می شود.
rec(0, -1);
بازگشت 0;
}
همان کد، اما بدون نظر:
int n، k;
vector arr;
void rec(int pos, int prev) {
اگر (pos == k) {
برای (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
برگشت؛
}
اگر (k - pos > n - قبلی - 1)
برگشت؛
برای (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, i);
arr.pop_back();
}
}
int main() {
cin>> n>> k;
rec(0, -1);
بازگشت 0;
}
در تکرارهای بازگشتی، همیشه باید به برش های بازگشتی توجه ویژه ای شود. در عمل می توانند سرعت برنامه را تا حد زیادی افزایش دهند.