Module: Énumération récursive


Problem

1 /4


Toutes les PSP

Theory Click to read/hide

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.

Problem

Le nombre n est donné. Vous devez générer toutes les séquences de parenthèses valides contenant n paires de parenthèses.

Saisie :
La première ligne contient un nombre naturel n (1 <= n <= 8).

Sortie :
Imprimez toutes les séquences de parenthèses correctes dans l'ordre lexicographique croissant. Chacun sur une ligne distincte.

Exemple :
 
Entrée Sortie
3 ((()))
(()())
(())()
()(())
()()()