versione power point

3 aprile 2002
Avvisi:
• 1o Esonero: mercoledi 17 aprile ore 11:30 – 14:00
consulta 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.
2.
3.
4.
5.
Perche' gli esoneri sostituiscano il compito d'esame devono essere stati
valutati entrambi. (Ad un esonero non fatto viene assegnato
automaticamente un punteggio insufficiente.)
Anche chi ottiene un voto insufficiente al primo esonero puo'
partecipare al secondo.
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).
Il voto proposto dopo gli esoneri puo' essere verbalizzato (con gli
aggiustamenti relativi al voto del progetto) soltanto nei due appelli
della sessione estiva.
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
Osservo l’esempio:
5! = 5 * 4 * 3 * 2 * 1
Quindi:
5! = 5 * 4!
4! = 4 * 3! ...
Formula ricorsiva:
n! = n(n-1)!
1!=1
Il fattoriale: versione ricorsiva
1. // 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!
5* 4!
120
3!
1!
2!
4* 3!
3* 2!
2* 1!
24
6
2
1
Cosa fa questo programma?
1.
2.
#include<stdio.h>
#include<stdlib.h>
3.
4.
5.
6.
7.
8.
9.
void stampa();
main()
{
stampa();
system("pause");
return 0;
}
10.
11.
12.
13.
14.
15.
16.
17.
18.
void stampa()
{
char c;
if ((c = getchar()) != EOF) {
stampa();
printf("%c", c);
};
}
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) = 1
fib(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 )
return
return
f( 1 )
return 1
f( 2 )
+
f( 0 )
return 0
+
f( 1 )
return 1
1 /* Fig. 5.15: fig05_15.c
2
Recursive fibonacci function */
3 #include <stdio.h>
4
5 long fibonacci( long );
6
7 int main()
8 {
9
long result, number;
10
11
printf( "Enter an integer: " );
12
scanf( "%ld", &number );
13
result = fibonacci( number );
14
printf("Fibonacci(%ld)= %ld\n", number,result );
15
return 0;
16 }
17
18 /* Definizione ricorsiva della funzione Fibonacci
19 long fibonacci( long n )
*/
20 {
21
if ( n == 0 || n == 1 )
22
return n;
23
else
24
return fibonacci(n - 1) + fibonacci(n - 2);
25 }
Sommario
prototipo
Inizializzazione
variabili
Chiamata funz.
fibonacci
Risultato in
output.
3. Defininzione
ricorsiva per
fibonacci
Enter an integer: 2
Fibonacci(2) = 1
Sommario
Enter an integer: 3
Fibonacci(3) = 2
Enter an integer: 4
Fibonacci(4) = 3
Enter an integer: 5
Fibonacci(5) = 5
Enter an integer: 6
Fibonacci(6) = 8
Enter an integer: 10
Fibonacci(10) = 55
Enter an integer: 20
Fibonacci(20) = 6765
Enter an integer: 30
Fibonacci(30) = 832040
Enter an integer: 35
Fibonacci(35) = 9227465
Output
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.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
#include <stdio.h>
Cosa fa questo programma?
int mystery(int, int);
main()
{
int x, y;
printf("Enter two integers: ");
scanf("%d%d", &x, &y);
printf("The result is %d\n", mystery(x, y));
return 0;
}
/* Parameter b must be a positive
integer to prevent infinite recursion */
int mystery(int a, int b)
{
if (b == 1)
return a;
else
return a + mystery(a, b - 1);
}
• 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