Algoritmo da ricorsivo a iterativo

[MaxDembo81]

Salve a tutti,
non ricordo/non riesco a trasformare un semplicissimo algoritmo da ricorsivo a iterativo.
L'algoritmo è il seguente

double s(int i, int N, int A{
if (i == 0 ) return 0;
if (i == 1 ) return 1;
else return 2*N*s(i-1,N,A) + (A-N*N)*s(i-2,N,A);}

Com'era la regola generale?
E come lo si traduce questo?

Grazie e scusate la nabbanza

[clockover]

Di solito con la risorsione in coda è una stupidaggine tradurlo in iterativo! Ma per quanto riguarda il tuo algoritmo hai a che fare con due chiamate ricorsive quindi non è proprio banale la cosa!

[gugoXX]

Nel caso pero' si puo' semplificare il tutto mantenendo traccia di quanto valeva la funzione nei passi necessari precedenti.
Ovvero, durante la conta da 1 a i basta memorizzare il valore che la funzione aveva al passo precedente, e quello che aveva al passo precedente ancora.

[tuccio`]

double s(int i, int N, int A)
{

// Il vettore S conterrà i valori del numero che vuoi calcolare
// inizialmente S[0] = 0 e S[1] = 1.
// Dopo di che usi gli ultimi due valori per calcolare il prossimo
// in maniera iterativa, sovrascrivendo di volta in volta il più
// vecchio, così da mantenere a ogni iterazione gli ultimi 2 valori
// che ti serviranno a calcolare il prossimo numero

double S[2] = { 0.0f, 1.0f }; // s(0, N, A) = 0, s(1, N, A) = 1

int j; // j è il prossimo numero che devi calcolare
for (j = 2; j <= i; j++)
{
// k è l'indice in cui si trova il valore s(j-2, N, A), quindi il più
// vecchio cioè quello che sostituirai. Ovviamente l'altro valore
// che ti serve si trova in S[1 - k]
int k = j % 2;
S[k] = 2*N*S[1 - k] + (A - N*N)*S[k];
}

// Uscito dal ciclo, il valore che cerchi è in 0 se i è pari, in 1 altrimenti
return S[i % 2];

}


Ma perché double? non può venire un numero con la virgola :E

ps: DOVREBBE funzionare :asd:

[gugoXX]

A me la complicazione dell'array con 2 elementi soli e del riferimento se il ciclo e' pari o dispari pare un eccesso poco leggibile.

[tuccio`]

per quello c'è più commento che codice :asd:

[gugoXX]

per quello c'è più commento che codice :asd:

:cry:

Propongo una cosa simile
(ne' compilato ne' tantomeno testato)


double s(int i, int N, int A)
{
if (i == 0 ) return 0;
if (i == 1 ) return 1;
int TM2 = 0;
int TM1 = 1;
int TM0;
for (int q=2; q<=i; q++)
{
TM0 = 2*N*TM1 + (A - N*N)*TM2;
TM2 = TM1;
TM1 = TM0;
}
return TM0;
}

[MaxDembo81]

testiamolo

[MaxDembo81]

funzionare funziona :D

Mi spieghi come ci sei arrivato?

[gugoXX]

Ho scritto la logica nel primo post.

[goldorak]

Salve a tutti,
non ricordo/non riesco a trasformare un semplicissimo algoritmo da ricorsivo a iterativo.
L'algoritmo è il seguente

double s(int i, int N, int A{
if (i == 0 ) return 0;
if (i == 1 ) return 1;
else return 2*N*s(i-1,N,A) + (A-N*N)*s(i-2,N,A);}

Com'era la regola generale?
E come lo si traduce questo?

Grazie e scusate la nabbanza

A e N sono parametri e non cambiano nelle varie chiamate ricorsive, quindi la tua funzione s dipende solo da i.

caso base : s(0) =0, s(1)=1
caso ricorsivo : s(n) = 2Ns(i-1)+(A-N^2)s(i-2)

quindi si vede che s(n) dipende soltanto dai due valori immediatamente precedenti s(i-1) e s(i-2). Nell'algoritmo iterativo sara' sufficiente ricordarsi degli ultimi due valori calcolati per determinare il valore piu' recente.