1
Esaminiamo ora un altro esempio:
Il calcolo della potenza ennesima di un dato numero.
2
DIMOSTRAZIONE PER INDUZIONE
POTENZE
Vogliamo dimostrare che S(n):
caso base
Poniamo n=1 avremo
X n  X  X n1
X1  X X0
XX
passo induttivo
Dobbiamo ora dimostrare che
X
n 1
a)
che è quindi dimostrato vero
 XX
n
b)
Avendo supposto vero l’asserto sostituiamo in b) il valore che si ottiene da a)
X  Xn  X  Xn
q.e.d.
3
Codice della funzione PotenzaN.
Si presume che siano stati assegnati Xre, numero che si vuole elevare a
potenza e N potenza alla quale si vuole elevare Xre.
Si noti che l’algoritmo è simile a quello per il calcolo della somma dei
numeri interi, fatto salvo per il caso base che vale 1, infatti (Xre)0=1.
double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}
Di seguito si mostra sia lo stack dei processi che la modifica dei parametri
man mano che il processo avanza. L’esempio è fatto per Xre=0.9 e N=6
4
PotenzaN(0.9,3)
PotenzaN(0.9,3)
N=0?
PotenzaN
No
PotenzaN(0.9,2)
N=0?
0.9*
PotenzaN(0.9,2)
PotenzaN
No
0.9*
PotenzaN(0.9,1)
N=0?
PotenzaN
PotenzaN(0.9,1)
double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}
PotenzaN(0.9,0)
No
N=0?
Si
0.9*
PotenzaN(0.9,0)
PotenzaN
1
0.9*PotenzaN(0.9,0)
=1
0.9*PotenzaN(0.9,1)
=0.9*1
0.9*PotenzaN(0.9,2)
=0.9*0.9
0.9*PotenzaN(0.9,3)
=0.9*0.9*0.9
5
ESERCIZIO
Scrivere una funzione ricorsiva che, assegnati due interi N1 ed
N2, restituisca la somma di tutti gli interi compresi tra N1 ed N2.
6
Esercizio
Scrivere un algoritmo ricorsivo per determinare se un
assegnato numero intero positivo N è primo.
Si dimostra che un numero è primo se nell’intervallo
1.. N non ha divisori tranne il numero 1.
7
ESERCIZIO
Scrivere un algoritmo ricorsivo per determinare se un assegnato
numero intero positivo N è primo.
int main(){
int N;
cout<<"Inserisci un numero intero: ";
cin>>N;
int radN=sqrt(N);
if (primo(N, radN)
cout<<" Il numero "<<N<<" e' primo "<<endl;
else
cout<<" Il numero "<<N<<" non e' primo "<<endl;
system("PAUSE");
}
8
bool primo(int n,int P)
{
if (P<2)
return true;
// Caso base: non ha trovato alcun divisore di kn
else
if (n%P==0)
return false;
else
// Esiste almeno un divisore di kn diverso da 1
return primi(n,P-1);
}
// Chiamata ricorsiva su un valore di kn minore
9
Allegato: numeriprimi
Esercizio
Scrivere un algoritmo ricorsivo per determinare quanti
numeri primi ci sono in un preassegnato intervallo
K1..K2 di numeri interi positivi.
Allegato: NumeriPrimiIntervallo3
10
ALGORITMO DI EUCLIDE PER IL CALCOLO DEL
MASSIMO COMUN DIVISORE
(300 A.C.)
Siano m ed n due numeri naturali e supponiamo sia m>n
•1
Si divide m per n
•2
Se il resto è zero allora n è il MCD tra m e n.
•3
Se il resto è diverso da zero torna al primo
passo scambiando m con n e n con r (cioè
dividi n per r)
11
Nel lucido seguente è mostrata una interpretazione geometrica
dell’algoritmo di Euclide.
Si vuole il MCD dei numeri M e N rappresentati ciascuno da un
segmento di lunghezza M e N.
Il segmento restante dalla differenza tra M e N, detto R viene
successivamente confrontato con N che quindi assume il ruolo
di M nel caso precedente.
Si prosegue fin quando i due segmenti che si confrontano non
hanno la stessa lunghezza. Il valore ultimo di R sarà il MCD tra
M e N.
12
ALGORITMO DI EUCLIDE
M
N
R
R
R’
MCD=
R’
R’
13
Un algoritmo ricorsivo per il calcolo del MCD tra M
e N può essere il seguente:
Pseudo codice
IF M o N sono valori che rappresentano una soluzione valida
MCD  valore della soluzione (M o N)
ELSE
MCD  MCD(N, M MOD N)
14
Di seguito si mostrano le versioni iterativa e ricorsiva per il calcolo
del MCD secondo l’algoritmo di Euclide.
VERSIONE ITERATIVA
int MCD(int m,n) {
int Resto=m%n;
while (Resto !=0) {
m=n;
n=Resto;
Resto= m % n;
}
return n;
VERSIONE RICORSIVA
int MCD(int m,int n) {
if (n==0)
return m;
else
return MCD(n, m%n )
}
}
15
Nel lucido seguente viene mostrato un esempio di calcolo del
MCD, tra 30 e 18, secondo Euclide, con un algoritmo ricorsivo,
tramite la rappresentazione in termini di processi aperti, variazioni
del valore delle variabile durante il calcolo, rappresentazione
geometrica.
16
MCD(int m, n)
MCD(30,18)
N=0?
MCD(18,12)
No
No
N=0?
MCD
MCD(12,6)
N=0?
MCD
MCD(18,12)
MCD(6,0)
No
N=0?
Si
MCD
MCD(12,6)
MCD
MCD(6,0)
6
int MCD(int m,int n)
{
if (n==0)
return m;
else
return MCD(n, m%n );
}
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
MCD(6,0)
=6
MCD(12,6)
=6
MCD(18,12)
=6
MCD(30,18)
=6
7
6
5
4
3
2
17
1
DIMOSTRAZIONE PER INDUZIONE DELLA CORRETTEZZA
DELL’ALGORTIMO RICORSIVO PER IL MCD
caso base
Poniamo MCD(M,0)=M
passo induttivo
Dobbiamo ora dimostrare che MCD(M’,N’)=MCD(N, M MOD N)
Supponiamo MCD(M’,N’)=X
allora M’=hX e N’=zX
essendo N’=M MOD N
dove h e z sono interi
questo implica per definizione che
M=kN+N’
dove k è un intero
ma N’=zX
allora M=kN+zX
inoltre N=M’=hX quindi
M=khX+zX=(kh+z)X=wX
essendo allora sia M che N divisibili per X questo è il MCD(M,N)
18
ALTRI ESEMPI
Supponiamo di avere 3 lettere a b c. Vogliamo sapere quante permutazioni si
possono fare con questi 3 caratteri.
- ci sono 3 maniere per scegliere quale lettera mettere in terza posizione
(genericamente n)
abc
acb
cba
- per ognuna delle 3 scelte precedenti ci sono 2 maniere diverse per scegliere la
lettera da mettere in seconda posizione in totale 3*2 (genericamente n*(n-1))
abc
bac
acb
cab
cba
bca
- per ognuna delle 6 scelte precedenti c’è 1 sola maniera per scegliere la lettere da
mettere in prima posizione in totale 3*2*1 (genericamente n*(n-1)…..*1)
abc
bac
acb
cab
cba
bca
19
Si definisce FATTORIALE di un numero N il prodotto di tutti i
numeri da 0 a N come di seguito definito:
0! 1
N! N * ( N  1) * ( N  2) * ....... * (2) *1
Di seguito sono mostrati gli algoritmi e relativi codici iterativi e ricorsivi
20
double fattorialeIterativo(int Num)
{
int fatt=1;
for (int j=1;j<=Num;j++)
fatt=j*fatt;
return fatt;
}
double fattorialeRicorsivo(int Num)
{
if (Num==0)
return 1;
else
return Num*fattoriale(Num-1);
}
21
Un algoritmo ricorsivo deve essere completo, deve cioè sempre esistere
una soluzione qualunque sia l’input.
La completezza dipende dal dominio su cui si definisce l’algoritmo.
Esempio:
PotenzaN se definito sugli interi non è completo perché non funziona
per gli interi negativi (infatti N-1 per N negativo non raggiunge mai lo
0).
Diventa completo se il domino di definizione è quello dei numeri interi
positivi.
double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}
22
Dall’esempio precedente si ricava che nel caso di cattiva definizione
dell’algoritmo ricorsivo sia in termini di caso base che di chiamata
ricorsiva si genera uno Stack Infinito.
Ciò accade quando non si raggiunge mai il caso base.
Infatti nel caso dell’algoritmo per il calcolo delle potenze di N se N è
negativo sottraendo ad esso 1 ad ogni chiamata ricorsiva non
raggiugeremmo mai il caso base previsto per N=0.
double PotenzaN(double Xre,int N)
{
if (N==0)
return 1;
else
return Xre*PotenzaN(Xre,N-1);
}
23