Dans la plupart des cas, les problèmes d'énumération sont résolus par une énumération récursive. Malheureusement, il n'y a pas d'approche générale, car souvent, les méthodes d'itération dépendent fortement de la tâche elle-même.
Cependant, on peut remarquer une certaine similitude entre les méthodes d'énumération des divers objets combinatoires. Par conséquent, pour un exemple illustratif, considérons un code qui génère toutes les combinaisons de n à k.
entier n, k ;
// Un tableau qui prend en charge les préfixes de combinaison.
//
// Le préfixe dans ce cas signifie que nous avons sélectionné des objets dans la combinaison.
//
// Par la suite, ils seront soit complétés dans la bonne combinaison,
// ou la récursivité coupera la branche lorsqu'elle se rendra compte qu'un tel préfixe ne peut pas être complété correctement
vecteur arr ;
// la fonction d'itération récursive elle-même
//
// pos - numéro de l'objet en combinaison, que nous déterminerons au moment actuel (de 0 à k - 1)
//
// prev - la valeur de l'objet qui a été prise à l'étape précédente
//
// Dans les combinaisons, l'ordre des objets n'est pas important ([1, 2] et [2, 1] sont considérés comme identiques et similaires),
// donc nous voulons uniquement générer des ensembles où les valeurs d'objets sont dans l'ordre croissant.
//
// Ceci est nécessaire pour que les mêmes options telles que [1, 2] et [2, 1] ne soient itérées qu'une seule fois
// (dans notre cas, nous ne considérerons que [1, 2], mais pas [2, 1] car ce n'est pas un ensemble ordonné).
//
// C'est pourquoi on garde la variable prev pour réduire le nombre d'itérations
void rec(int pos, int prev) {
// si le numéro de l'élément sélectionné est égal à k, alors nous avons déjà sélectionné tous les éléments
// parce que leurs nombres vont de 0 à k - 1
si (pos == k) {
// si la condition est remplie, alors la bonne combinaison est maintenant dans le tableau arr
// et nous pouvons le traiter d'une manière ou d'une autre (dans ce cas, imprimez-le simplement sur la console)
pour (int i = 0; je < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
retour; // coupe la branche de récursivité, car déjà obtenu une combinaison et pas besoin de continuer plus loin
}
// Ici, nous vérifions si nous pouvons obtenir la bonne combinaison à partir des éléments restants
// s'il n'y a pas assez d'éléments restants, alors on coupe cette branche de récursivité
si (k - pos > n - préc - 1)
retour;
// itération sur l'objet que nous avons mis sur la position avec l'index pos
// mais parce que nous voulons un ensemble ordonné, alors la valeur minimale possible est prev + 1
for (int i = prev + 1; i < n; i++) {
arr.push_back(i); // Ajoute un élément au tableau global. Maintenant, nous semblons l'avoir choisi
rec(pos + 1, je); // exécution récursive pour définir les éléments suivants
arr.pop_back(); // après retour de la récursivité, notre élément actuellement sélectionné n'est plus pertinent,
// parce que à l'intérieur de la récursivité, nous avons parcouru toutes les options avec un tel préfixe,
// donc cet élément doit être supprimé
}
}
int main()
{
cin>> n>> k;
// initialement nous placerons l'élément à la 0ème position
// nous supposons que l'élément -1 a été sélectionné auparavant, de sorte que l'itération commence initialement à partir d'un objet nul
rec(0, -1);
renvoie 0 ;
}
Le même code, mais sans commentaires :
entier n, k ;
vecteur arr ;
void rec(int pos, int prev) {
si (pos == k) {
pour (int i = 0; je < k; i++)
cout << arr[i] + 1 << ' ';
cout << '\n';
retour;
}
si (k - pos > n - préc - 1)
retour;
for (int i = prev + 1; i < n; i++) {
arr.push_back(i);
rec(pos + 1, je);
arr.pop_back();
}
}
int main() {
cin>> n>> k;
rec(0, -1);
renvoie 0 ;
}
Dans les itérations récursives, une attention particulière doit toujours être portée aux coupes récursives. En pratique, ils peuvent considérablement accélérer le programme.
|