Module: Enumerazione ricorsiva


Problem

1 /4


Tutto PSP

Theory Click to read/hide

Nella maggior parte dei casi, i problemi di enumerazione vengono risolti mediante enumerazione ricorsiva. Sfortunatamente, non esiste un approccio generale, perché spesso, i metodi di iterazione dipendono fortemente dall'attività stessa.
Tuttavia, si può notare una certa somiglianza tra i metodi di enumerazione di vari oggetti combinatori. Pertanto, per un esempio illustrativo, considera un codice che genera tutte le combinazioni da n a k.
  int n,k; // Un array che supporta i prefissi di combinazione. // // Il prefisso in questo caso significa che abbiamo selezionato alcuni oggetti nella combinazione. // // Successivamente, saranno completati nella combinazione corretta, // o la ricorsione interromperà il ramo quando si rende conto che tale prefisso non può essere completato correttamente vettore arr; // la funzione di iterazione ricorsiva stessa // // pos - numero dell'oggetto in combinazione, che determineremo al momento corrente (da 0 a k - 1) // // prev - il valore dell'oggetto preso nel passaggio precedente // // Nelle combinazioni, l'ordine degli oggetti non è importante ([1, 2] e [2, 1] sono considerati uguali e simili), // quindi vogliamo solo generare insiemi in cui i valori degli oggetti sono in ordine crescente. // // Questo è necessario affinché le stesse opzioni come [1, 2] e [2, 1] vengano ripetute solo una volta // (nel nostro caso considereremo solo [1, 2], ma non [2, 1] poiché non è un insieme ordinato). // // Ecco perché manteniamo la variabile prev per ridurre il numero di iterazioni void rec(int pos, int prev) { // se il numero dell'elemento selezionato è uguale a k, allora abbiamo già selezionato tutti gli elementi // Perché i loro numeri vanno da 0 a k - 1 se (pos == k) { // se la condizione è soddisfatta, la combinazione corretta è ora nell'array arr // e possiamo elaborarlo in qualche modo (in questo caso, basta stamparlo sulla console) for (int i = 0; i < k; i++) cout << arr[i] + 1 << ' '; cout << '\n'; ritorno; // taglia il ramo di ricorsione, perché ho già una combinazione e non c'è bisogno di continuare oltre } // qui controlliamo se possiamo ottenere la combinazione corretta dagli elementi rimanenti // se non ci sono abbastanza elementi rimanenti, allora tagliamo questo ramo di ricorsione if (k - pos > n - prec - 1) ritorno; // itera sull'oggetto che mettiamo nella posizione con l'indice pos // ma perché vogliamo un insieme ordinato, allora il valore minimo possibile è prev + 1 for (int i = prev + 1; i < n; i++) { arr.push_back(i); // Aggiunge un elemento all'array globale. Ora sembra che abbiamo scelto lui rec(pos + 1, i); // eseguito in modo ricorsivo per impostare i seguenti elementi arr.pop_back(); // dopo essere tornati dalla ricorsione, il nostro elemento attualmente selezionato non è più rilevante, // Perché all'interno della ricorsione, abbiamo esaminato tutte le opzioni con tale prefisso, // quindi questo elemento deve essere rimosso } } int principale() { cin>> n>> K; // inizialmente imposteremo l'elemento alla posizione 0 // supponiamo che l'elemento -1 sia stato selezionato in precedenza, in modo che l'iterazione inizi inizialmente da un oggetto nullo rec(0, -1); ritorno 0; }

Lo stesso codice, ma senza commenti:
  int n,k; vettore arr; void rec(int pos, int prev) { se (pos == k) { for (int i = 0; i < k; i++) cout << arr[i] + 1 << ' '; cout << '\n'; ritorno; } if (k - pos > n - prec - 1) ritorno; for (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); ritorno 0; }  
Nelle iterazioni ricorsive, si dovrebbe sempre prestare particolare attenzione ai tagli ricorsivi. In pratica, possono velocizzare notevolmente il programma.

Problem

Il numero n è dato. Devi generare tutte le sequenze di parentesi valide contenenti n coppie di parentesi.

Inserimento:
La prima riga contiene un numero naturale n (1 <= n <= 8).

Uscita:
Stampa tutte le sequenze di parentesi corrette in ordine lessicografico ascendente. Ognuno su una riga separata.

Esempio:
 
Input Uscita
3 ((()))
(()())
(())()
()(())
()()()