1

2

Esaminiamo ora un altro esempio:

Il calcolo della potenza ennesima di un dato numero.

3

DIMOSTRAZIONE PER INDUZIONEPOTENZE

Vogliamo dimostrare che S(n): a)1 nn XXX

caso basePoniamo n=1 avremo che è quindi dimostrato vero

XX

XXX 01

Avendo supposto vero l’asserto sostituiamo in b) il valore che si ottiene da a)

passo induttivoDobbiamo ora dimostrare che b)

n1n XXX

nn XXXX

q.e.d.

4

double PotenzaN(double Xre,int N){ if (N==0)

return 1; else

return Xre*PotenzaN(Xre,N-1);}

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.

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

5

PotenzaN(0.9,3)

N=0?No

PotenzaN(0.9,2)

PotenzaN(0.9,2) PotenzaN(0.9,1)

N=0?No

PotenzaN(0.9,0)

PotenzaN(0.9,0)

PotenzaN(0.9,1)

N=0?No

N=0?Si

PotenzaN 1

PotenzaN 0.9*PotenzaN 0.9*PotenzaN 0.9*

PotenzaN(0.9,3)

double PotenzaN(double Xre,int N){ if (N==0)

return 1; else

return Xre*PotenzaN(Xre,N-1);}

0.9*PotenzaN(0.9,3)

0.9*PotenzaN(0.9,2)

0.9*PotenzaN(0.9,1)

0.9*PotenzaN(0.9,0) =1

=0.9*1

=0.9*0.9

=0.9*0.9*0.9

6

ESERCIZIO

Scrivere una funzione ricorsiva che, assegnati due interi N1 ed N2, restituisca la somma di tutti gli interi compresi tra N1 ed N2.

7

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.. non ha divisori tranne il numero 1.

N

8

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");}

ESERCIZIOScrivere un algoritmo ricorsivo per determinare se un assegnato numero intero positivo N è primo.

9

bool primo(int n,int P){ if (P<2) return true; else if (n%P==0) return false; else return primi(n,P-1);}

Allegato: numeriprimi

// Caso base: non ha trovato alcun divisore di kn

// Esiste almeno un divisore di kn diverso da 1

// Chiamata ricorsiva su un valore di kn minore

10

Esercizio

Scrivere un algoritmo ricorsivo per determinare quanti numeri primi ci sono in un preassegnato intervallo K1..K2 di numeri interi positivi.

Allegato: NumeriPrimiIntervallo3

11

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)

12

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.

13

NR

RR’ R’

M

MCD=R’

ALGORITMO DI EUCLIDE

14

Pseudo codiceIF M o N sono valori che rappresentano una soluzione valida

MCD valore della soluzione (M o N) ELSE

MCD MCD(N, M MOD N)

Un algoritmo ricorsivo per il calcolo del MCD tra M e N può essere il seguente:

15

Di seguito si mostrano le versioni iterativa e ricorsiva per il calcolo del MCD secondo l’algoritmo di Euclide.

int MCD(int m,n) {

int Resto=m%n; while (Resto !=0) { m=n; n=Resto; Resto= m % n; } return n; }

int MCD(int m,int n) { if (n==0) return m; else return MCD(n, m%n ) }

VERSIONE ITERATIVA VERSIONE RICORSIVA

16

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.

17

MCD(30,18)

N=0?No

MCD(18,12)

MCD(18,12)

N=0?No

MCD(12,6)

MCD(12,6)

N=0?No

MCD(6,0)

N=0?Si

MCD 6

MCD(6,0)

MCDMCD MCD

MCD(int m, n)

MCD(30,18)

MCD(18,12)

MCD(12,6)

MCD(6,0) =6

=6

=6

=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 7 6 5 4 3 2 1

                                                           

                                                           

 

                                                           

18

caso basePoniamo MCD(M,0)=M

passo induttivoDobbiamo ora dimostrare che MCD(M’,N’)=MCD(N, M MOD N)

DIMOSTRAZIONE PER INDUZIONE DELLA CORRETTEZZA DELL’ALGORTIMO RICORSIVO PER IL MCD

Supponiamo MCD(M’,N’)=X

allora M’=hX e N’=zX dove h e z sono interi

essendo N’=M MOD N 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)

19

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 bacacb cabcba 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 bacacb cabcba bca

20

Si definisce FATTORIALE di un numero N il prodotto di tutti i numeri da 0 a N come di seguito definito:

1*)2(**)2N(*)1N(*N!N

1!0

.......

Di seguito sono mostrati gli algoritmi e relativi codici iterativi e ricorsivi

21

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);

}

22

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);}

23

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);}