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

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]

Originariamente inviato da Black imp

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

infatti è ricorsione, no backtraking