Penjelasan terperinci tentang rekursi fungsi C++: menyelesaikan masalah gabungan secara rekursif

Rekursi ialah kaedah yang digunakan untuk menyelesaikan masalah gabungan di mana fungsi memanggil dirinya sendiri. Langkah algoritma termasuk keadaan garis dasar (mengembalikan set kosong apabila bilangan elemen yang akan dipilih ialah 0) dan langkah rekursif (menghitung semua kombinasi yang mungkin dan menambahkan elemen semasa). Dalam kes sebenar, fungsi rekursif digunakan untuk menyelesaikan semua kemungkinan kombinasi memilih 3 nombor daripada nombor yang ditetapkan untuk membentuk nombor tiga digit.

C++ Fungsi Rekursi Penjelasan Terperinci: Rekursif Menyelesaikan Masalah Kombinasi

Pengenalan

Rekursi ialah proses di mana fungsi memanggil dirinya sendiri, dan ia boleh digunakan untuk menyelesaikannya. Dalam artikel ini, kami akan meneroka teknik untuk menyelesaikan masalah gabungan menggunakan rekursi.

Masalah kombinatorial

Masalah kombinatorial merujuk kepada pemilihan bilangan elemen tertentu daripada set elemen, tanpa mengira susunan unsur. Sebagai contoh, pilih 3 huruf daripada set untuk membentuk perkataan.

Algoritma Rekursif

Kita boleh menggunakan fungsi rekursif untuk menyelesaikan masalah kombinatorial. Fungsi ini menerima dua parameter:

• Set elemen
• Bilangan elemen yang akan dipilih

Langkah algoritma:

1. Syarat garis dasar: Jika set ialah bilangan 0 elemen, yang akan dipilih dikembalikan (iaitu set tanpa sebarang unsur).

2. Langkah rekursif:

   • Alih keluar sebarang elemen daripada set elemen.
   • Panggil fungsi secara rekursif pada set elemen yang tinggal dan kurangkan bilangan elemen yang akan dipilih sebanyak 1.
   • Tambahkan elemen semasa pada hasil panggilan rekursif.

Kes praktikal:

Mari kita gunakan fungsi rekursif untuk menyelesaikan masalah praktikal:

Masalah: Pilih 3 nombor daripada set nombor untuk membentuk gabungan tiga angka yang mungkin .

Penyelesaian:

#include <iostream>
#include <vector>

using namespace std;

void findCombinations(vector<int> numbers, int n, int k) {
    if (k == 0) {
        for (int i : numbers) {
            cout << i;
        }
        cout << endl;
    } else {
        for (int i = 0; i < n; i++) {
            numbers.push_back(i);
            findCombinations(numbers, n, k - 1);
            numbers.pop_back();
        }
    }
}

int main() {
    int n; // 元素数量
    int k; // 需要选择的元素数量
    cin >> n >> k;

    vector<int> numbers;
    findCombinations(numbers, n, k);

    return 0;
}

Penerangan program:

• Masukkan bilangan elemen dan bilangan elemen yang akan dipilih.
• Mulakan koleksi kosong untuk menyimpan gabungan.
• Panggil fungsi rekursif findCombinations, yang menyenaraikan semua kemungkinan kombinasi dan mengeluarkan hasilnya.

Contoh pelaksanaan:

Input:

5 3

Output:

012
013
014
023
024
034
123
124
134
234

Atas ialah kandungan terperinci Penjelasan terperinci tentang rekursi fungsi C++: menyelesaikan masalah gabungan secara rekursif. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!