Newsgroup: it.comp.lang.c++
Titolo: help, spunto per risoluzione esercizi!

ciao a tutti,
senza spiegarmi troppo, che non avrebbe senso, mi dato uno spunto per
trovare l'n-esimo numero di Fibonacci (un classico...) però attraverso
una funzione NON ricorsiva?
Poi, una domanda un po' più teorica: qual è il metodo più veloce, e se
vogliamo  elegante, per modificare la lunghezza di un array ricevuto
come parametro, da parte di una funzione?
Ad esempio, ho un array di 5 elementi, magari già inizializzato oppure
inizializzato a run-time. Poi lo passo ad una funzione che, poniamo,
mi aggiunge un sesto elemento che può essere magari la somma dei
precedenti 5...però vorrei che la funzione mi andasse effettivamente a
modificare l'array iniziale!
Saluti! 
Luigi

 come parametro, da parte di una funzione?
Non esiste alcun metodo, né veloce né lento. Un array in C/C++ è una 
sequenza di lunghezza fissa, che può essere soltanto instanziata e 
distrutta. Non c'è nulla che si possa fare per allungare o accorciare un 
array.
Fortunatamente in C++ esiste std::vector<T>, che permette di manipolare una 
sequenza di dimensioni variabili, con la complessita computazionale e la 
sematica di un array.
Max

 una funzione NON ricorsiva?
L'aspetto fondamentale del metodo ricorsivo e' che ad ogni passo
"ricorda" per te informazioni essenziali al calcolo finale. Il tuo
problema e' individuare queste informazioni e gestirle esplicitamente,
in modo incrementale, all'interno del tuo ciclo.
Un'altra considerazione e' che generalmente i metodi ricorsivi
definiscono l'elemento complesso in termini di altri piu' semplici.
Operando invece in modo iterativo puo' risultare piu' intuitivo partire
dal semplice e costruire via via elementi piu' complicati.
Buon lavoro, e posta la soluzione!
Un consiglio: spaccati la testa, ma risolvi il problema da solo. Capire
la ricorsione e' fondamentale per chi vuole seriamente imparare a
programmare.
Un altro consiglio: se ti trovi bloccato comincia a scrivere la
versione iterativa del calcolo del fattoriale e confronta le versioni
iterativa e ricorsiva; potresti trovare spunti per il calcolo dei
numeri di Fibonacci.
Ciao,
Nicola

 una funzione NON ricorsiva?
Non ti dico come fare la funzione non ricorsiva, ma ti aiuto un po':
La classica funzione per il calcolo dei numeri di Fibonacci e' questa:
long double fib (int x )
{
     if (x < 2)
             return 1;
     return fib( x - 1 ) + fib ( x - 2 ) ;
}
E' ricorsiva, e impiega anni (miliardi di anni) a calcolare il fibonacci
di 100.
La stessa funzione si puo' scrivere usando una cache per velocizzare i calcoli:
long double fib (int x )
{
     static std::map<int, long double> fib_cache;
     std::map<int, long double>::iterator it = fib_cache.find(x);
     if ( it == fib_cache.end())   // non esiste un valore calcolato per x
     {
         if (x < 2)
             fib_cache[x] = 1;
         else
             fib_cache[x] = fib( x - 2 ) + fib (x - 1);
     }
     return fib_cache[x];
}
Nella realta' io farei una classe, invece di dichiarare un map
static all'interno di una funzione, ma per dimostrazione va bene
ugualmente.
Questa funzione calcola il Fibonacci di 1000 in qualche millesimo di secondo.
E' possibile implementare questa funzione in modo che non sia ricorsiva,
e questo lo lascio a te.
Ciao
gmax
-- 
   ____ ____  _____ _   _
  / _  |    \(____ ( \ / )
( (_| | | | / ___ |) X (
  \___ |_|_|_\_____(_/ \_)
(_____|
MySQL Certified Professional
Sapere, saper fare, fare, far sapere
http://gmax.oltrelinux.com

 una funzione NON ricorsiva?
Io se vuoi ti posso spiegare come fare una funzione che te lo rende in
O(1). Pero` e` un pochetto OT.
Allora... noi cerchiamo di risolvere la relazione ricorsiva
Fn = F(n-1) + F(n-2). Per ora ignoriamo le condizioni iniziali, ci
lavoreremo poi dopo. Cerchiamo anche una Fn nella forma x^n per qualche
x costante reale.
Svolgendo pochi calcoli algebrici
x^n - x^(n-1) - x^(n-2) = x^(n-2) * ( x^ 2 - x - 1) = 0
Scartiamo x = 0 come soluzione, scopriamo che l'equazione caratteristica
della relazione ricorsiva di Fibonacci e`
x^2 - x - 1 = 0
Le radici sono a = (1 + sqrt(5))/2 e b = (1 - sqrt(5))/2 
Purtroppo nessuna delle soluzioni Fn = a^n o Fn = b^n soddisfa le
condizioni iniziali. Tuttavia anche una combinazione lineare delle due
solzioni risolve l'equazione.
Prendiamo quindi 
Ya^n + Zb^n
E cerchiamo 
Fn = Ya^n + Zb^n
per qualche Y e Z. In particolare vogliamo che
0 = Ya^0 + Zb^0
e 
1 = Ya^1 + Zb^1
Il sistema da che Y = 1/sqrt(5) e Z = -1/sqrt(5)
ergo otteniamo che
Fn = (1/sqrt(5)) * ( ((1 + sqrt(5))/2) ^ n - ((1 - sqrt(5))/2) ^ n) )
Occhio alle approssimazioni!
[ il codice C++ e` superfluo... ]
-- 
Adesso quando i medici di turno rifiuteranno di esserti d'aiuto / perchè
venne un polacco ad insegnargli che è più cristiano imporsi col rifiuto
pretenderanno che tu torni indietro/e ti costringeranno a partorire per
poi chiamarlo figlio della colpa / e tu una Maddalena da pentire