Argomento della lezione e' la presentazione della soluzione degli esercizi 2, 3, 4 assegnati la scorsa settimana.
L'intestazione del metodo e' la seguente:
/* AI: n >= 0 AF: restituisce n! */ public static int myFact(int n)
Una prima versione del body e' la seguente:
{ int r=1; // il valore da restituire
// IC: 1<=i<=n+1 AND r=(i-1)!
for (int i=1; i <= n ; i++)
r*=i;
// r = n!
return r;
}
NOTA1: quando si esce dal ciclo si ha i=n+1, quindi r=n!.
Una seconda versione del body e' la seguente (in cui il fattoriale e' calcolado in "modo discendente", cioe' per calcolare n! si calcola il prodotto n*(n-1)*...*3*2*1):
{ int r=1; // il valore da restituire
// IC: 0<=i<=n AND r*i!=n!
for (int i=n; i >= 1 ; i--)
r*=i;
// r = n!
return r;
}
NOTA1: quando si esce dal ciclo si ha i<1, ovvero i=0, quindi r=n!.
Vediamo se riusciamo a fare a meno della variabile i.
Una terza versione del body e' la seguente:
{ int r=1; // il valore da restituire
// n=N
// IC: 0<=n<=N AND r * n! = N!
while (n >= 2)
{ r*=n;
n--;
}
// r = N!
return r;
}
NOTA: quando si esce dal ciclo si ha n<2, ovvero i=0 o i=1, quindi r=N!.
Proviamo a trasformare il "while" in un "for".
Una quarta versione del body e' la seguente:
{ int r=1; // il valore da restituire
// n=N
// IC: 0<=n<=N AND r * n! = N!
for (; n>2; n--)
r*=n;
// r = N!
return r;
}
DOMANDA: quali sono i pro e i contro di ciascuna versione del body?
L'intestazione del metodo e' la seguente:
/*
AI: n >= 0
AF: restituisce F(n), l'n-esimo numero di Fibonacci, dove:
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (per n>=2)
*/
public static int myFib(int n)
Una prima vesrione del body e' la seguente (si noti la presenza dello pseudo-codice, racchiuso tra i simboli "<<" e ">>"):
{ if (n==0) return 0;
// n >= 1
int f=1;
int p=0;
// IC: 1<=i<=n AND f=F(i) AND p=F(i-1)
for (i=1; i < n; i++)
{
<< ESEGUI L'ASSEGNAZIONE SIMULTANEA: (f,p)=(f+p,f) >>
}
// f=F(n)
return f;
}
NOTA: quando si esce dal ciclo si ha i=n, quindi f=F(n).
Lo pseudo codice puo' essere "espanso" nel seguente codice:
int aux = f; // memorizza il valore di F(i) f=f+p; p=aux;
Tuttavia, osservando che, per n>=2, F(n-1)=F(n)-F(n-2), e' possibile rimpiazzare le tre assegnazioni precedenti con le due seguenti:
f=f+p; p=f-p;
L'intestazione del metodo non e' cambiata:
/* AI: b != 0 AND e >= 0 AF: restituisce b^e */ public static int myExp(int b, int e)
Il body invece e' completamente diverso:
{ int r=1; // il valore da restituire
int i=0; // indice sull'intervallo 0..e
// b=B AND e=E
// IC: e >= 0 AND r * b^e = B^E
while (e>0)
if (e % 2 == 0)
{ b *= b;
e /= 2;
}
else
{ r *= b;
e--;
}
// r = B^E
return r;
}
Questa settimana non vengono assegnate "letture" per la parte di laboratorio. LEGGETE PERO' LE PARTI DI LIBRO INDICATE ALLA PAGINA DEL Programma delle Lezioni tenute dal prof. Martelli .
Per eventuali chiarimenti rivolgersi ai docenti.
6 = 3 + 2 + 1Aggiungere alla classe MyMath un metodo:
public static bool perfetto(int n)tale che, per ogni m>=0, MyMath.perfetto(m) restituisca true se m e' un numero perfetto, false altrimenti. (NOTA:si richiede di corredare l'intestazione del metodo di "Asserzione Iniziale" e "Asserzione Finale", e di inserire nel codice l'eventuale "Invariante di Ciclo".)
static bool palindrome(String s)tale che, per ogni t!=null di tipo String, MyMath.palindrome(t) restituisca true se t e' una palindrome, false altrimenti. (NOTA:si richiede di corredare l'intestazione del metodo di "Asserzione Iniziale" e "Asserzione Finale", e di inserire nel codice l'eventuale "Invariante di Ciclo".)