1
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
Xp + a
Xp
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.
Volendo calcolare la radice di 2, seguiamo i primi passi dell’algoritmo:
Xp=1
Xs=(1+2)/2=1,5
Poniamo ora Xp=1,5
Xs=(1,5+2/1,5)/2=1,416
Poniamo ora Xp=1,416 e così via
2
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 è
A
A
cioè è uguale all’area del quadrato che cerchiamo. I lati sono invece
uno minore e uno maggiore del lato del quadrato.
3
Calcoliamo ora la media aritmetica delle misure dei due lati del
rettangolo,
A
Avremo ovviamente che h1 è maggiore di h.
Costruiamo un nuovo rettangolo i cui lati misurano h1
e
A
4
Avremo ancora che l’area del rettangolo, pari a
A
A
resta
uguale a quella del quadrato, mentre h1 è un valore approssimato
per eccesso del lato del quadrato, mentre
A
è 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
A
del rettangolo, otteniamo
h1 ma sempre minore di A.
dove ancora h2 è maggiore di
5
Reiteriamo il processo costruendo il rettangolo i cui lati misurano h2
e
A
. 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.
6
passo2
Al =400
passo3
h
passo1
A
10
40
25
16
A
h
A
20,5
A
Quadrato da costruire
19,5
………….
A
20
20
7
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 .
8
Un codice iterativo è il seguente:
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
// Calcola radice quadrata
main () {
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”);
}
9
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.
10
// La Radice Quadrata con il metodo di Erone
// DEFINIZIONI
double 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
11
ALGORITMI DI RICERCA LINEARE
Problema: Cercare tra i valori contenuti in un Array un preassegnato
valore.
Esempio: Data una lista di N numeri verificare se esiste un preassegnato
valore.
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.
12
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.
13
// MAIN
{
Algoritmo di ricerca: soluzione iterativa.
Indicatore= CercaIndice(Nome, NumeroElementi,ValoreCercato);
IF (Indicatore>=0)
cout<<ValoreCercato<<” è stato trovato nella posizione “<<Indicatore;
ELSE
cout<< ValoreCercato<<“ non è stato trovato “<<endl; }
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;
}
14
La versione ricorsiva dello stesso algoritmo è la seguente
int RicercaLinRic(int a[],int i, int Chiave)
{
if (i<0)
1° caso base
return -1;
else
{
// prendi un Candidato
2° caso base
if (a[i] == Chiave)
return i;
else
// rivedi il SubRange riducendo le dimensioni del problema
return RicercaLinRic(a, i-1, Chiave);
}
}
Chiamata ricorsiva
15
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.
16
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.
17
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.
18
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.
19
Un algoritmo iterativo per la ricerca binaria è il seguente:
// BINARIA ITERATIVA
// basso=indice più piccolo, alto=indice più grande del
vettore
int 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;
}
Si noti che la variabile i, inizialmente posta =-1, cambia solo se troviamo il
20
dato cercato, quindi se in uscita, la funzione ritorna -1, implica che il dato
cercato non è stato trovato.
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 BASE
else
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
21
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);
}
}
22
Esercizio
Scrivere 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.
23
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
24
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
25