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.
|