Tags:
create new tag
view all tags

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
  • 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:

-- AndreaSterbini - 12 Nov 2002

Edit | Attach | Watch | Print version | History: r15 < r14 < r13 < r12 < r11 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r15 - 2003-09-30 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback