Homework 5

Vedi anche DomandeHomework5aa0203, SoluzioneHomework5aa0203, RisultatiHomework5aa0203.

---

---

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)
2. funzione fibonacci (opzione -F)
   • definita per x>=0
   • fibonacci(0) = 1
   • fibonacci(1) = 1
   • fibonacci(x) = fibonacci(x-1)---+ fibonacci(x-2)
3. funzione 42 (opzione -h)
   • definita per x>=0
   • f(0) = 42
   • f(x) = f(x-1)---+ 2*x
4. funzione GCD, ovvero massimo comun divisore usando l'algoritmo di Euclide (opzione -G)
   • definita per 0 ≤ x < 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
5. 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)
     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).
6. 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à
     2. 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:
  • 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

Esempi

-v (Dati personali)

• es5 -v (vostri dati)

Andrea
Sterbini
02
02
1961
sterbini@dsi.uniroma1NOSPAM.it

-f (Fattoriale)

• es5 -f 5 (calcola il fattoriale di 5)

* 5
** 4
*** 3
**** 2
***** 1
****** 0
120

-h (quarantadue)

• es5 -h 5 (che calcola la funzione 42 di 5)

* 5
** 4
*** 3
**** 2
***** 1
****** 0
72

-F (Fibonacci)

• es5 -F 5 (che calcola Fibonacci(5) )

* 5
** 4
*** 3
**** 2
***** 1
***** 0
**** 1
*** 2
**** 1
**** 0
** 3
*** 2
**** 1
**** 0
*** 1
8

-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

* 5
** 4
*** 3
**** 2
***** 1
8

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

* 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

-G (GCD)

• es5 -G 10 25 (calcola il Massimo Comun Divisore tra 10 e 25)

* 10 25
** 5 10
*** 0 5
5

Consegna

La soluzione va consegnata:

• entro la mezzanotte di lunedì 25 Novembre
• usando esclusivamente la pagina di consegna

-- AndreaSterbini - 12 Nov 2002

• Set ALLOWTOPICCHANGE = DocentiProg1Group