Explication détaillée de la récursivité des fonctions C++ : résolution récursive des problèmes de combinaison

La récursion est une méthode utilisée pour résoudre des problèmes combinatoires où une fonction s'appelle elle-même. Les étapes de l'algorithme comprennent une condition de base (renvoi d'un ensemble vide lorsque le nombre d'éléments à sélectionner est 0) et une étape récursive (énumération de toutes les combinaisons possibles et ajout de l'élément actuel). Dans le cas réel, une fonction récursive est utilisée pour résoudre toutes les combinaisons possibles en sélectionnant 3 nombres dans le nombre défini pour former un nombre à trois chiffres.

Récursion de fonction C++ Explication détaillée : Résolution récursive de problèmes de combinaison

Introduction

La récursion est un processus dans lequel une fonction s'appelle elle-même et elle peut être utilisée pour résoudre une variété de problèmes. Dans cet article, nous explorerons les techniques de résolution de problèmes combinatoires par récursivité.

Problème combinatoire

Le problème combinatoire fait référence à la sélection d'un nombre spécifique d'éléments parmi un ensemble d'éléments, quel que soit l'ordre des éléments. Par exemple, choisissez 3 lettres dans un ensemble pour former un mot.

Algorithme récursif

Nous pouvons utiliser des fonctions récursives pour résoudre des problèmes combinatoires. Cette fonction accepte deux paramètres :

• Ensemble d'éléments
• Le nombre d'éléments à sélectionner

Étapes de l'algorithme :

1. Condition de base : Si le nombre d'éléments à sélectionner est 0, un ensemble vide est renvoyé (c'est-à-dire un ensemble sans aucun élément).

2. Étapes récursives :

   • Supprimez tout élément de l'ensemble d'éléments.
   • Appelez la fonction de manière récursive sur l'ensemble d'éléments restant et réduisez le nombre d'éléments à sélectionner de 1.
   • Ajouter l'élément actuel au résultat de l'appel récursif.

Cas pratique :

Utilisons la fonction récursive pour résoudre un problème pratique :

Problème : Sélectionnez 3 nombres dans un ensemble de nombres pour former un nombre à trois chiffres et trouvez toutes les combinaisons possibles .

Solution :

#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;
}

Description du programme :

• Entrez le nombre d'éléments et le nombre d'éléments à sélectionner.
• Initialisez une collection vide pour stocker les combinaisons.
• Appelez la fonction récursive findCombinations, qui énumère toutes les combinaisons possibles et affiche les résultats.

Exemple d'exécution :

Entrée :

5 3

Sortie :

012
013
014
023
024
034
123
124
134
234

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!