Dalam kebanyakan kes, masalah penghitungan diselesaikan dengan penghitungan rekursif. Malangnya, tidak ada pendekatan umum, kerana selalunya, kaedah lelaran sangat bergantung pada tugas itu sendiri.
Walau bagaimanapun, seseorang boleh melihat beberapa persamaan antara kaedah penghitungan pelbagai objek gabungan. Oleh itu, untuk contoh ilustrasi, pertimbangkan kod yang menjana semua gabungan daripada n hingga k.
int n, k;
// Tatasusunan yang menyokong awalan gabungan.
//
// Awalan dalam kes ini bermakna kita telah memilih beberapa objek dalam gabungan.
//
// Selepas itu, ia sama ada akan dilengkapkan dalam kombinasi yang betul,
// atau rekursi akan memotong cawangan apabila ia menyedari bahawa awalan sedemikian tidak dapat dilengkapkan dengan betul
vektor arr;
// fungsi lelaran rekursif itu sendiri
//
// pos - nombor objek dalam kombinasi, yang akan kita tentukan pada momen semasa (dari 0 hingga k - 1)
//
// prev - nilai objek yang telah diambil dalam langkah sebelumnya
//
// Dalam gabungan, susunan objek tidak penting ([1, 2] dan [2, 1] dianggap sama dan serupa),
// jadi kami hanya mahu menjana set di mana nilai objek berada dalam susunan menaik.
//
// Ini perlu supaya pilihan yang sama seperti [1, 2] dan [2, 1] diulang sekali sahaja
// (dalam kes kami, kami hanya akan mempertimbangkan [1, 2], tetapi bukan [2, 1] kerana ia bukan set tersusun).
//
// Itulah sebabnya kami mengekalkan pembolehubah sebelumnya untuk mengurangkan bilangan lelaran
void rec(int pos, int prev) {
// jika bilangan elemen yang dipilih adalah sama dengan k, maka kita telah memilih semua elemen
// kerana nombor mereka adalah dari 0 hingga k - 1
jika (pos == k) {
// jika syarat dipenuhi, maka gabungan yang betul kini berada dalam tatasusunan arr
// dan kami boleh memprosesnya entah bagaimana (dalam kes ini, cetak sahaja ke konsol)
untuk (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
kembali; // potong cawangan rekursi, kerana sudah mendapat kombinasi dan tidak perlu diteruskan lagi
}
// di sini kita semak sama ada kita boleh mendapatkan gabungan yang betul daripada elemen yang tinggal
// jika tidak cukup elemen yang tinggal, maka kita potong cabang rekursi ini
jika (k - pos > n - sebelum - 1)
kembali;
// lelaran ke atas objek yang kita letakkan pada kedudukan dengan pos indeks
// tapi sebab kami mahukan set tersusun, maka nilai minimum yang mungkin ialah prev + 1
untuk (int i = prev + 1; i < n; i++) {
arr.push_back(i); // Tambah elemen pada tatasusunan global. Sekarang kita nampaknya telah memilih dia
rec(pos + 1, i); // jalankan secara rekursif untuk menetapkan item berikut
arr.pop_back(); // selepas kembali dari rekursi, elemen yang dipilih pada masa ini tidak lagi relevan,
// kerana di dalam rekursi, kami melalui semua pilihan dengan awalan sedemikian,
// jadi elemen ini perlu dialih keluar
}
}
int utama()
{
cin>> n>> k;
// pada mulanya kita akan menetapkan elemen pada kedudukan ke-0
// kami menganggap bahawa elemen -1 telah dipilih sebelum ini, supaya lelaran pada mulanya bermula dari objek nol
rec(0, -1);
pulangan 0;
}
Kod yang sama, tetapi tanpa ulasan:
int n, k;
vektor arr;
void rec(int pos, int prev) {
jika (pos == k) {
untuk (int i = 0; i < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
kembali;
}
jika (k - pos > n - sebelum - 1)
kembali;
untuk (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);
pulangan 0;
}
Dalam lelaran rekursif, perhatian khusus harus sentiasa diberikan kepada pemotongan rekursif. Dalam amalan, mereka boleh mempercepatkan program.