[C] Algoritmo di backtracking

[Manugal]

Ciao.

Sto cercando di capire cosa avviene passo passo in questo algoritmo:


Funzione chiamante:

void gensec(int n, int k){
int t[n];
genseqrec(n,k,t,-1);
}

void genseqrec (int n, int k, int t[], int l){
int i;
if(l==n-1)
stampa(t);
else
for(i=1; i<=k; ++i){
t[l+1]=i;
genseqrec(n,k,t,l+1);
}
}


Praticamente è un algoritmo che genera tutte le sequenze di lunghezza n, definite nell'inisieme {1,.....,k}. Quindi per n=2 e k=3 avrò:

(1,1) (1,2) (1,3)
(2,1) (2,2) (2,3)
(3,1) (3,2) (3,3)

Il problema è che non riesco a capire quel ciclo for, cosa succede ad ogni iterazione. Grazie.

[franksisca]

scusa, ma che cosa non capisci???
è un classico esempio di ricorsione, non riesco a capire che cosa non hai capito..... :mbe: :mbe:
for(i=1; i<=k; ++i){
t[l+1]=i; --->qua metti in posizione l+1 il valore i, che viene
incrementatto per ogni for
genseqrec(n,k,t,l+1); ---> qua richiami la stessa funzione aumentando l di uno....

}

[Manugal]

Non riesco a capire come si riempie il vettore.... come fa alla fine a generare quella sequenza?

[Manugal]

Ragionandoci meglio sopra, sono riuscito a capire come viene costruita ad ogni passo della ricorsione la sequenza. Grazie lo stesso :)

[sottovento]

In effetti e' un codice piuttosto difficile. Immagino si tratti di un esercizio, visto che non c'e' altro motivo di generare un codice simile.

Comunque: si tratta di una procedura ricorsiva.

- Base della ricorsione: l == n-1.
Quando questo valore e' raggiunto, siamo sicuri di aver riempito il vettore degli n elementi necessari, pertanto lo si stampa e la ricorsione finisce li.

- passo ricorsivo> l != n - 1 (ovviamente l < n-1)
In questo caso, l'elemento corrente dell'array viene riempito e si demanda alla ricorsione il riempimento del resto. Il vettore riduce il numero di elementi da riempire fino ad arrivare alla base della ricorsione.
Tutto qui

High Flying
Sottovento

[Black imp]

non mi sembra però backtracking, nel senso che non torna indietro ma si propaga in una sola direzione.

[franksisca]

non mi sembra però backtracking, nel senso che non torna indietro ma si propaga in una sola direzione.
infatti è ricorsione, no backtraking