3 aprile 2002

Avvisi:

• 1o Esonero: mercoledi 17 aprile ore 11:30 – 14:00consulta la pag. WEB alla voce “esoneri”

si raccomanda la puntualita’!

Qualche “informazione” sull’esonero…

• Argomenti trattati: svolti nelle lezioni fino al 4 aprile (domani)

• Tipologia compito: Esercizi da svolgere del tipo proposto e discusso a lezione. (Ovviamente senza l’ausilio del compilatore…..)

• Non e’ possibile consultare:

– Libri o appunti

– I colleghi vicini e lontani

Qualche “informazione” sull’esonero…

1. Perche' gli esoneri sostituiscano il compito d'esame devono essere stati valutati entrambi. (Ad un esonero non fatto viene assegnato automaticamente un punteggio insufficiente.)

2. Anche chi ottiene un voto insufficiente al primo esonero puo' partecipare al secondo. 

3. Dopo gli esoneri, verra' proposto un voto che tiene conto dei risultati ottenuti in entrambe le prove (il secondo esonero avra' un peso maggiore del primo).

4. Il voto proposto dopo gli esoneri puo' essere verbalizzato (con gli aggiustamenti relativi al voto del progetto) soltanto nei due appelli della sessione estiva.

5. Chi si presenta e consegna il compito ad uno dei due appelli della sessione estiva, rinuncia automaticamente al voto proposto dopo gli esoneri.

Qualche minuto di laboratorio…

• Esercizio 5.17 Scrivere una funzione “multiplo” che per una coppia

di interi determina se il primo e’ multiplo del secondo. Utilizzare questa funzione per un programma che prende in input serie di coppie di interi e, per ogni coppia, decide se i due numeri sono uno multiplo dell’altro.

Vediamo le soluzioni che avete proposto…

• Esercizio 5.51 Ampliamento del programma “Simulatore del

gioco craps”. Incapsulare una partita in una funzione e consentire una successione di partite in cui l’utente puo’ fare delle scommesse. Per questo inizializzare una somma di denaro di partenza (es. 100 Euro) ed alla fine di ogni partita valutare la somma posseduta. (Ovviamente si puo’ continuare a giocare e a scommettere solo se si possiede ancora qualche euro….).

Vediamo le soluzioni che avete proposto…

• Esercizio 5.23 Scrivere una funzione che accetta in input l’ora ,

suddivisa in tre numeri interi (ore, minuti, secondi) e restituisce il numero di secondi trascorsi dalla mezzanotte. Utilizzare questa funzione per calcolare la quantita’ di secondi intercorsi tra due orari della stessa giornata.

Vediamo le soluzioni che avete proposto…

Ricorsione

• Funzioni Ricorsive – Funzione che chiama se stessa– Si puo’ risolvere solo il caso base– Divido il problema in:

• Quello che si puo’ risolvere• Quello che non si puo’ risolvere – somiglia al

problema originale– Lancia una nuova copia di se stesso (passo ricorsivo)

• Alla fine arrivo al caso base, che risolvo– Sostituisco la soluzione, ritorno su fino a risolvere

l’intero problema

Il fattoriale

n! = n(n-1)(n-2)(n-3)…. 1

1. // funzione fattoriale iterativa

2. long factorial(long number)

3. {

4. long fact =1;

5. for (counter= number; counter>=1; counter --)

6. fact *= counter;

7. return fact;

8. }

Il fattoriale: versione ricorsiva

n! = n(n-1)(n-2)(n-3)…. 1

Formula ricorsiva:

n! = n(n-1)!

1!=1

Osservo l’esempio:

5! = 5 * 4 * 3 * 2 * 1

Quindi:

5! = 5 * 4! 4! = 4 * 3! ...

Il fattoriale: versione ricorsiva1. // funzione fattoriale ricorsiva

2. long factorial(long number)

3. {

4. if (number <=1)

5. return 1;

6. else

7. return (number * factorial(number - 1));

8. }

5! 4! 3! 2! 1!5* 4! 4* 3! 3* 2! 2* 1!

12624120

1. #include<stdio.h>2. #include<stdlib.h>

3. void stampa();4. main()5. {6. stampa();7. system("pause");8. return 0;9. }

10. void stampa()11. {12. char c;13. 14. if ((c = getchar()) != EOF) {15. stampa();16. printf("%c", c);17. };18. }

Cosa fa questo programma?

Qualcosa sul tipo char

• char richiede 1 byte di memoria ( valore da –128 a 127)

• si puo’ visualizzare come:

• valore intero (conversione %d )

• carattere vero e proprio (conversione %c )

printf(“ Il carattere (%c) ha valore %d.\n”,’a’,’a’);

Da’ in output:

Il carattere (a) ha valore 97. (valore ASCII)

Esempio uso ricorsione : Le serie d Fibonacci

• Serie di Fibonacci :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

 

Il rapporto tra due numeri consecutivi tende a sezione aurea per i=2,3,….

Esempio uso ricorsione : Le serie d Fibonacci

• Serie di Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Ogni numero e’ la somma dei due precedenti 

fib(0) = 0 formula ricorsiva

fib(1) = 1fib(n) = fib(n-1) + fib(n-2)

Esempio uso ricorsione : Le serie d Fibonacci

long fibonacci(long n)

{

if (n==0 || n==1) // caso base

return n;

else

return fibonacci(n-1) + fibonacci(n-2);

}

 

Esempio uso ricorsione : Le serie d Fibonacci

f( 3 )

f( 1 )f( 2 )

f( 1 ) f( 0 ) return 1

return 1 return 0

return +

+return 

Sommario

prototipo

Inizializzazione variabili

Chiamata funz. fibonacci

Risultato in output.

3. Defininzione ricorsiva per fibonacci

1 /* Fig. 5.15: fig05_15.c2 Recursive fibonacci function */3 #include <stdio.h>45 long fibonacci( long );67 int main()8 {9 long result, number;1011 printf( "Enter an integer: " );12 scanf( "%ld", &number );13 result = fibonacci( number );14 printf("Fibonacci(%ld)= %ld\n", number,result );15 return 0;16 }1718 /* Definizione ricorsiva della funzione Fibonacci */19 long fibonacci( long n )20 {21 if ( n == 0 || n == 1 )22 return n;23 else24 return fibonacci(n - 1) + fibonacci(n - 2);25 }

Sommario

Output

Enter an integer: 2Fibonacci(2) = 1 Enter an integer: 3Fibonacci(3) = 2 Enter an integer: 4Fibonacci(4) = 3 Enter an integer: 5Fibonacci(5) = 5 Enter an integer: 6Fibonacci(6) = 8 Enter an integer: 10Fibonacci(10) = 55 Enter an integer: 20Fibonacci(20) = 6765 Enter an integer: 30Fibonacci(30) = 832040 Enter an integer: 35Fibonacci(35) = 9227465

Esempio uso ricorsione : Le serie d Fibonacci

 

Domanda:Quante chiamate ricorsive fa il programma?

Risposta: Ad ogni passo due

Da un semplice calcolo:

Per calcolare fibonacci(23)=28657,

Occorrono 92735 chiamate ricorsive!

• Esercizio 1

Scrivere una versione iterativa della funzione

long fibonacci( long n )

(*) spedire la soluzione entro il 9/4 ore 14:00

Ricorsione e Iterazione

• Ripetizione– iterazione : loop “esplicito”

– ricorsione : ripetizione di chiamate di funzioni

• Terminazione– iterazione : la condizione del loop non e’ piu’ verificata

– ricorsione : si arriva al caso base

• Entrambi possono avere loop infinito• Quale scegliere?

– La scelta e’ tra performance (iterazione) e buon software engineering (ricorsione)

1. #include <stdio.h>2. 3. int mystery(int, int);4. 5. main()6. {7. int x, y;8. 9. printf("Enter two integers: ");10. scanf("%d%d", &x, &y);11. printf("The result is %d\n", mystery(x, y));12. return 0;13. }14. /* Parameter b must be a positive 15. integer to prevent infinite recursion */16. int mystery(int a, int b)17. {18. if (b == 1)19. return a;20. else21. return a + mystery(a, b - 1);22. }

Cosa fa questo programma?

• Esercizio 2

Scrivere un programma con una funzione ricorsiva che prenda in input una coppia di interi e ne restituisca il Massimo Comune Divisore (cioe’ il piu’ grande intero che li divide entrambi)

(*) spedire la soluzione entro il 9/4 ore 14:00