HomeWork5aa0203 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Homework 5
Vedi anche DomandeHomework5aa0203, SoluzioneHomework5aa0203, RisultatiHomework5aa0203.
----
%TOC%
----
---+++ Obiettivi
   * uso degli argomenti passati al programma dalla riga di comando
   * uso della struttura di controllo *switch* (per selezionare la funzione calcolata)
   * definizione e uso di funzioni ricorsive semplici, doppiamente ricorsive e mutualmente ricorsive

---+++ Svolgimento

Si sviluppi un programma C che implementa una o più (a vostra scelta) delle seguenti funzioni ricorsive a valori ed argomenti *interi*:
   1 funzione *fattoriale* (opzione *-f*) 
      * definita per x>=0
      * _fattoriale(0) = 1_
      * _fattoriale(x) = x * fattoriale(x-1)_
   1 funzione *fibonacci* (opzione *-F*)
      * definita per x>=0
      * _fibonacci(0) = 1_
      * _fibonacci(1) = 1_
      * _fibonacci(x) = fibonacci(x-1)---+ fibonacci(x-2)_
   1 funzione *42* (opzione *-h*)
      * definita per x>=0
      * _f(0) = 42_
      * _f(x) = f(x-1)---+ 2*x_
   1 funzione *GCD*, ovvero _massimo comun divisore_ usando l'algoritmo di Euclide (opzione *-G*)
      * definita per *0 &le; x &lt; y*
      * _GCD(0,y) = y_
      * _GCD(x,y) = GCD(mod(y,x),x)_
      * Esempio: _GCD(10,25) = GCD(5,10) = GCD(0,5) = 5_
      * ricordatevi di disporre i due parametri in ordine crescente prima di chiamare la funzione
   1 funzione *m* (opzione *-m*)
      * definita per x>=0
      * _m(0) = 0_
      * _m(x) = m(x-1)---+ 2*g(x)_
      * _g(0) = 1_
      * _g(x) = g(x-1) - 2*m(x-1)_ <br />
      __NOTA:__ Visto che il compilatore deve conoscere una funzione prima di poterla usare in un'altra funzione, dovete inserire nel testo il
      prototipo di g prima della funzione m (supponendo che il codice di g sia dopo quello di m).
   1 funzione *fibonacci_efficiente* (opzioni *-E* e *-A*)
      * la funzione di fibonacci vista sopra ha complessità esponenziale (raddoppia il numero di chiamate per ogni livello)
      * è possibile implementarla in modo che abbia complessità lineare in uno dei seguenti modi:
         1 la funzione *torna due valori*, quello corrente ed il precedente, calcola il nuovo valore e torna i due valori.
           Per tornare due valori potete:
            * usare un record (una *struct*)
            * *oppure* passare come argomento della funzione un array di due elementi *che la funzione modificherà*
         1 oppure si allochi un vettore di dimensioni adeguate che _ricorda_ per ogni *n* il valore di F(n). 
           Il valore F(n) viene inserito nel vettore la prima volta che viene calcolata F(n) 
           e da quel momento in poi ogni chiamata successiva di F(n) prima controlla se il valore è stato calcolato ed in caso positivo lo ricava dal vettore. Questa tecnica si chiama *memoization* (è parente della *programmazione dinamica*).
      * implementate una delle due versioni efficienti
      * __NOTA__ non ho controllato se le due versioni danno una traccia identica per cui conviene che si usino 2 parametri diversi per i due tipi di implementazione:
         * ==-E== per la versione che torna 2 valori
         * ==-A== per la versione che usa la tecnica della *memoization*, ovvero il vettore che si ricorda i valori delle chiamate precedenti
            * inseriro' appena possibile la traccia per questo secondo caso

---+++ Input e parametri di chiamata
Il programma deve ricevere sulla riga di comando una *sola* opzione (*-v -f -F -h -E -G* oppure *-m*) ed uno o due parametri (i valori *x* e *y*).
   * l'opzione indica quale funzione dev'essere calcolata
   * i parametri sono i valori di *x* e *y*, interi validi per la funzione data.
   * si preveda inolte l'opzione ==-v== che fa stampare le solite 6 righe che identificano lo studente (vedi HomeWork1aa0203)
Esempi di chiamate valide:
   * per eseguire il *fattoriale* di 10:  ==es4 -f 10==
   * per calcolare il 20mo numero di *fibonacci*:  ==es4 -F 20==
   * per calcolare il 20mo numero di *fibonacci* in modo efficiente:  ==es4 -E 20== (versione che torna la coppia [F(n),F(n-1)] )
   * per calcolare il 20mo numero di *fibonacci* in modo efficiente:  ==es4 -A 20== (versione che *ricorda* i valori)
   * per calcolare il valore della funzione *42* per x=13: ==es4 -h 13==
   * per calcolare il valore della funzione *m* per x=17: ==es4 -m 17==
   * per calcolare il Massimo Comun Divisore tra 25 e 10:  ==es4 -G 10 25==

---+++ Output
Il programma deve fornire in output:
   * opzione *-v*
      * le solite 6 righe che identificano lo studente (vedi HomeWork1aa0203)
   * opzione *-f x*
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *fattoriale(x)*
   * opzione *-F x*
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *fibonacci(x)*
   * opzione *-E x* oppure *-A x* 
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *fibonacci_efficiente(x)*
   * opzione *-G x y*
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *GCD(x,y)*
   * opzione *-h x*
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *f(x)*
   * opzione *-m x*
      * la traccia della chiamata ricorsiva (vedi dopo)
      * il valore di *m(x)*

---+++ Traccia della chiamata ricorsiva
Per evidenziare l'esecuzione ricorsiva di ciascuna funzione:
   * si passi alla funzione il parametro aggiuntivo *profondita* (intero) che indica a quale profondità di chiamata si è arrivati
      * la chiamata più esterna ha *profondita=0*
      * in ciascuna chiamata della funzione si abbia l'accortezza di incrementare la profondità di 1 prima di eseguire la chiamata ricorsiva e la stampa della traccia
   * si stampi su una nuova riga un numero di asterischi pari alla profondità corrente, seguiti da spazio e dal valore corrente di *x* (e di *y* nel caso di GCD). 
   * in particolare per l'opzione *-m*:
      * %RED% il valore di *profondita* dev'essere incrementato sia nella funzione *m* che nella funzione *g* e stampata la riga di asterischi seguita da spazio ed x %FINE%

---+++ Esempi
---++++ -v (Dati personali)
   * ==es5 -v== (vostri dati)
<verbatim>
Andrea
Sterbini
02
02
1961
sterbini@dsi.uniroma1NOSPAM.it
</verbatim>
---++++ -f (Fattoriale)
   * ==es5 -f 5== (calcola il fattoriale di 5)
<verbatim>
* 5
** 4
*** 3
**** 2
***** 1
****** 0
120
</verbatim>
---++++ -h (quarantadue)
   * ==es5 -h 5== (che calcola la funzione *42* di 5)
<verbatim>
* 5
** 4
*** 3
**** 2
***** 1
****** 0
72
</verbatim>
---++++ -F (Fibonacci)
   * ==es5 -F 5== (che calcola Fibonacci(5) )
<verbatim>
* 5
** 4
*** 3
**** 2
***** 1
***** 0
**** 1
*** 2
**** 1
**** 0
** 3
*** 2
**** 1
**** 0
*** 1
8
</verbatim>
---++++ -E (Fibonacci efficiente che torna la coppia di valori)
   * ==es5 -E 5== (che calcola la funzione Fibonacci(5) *efficiente*)
   * notate che torna la coppia 1,1 non appena arriva a 1
<verbatim>
* 5
** 4
*** 3
**** 2
***** 1
8
</verbatim>
---++++ -A (Fibonacci efficiente che usa l'array per ricordare i valori calcolati)
   * ==es5 -A 5== (che calcola la funzione Fibonacci(5) *efficiente*)
   * la implemento al più presto!
---++++ -m (mutuamente ricorsive)
   * ==es5 -m 3== (che calcola la funzione emme(3))
   * __NOTA__ l'ho appena implementata ... devo controllarla, ci vediamo domani.
<verbatim>
* 3
** 2
*** 1
**** 0
**** 1
***** 0
***** 0
*** 2
**** 1
***** 0
***** 0
**** 1
***** 0
***** 1
****** 0
****** 0
** 3
*** 2
**** 1
***** 0
***** 0
**** 1
***** 0
***** 1
****** 0
****** 0
*** 2
**** 1
***** 0
***** 1
****** 0
****** 0
**** 2
***** 1
****** 0
****** 0
***** 1
****** 0
****** 1
******* 0
******* 0
6
</verbatim>
---++++ -G (GCD)
   * ==es5 -G 10 25== (calcola il Massimo Comun Divisore tra 10 e 25)
<verbatim>
* 10 25
** 5 10
*** 0 5
5
</verbatim>
    
---+++ Consegna
La soluzione va consegnata:
   * entro la mezzanotte di *lunedì 25* Novembre
   * usando *esclusivamente* la [[http://twiki.dsi.uniroma1.it/~andrea/consegna.html][pagina di consegna]]

-- Users.AndreaSterbini - 12 Nov 2002

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group