1

2

Un caso di studio: il calcolo della radice quadrata.

Il modo più semplice per calcolare la radice quadrata di un numero “a” è quello di utilizzare un algoritmo molto antico, usato dai babilonesi, e riproposto da Erone, che consiste nell’utilizzare la formula ricorrente

Xs = _________________ 2

dove Xp è il valore precedente e Xs è quello successivo. Per poter applicare questa formula è necessario assegnare un valore iniziale a Xp; poiché Xp appare anche al denominatore poniamo come valore iniziale Xp=1.

Xp + a Xp

Volendo calcolare la radice di 2, seguiamo i primi passi dell’algoritmo: Xp=1 Xs=(1+2)/2=1,5Poniamo ora Xp=1,5 Xs=(1,5+2/1,5)/2=1,416Poniamo ora Xp=1,416 e così via

3

L’algoritmo di Erone di Alessandria (vissuto tra il I° e II° sec. d.C.) utilizza solo le quattro operazioni dell’aritmetica.

L’algoritmo si sviluppa sulla base di alcune osservazioni geometriche. Dato un numero A se costruiamo un quadrato di area A, il lato di questo quadrato sarà proprio la radice di A

Per costruire questo quadrato eseguiamo una serie di approssimazioni successive partendo da un rettangolo i cui lati misurano h e A/h, con h minore di A. L’area del rettangolo è

cioè è uguale all’area del quadrato che cerchiamo. I lati sono invece uno minore e uno maggiore del lato del quadrato.

AA

4

Calcoliamo ora la media aritmetica delle misure dei due lati del

rettangolo, Avremo ovviamente che h1 è maggiore di h.

Costruiamo un nuovo rettangolo i cui lati misurano h1 e

A

A

5

Avremo ancora che l’area del rettangolo, pari a resta

uguale a quella del quadrato, mentre h1 è un valore approssimato

per eccesso del lato del quadrato, mentre è un valore

approssimato per difetto.

La media aritmetica così ottenuta fornisce ora un valore h1 più

vicino a VA di quanto lo fosse h.

Calcolando di nuovo la media aritmetica delle misure dei due lati

del rettangolo, otteniamo dove ancora h2 è maggiore di

h1 ma sempre minore di A.

AA

A

A

6

Reiteriamo il processo costruendo il rettangolo i cui lati misurano h2

e . Avremo un valore approssimato per eccesso del lato del

quadrato e un valore approssimato per difetto. Il valore di h2 è però

più vicino a A di quanto lo fosse h1.

Proseguendo per questa strada, cioè con successive

approssimazioni, costruiamo due successioni di numeri che

approssimano, una per eccesso e una per difetto, la radice

quadrata di A.

A

7

Quadrato da costruire

l =400

passo1

h

10 40

25 16

passo2

20,5 19,5

………….

passo3

20 20

h

A

A

A

A

A

A

8

Nella prossima diapositiva si mostra l’algoritmo di Erone mediante

un algoritmo iterativo.

Viene richiesto il valore dell’approssimazione che si vuole ottenere

per il calcolo della radice quadrata () e quindi iterativamente, tramite

un ciclo si esegue l’algoritmo fin quando l’approssimazione ottenuta

non è minore di .

9

Un codice iterativo è il seguente:

#include <iostream>#include <cstdlib>#include <cmath>using namespace std;// Calcola radice quadratamain () {const float eps=0.000001; float a,x ; // precondizioni: a>=0 and eps>0 cout << " Calcolo della radice di a: a="; cin >> a; x=1.0; while (fabs(x-a/x)/2>=eps) x=(x+a/x)/2;//Postcondizioni: x>0 |x-a/x|<eps cout <<"Radice di "<< a <<"="<< x <<endl; system(“pause”);}

10

L’algoritmo di Erone si presta perfettamente ad una sua interpretazione

in chiave ricorsiva.

Il caso base è rappresentato dal raggiungimento del valore di

approssimazione richiesta, mentre la chiamata ricorsiva riproduce la

formula di Erone.

11

// La Radice Quadrata con il metodo di Erone

// DEFINIZIONIdouble radice(double a,double eps1,double &x1){ if ((fabs(x1-a/x1)/2)>=eps1) { x1=(x1+a/x1)/2; return radice(a,eps1,x1); }else return x1; }

Allegato: radice quadrata

12

ALGORITMI DI RICERCA LINEARE

Problema: Cercare tra i valori contenuti in un Array un preassegnatovalore.

Esempio: Data una lista di N numeri verificare se esiste un preassegnatovalore.

Un algoritmo ricorsivo, che risolva questa problema presenta due casi base:- la ricerca è finita se nessun elemento uguale a quello cercato esiste- la ricerca è finita se almeno un elemento uguale a quello cercato è

stato trovato

Supponiamo di partire dall’ultimo elemento della lista e risalire fino in cima nella ricerca dell’elemento.

13

Soluzione iterativa:

Gestire opportunamente l’indice dell’array in cui sono contenuti gli

elementi su cui fare la ricerca.

I criteri per stabilire il nuovo valore da attribuire all’indice possono

essere i più diversi.

E’ però importante che una volta stabilito che un elemento individuato

da un certo indice non è quello cercato questo elemento non venga più

esaminato. Di seguito si mostra una versione iterativa.

Si noti che poiché ad ogni passo della ricerca eliminiamo un elemento il massimo numero di passi che potranno essere eseguiti è pari al numero di elementi.

14

// MAIN

{ Indicatore= CercaIndice(Nome, NumeroElementi,ValoreCercato);

IF (Indicatore>=0)

cout<<ValoreCercato<<” è stato trovato nella posizione

“<<Indicatore;

ELSE

cout<< ValoreCercato<<“ non è stato trovato “<<endl; }

Algoritmo di ricerca: soluzione iterativa.

int CercaIndice(int Nome[], int NumeroElementi, int ValoreCercato)

int Indice;

bool Trovato;

{ while (Indice>0) && ( Trovato!=1)

{

if (Nome[Indice]==ValoreCercato)

Trovato= true

else

Indice= Indice-1; }

return Indice;

}

15

La versione ricorsiva dello stesso algoritmo è la seguente

int RicercaLinRic(int a[],int i, int Chiave){if (i<0)

return -1;else {// prendi un Candidato

if (a[i] == Chiave) return i;else

// rivedi il SubRange riducendo le dimensioni del problema

return RicercaLinRic(a, i-1, Chiave); }}

Chiamata ricorsiva

2° caso base

1° caso base

16

Caratteristiche di una ricerca ricorsiva

• Una chiamata ricorsiva implica sempre una riduzione del sub

range di possibili candidati. Quindi nell’intestazione è presente

almeno un parametro che rappresenta il subrange di elementi. Il

valore del parametro in ogni istante di computazione è funzione di

un qualche subrange candidato locale. Questa espressione, i cui

valori devono rappresentare una riduzione del subrange candidato,

viene calcolata e al successivo processo di ricerca i valori ottenuti

vengono applicati.

17

Caratteristiche di una ricerca ricorsiva

•La condizione di terminazione è espressa in termini dei parametri

del subrange candidato. Questa condizione rappresenta il caso base

quando non restano altri subrange candidati alla ricerca.

• L’altro caso base si ha quando la ricerca ha buon esito, quando

cioè a[Candidato] coincide con Chiave.

18

Ricerca binaria

Assegnato un vettore ordinato A di interi, di dimensione N,

determinare la posizione di un elemento mediante una ricerca

binaria.

Ricordiamo che la ricerca binaria si basa sulla tecnica del divide

et impera.

19

Ricerca binaria

Dividiamo gli elementi in due parti; essendo tutti gli elementi

ordinati, confrontiamo l’elemento cercato x con il valore M che

separa le due parti: se x<M allora dobbiamo continuare a cercare

nella prima parte, altrimenti cercheremo nella seconda parte.

Dividiamo la parte scelta ancora in due e applichiamo sempre il

ragionamento precedente. L’algoritmo termina o quando l’ultimo

elemento rimasto dalle successive suddivisioni è uguale a quello

cercato, oppure quando l’intervallo rimasto non è più suddivisibile

il che implica che il nostro elemento non appartiene al vettore.

20

// BINARIA ITERATIVA // basso=indice più piccolo, alto=indice più grande del vettoreint RicercaBinIter ( int vet[], int basso, int alto, int x) { int medio, i=-1; while ((basso<=alto) && i==-1) { medio=(basso+alto)/2; if (vet[medio]==x) i=medio ;

else if (vet[medio]<x) basso=medio+1;

else alto=medio-1; } return i;}

Un algoritmo iterativo per la ricerca binaria è il seguente:

Si noti che la variabile i, inizialmente posta =-1, cambia solo se troviamo il dato cercato, quindi se in uscita, la funzione ritorna -1, implica che il dato cercato non è stato trovato.

21

Ricerca binaria ricorsiva

Scriviamo la funzione tenendo presente che vet[] è il vettore di interi, x è l’elemento da cercare, basso rappresenta l’indice minimo, alto quello massimo del vettore di interi

int RicercaBinRic (int vet[],int x, int basso, int alto ) if (basso>alto) // è stato analizzato tutto il vettore senza trovare l’elemento x: primo CASO BASEelse Medio = (basso+alto) / 2; if (vet[Medio]==x) // la funzione deve restituire l’indice Medio : secondo CASO-BASE else if (vet[Medio] < x)// deve richiamare le funzione nella metà superiore dell’array else// deve richiamare le funzione nella metà inferiore dell’array

22

Il codice è pertanto il seguente.

int RicercaBinRic (int vet[],int x, int basso, int alto ) {int Medio;if (basso>alto) return -1;else { Medio = (basso+alto) / 2; if (vet[Medio]==x) return Medio; else if (vet[Medio] < x)

return RicercaBinRic (vet, x, Medio+1, alto); else

return RicercaBinRic (vet, x, basso, Medio-1); }}

23

EsercizioScrivere una funzione ricorsiva che ritorna vero se gli elementi di UnArray di interi, con valori assegnati nel subrange 1..TotElem, sono in ordine crescente.

Obiettivo: ricercare un elemento che sia fuori ordine in un dato subrange.Ridurre di volta in volta il subrange fino a quando in questo resta un solo elemento allora vuol dire che la ricerca è finita e la risposta è TRUE.Se invece si verifica che è vera l’espressione

UnArray[N-1]>UnArray[N]questo significa che è stato trovato un elemento non in ordine e la funzione ritorna FALSE.

24

ESERCIZIO

Con una function ricorsiva, utilizzando la tecnica

dell’INSERTION SORT, inserire in maniera ordinata, in

un array di numeri interi, i valori letti da tastiera fin

quando non si introduce lo 0.

insfinale

25

void InsertionRic(int a[], int &fine,int j, int &elemento){ if (elemento==0) return; else if (j==0) { a[0]=elemento; fine=fine+1; cout<<" Elemento "; cin>>elemento; return InsertionRic(a,fine,fine,elemento); } else { if (a[j-1]>elemento) { a[j]=a[j-1]; return InsertionRic(a,fine,j-1,elemento); } else { a[j]=elemento; fine=fine+1; cout<<" Elemento "; cin>>elemento; return InsertionRic(a,fine,fine,elemento); } } }

Allegato insertion