Programmazionericorsione e divide et impera

Alessandra Raffaetà

Università Ca’ Foscari VeneziaCorso di Laurea in Informatica

Ricorsione

La ricorsione è un modo classico di affrontare un problema riducendolo a un insieme di sottoproblemi dello stesso tipo, ma più semplicida risolvere. In generale una procedura ricorsiva ha la forma:

void foo (tipoParametro p) {if (p == casoBase1)

comandoBase1else

……foo(p’) /* p’ è un’espressione di tipo

tipoParametro tale che p’ < p */……

}

Una procedura ricorsiva …

Chiama se stessa ricorsivamente.

Ha una o più condizioni di terminazione.

Ad ogni chiamata ci si avvicina alla condizione di terminazione.

Esercizio

Problema: Trovare il massimo elemento di un array non vuoto.

TipoElem massimo (TipoElem v[ ], int dim) {TipoElem max;if (dim == 1)

return v[0];

max = massimo(v, dim - 1);if (maggiore(max, v[dim - 1]))

return max; return v[dim - 1];

}Chiamata della funzione: ris = massimo(v, dim);

Seconda soluzione

TipoElem massimotl (TipoElem v[ ], int dim, TipoElem max) {if (dim == 0)

return max;

if (maggiore(v[dim - 1], max))max = v[dim - 1];

return massimotl(v, dim – 1, max);}

Chiamata della funzione: ris = massimotl(v, dim – 1, v[dim - 1]);

Ricerca lineare ricorsiva

int riclineareRic (TipoElem v[ ], int dim, TipoElem elem) { if (dim == 0) /*il vettore è vuoto */

return -1;

if (equal(elem, v[dim - 1]))return dim - 1; /*l’elemento è stato trovato */

return riclineareRic(v, dim – 1, elem);}

Restituisce lo stesso risultato della ricerca lineareiterativa?

Ricerca binariaAssunzione: l’array v è ordinato.

Ricerca binaria: Si confronta l’elemento x dacercare con l’elemento m in posizione centraledell’array v. □ Se x è uguale a m ho finito.□ Se x è minore di m, la ricerca prosegue nella metà

inferiore dell’array.□ Se x è maggiore di m, la ricerca prosegue nella metà

superiore dell’array.

Il processo prosegue fino al reperimento di x oppure fino all’esaurimento dell’array nel qualcaso x non è presente in v.

Algoritmo per la ricerca binaria

int ricercabinaria (TipoElem v[ ], TipoElem elem, int inf, int sup) { int med, indice;if (inf > sup) /*la parte del vettore fra inf e sup è vuota */

indice = -1;else {

med = (inf + sup)/2;if (equal(elem, v[med]))

indice = med; /*l’elemento è stato trovato */else

if (minore(elem, v[med])) /*cerca nella parte inferiore*/indice = ricercabinaria(v, elem, inf, med -1);

else /*cerca nella parte superiore*/ indice = ricercabinaria(v, elem, med+1, sup);

}return indice;

}Chiamata della funzione: risultato = ricercabinaria(v, elem, 0, dim–1);

Esempio di ricerca binaria

60555133257

0 1 2 3 4 5

3

med = 2

605551

3 4 5

51

60555133257

0 1 2 3 4 5

v

Dato il vettore v ordinato, determinare l’indice di 51 se occorre in v.

med = 4

med = 3

L’elemento è stato trovato e la sua posizione in v è 3.

Tecnica di progetto di algoritmi: divide et impera

Soluzione ricorsiva di un problema articolata in 3 passi:Divide: divisione del problema originale in sottoproblemianaloghi a quello originale, ma di dimensione inferiore.

Impera: soluzione ricorsiva dei sottoproblemi; se la dimensione dei sottoproblemi è sufficientemente piccola, questi possono essere risolti direttamente.

Combina: composizione delle soluzioni dei sottoproblemiper ottenere una soluzione del problema originale.

Esempio di tecnica divide et imperaProblema: Trovare il massimo elemento di un array non vuoto.

Divide: divide l’array A[inf..sup] in due sottoarray con metà elementi, A[inf..med] e A[med+1..sup] dove med = (inf+sup)/2.Impera: trova i max applicando la funzionericorsivamente ai sottoarray se il sottoarray ha almeno due elementi, altrimenti il max èl’elemento stesso.Combina: confronta i due max trovati di A[inf..med] e A[med+1..sup] e restituisce il max dei due al fine di ottenere il max di A[inf..sup].

Funzione massimo – divide et imperaTipoElem massimo (TipoElem v[ ], int inf, int sup) {/*Trova il massimo degli elementi del vettore v di indice compreso tra inf e sup */

int med;TipoElem m1, m2;if (inf == sup) /* impera: risolve direttamente */

return v[inf];

med = (inf + sup)/2; /* divide: il problema in 2 sottopb */m1 = massimo(v, inf, med); /*impera: trova max parte inferiore*/m2 = massimo(v, med + 1, sup); /*impera:trova max parte superiore*/

if (m1 > m2) /*combina: trova max del vettore*/return m1;

return m2;}

EsercizioDato un vettore v contenente (n > 0) interi positivi, sideve stabilire se la somma di tutti gli elementi di v siapari o dispari senza eseguire addizioni.

int sommaPari (int v[ ], int inf, int sup) {

int med, ris1, ris2;if (inf == sup)

return (v[inf] % 2 == 0);

med = (inf + sup)/2; /* divide: il problema in 2 sottopb */ris1 = sommaPari(v, inf, med); /*impera: trova pari parte inf*/ris2 = sommaPari(v, med + 1, sup); /*impera:trova pari parte sup*/

return (ris1 == ris2); /*combina: trova max del vettore*/}

Algoritmo di ordinamento: mergesort

Algoritmo di tipo divide et impera.

Divide: divide l’array v[p..u] in due sottoarray con metà elementi, v[p..med] e v[med+1..u] dove med = (p+u)/2.

Impera: ordina ricorsivamente i sottoarrayusando il mergesort se il sottoarray ha almenodue elementi, altrimenti il sottoarray è ordinato.

Combina: fondi insieme i due sottoarray ordinativ[p..med] e v[med+1..u] al fine di ottenere un array ordinato v[p..u].

La procedura mergesort

void mergesort (TipoElem v[ ], int iniziale, int finale) {/*Ordina gli elementi del vettore v di indice compreso tra iniziale e

finale */ int med;if (iniziale < finale) {

med = (iniziale + finale)/2;mergesort(v, iniziale, med);mergesort(v, med + 1, finale);merge(v, iniziale, med, finale);

}}

Esempio: le chiamate ricorsive di mergesort

0 1 2 3 4 5

94752381

6 7

0 1 2 3

2381

4 5

9475

6 7

0 1

81

2 3

23

4 5

75 94

6 7

0

1

1

8

2

3

3

2

4

5

5

7

6

4

7

9

La procedura mergeIdea: Da due mazzetti ordinati di carte vogliamo farneun terzo mettendo di volta in volta la carta più piccolatra le due in cima ai due mazzetti. Questo si ripete finoa quando uno dei due mazzetti finisce. Le carte restantisono aggiunte in fondo.

void merge (TipoElem v [ ], int iniziale, int med, int finale) {/*Fonde i due sottoarray ordinati di v da iniziale a med e da med+1 a

finale in un unico sottoarray ordinato da iniziale a finale */

TipoElem buf [DIM]; /* vettore di appoggio */ int primo,secondo, appoggio,i;primo = iniziale;secondo = med +1;appoggio = iniziale;

La procedura merge (cont.)

while (primo <= med && secondo <= finale) {if (minoreUguale(v [primo], v [secondo])) {

buf [appoggio] = v [primo];primo ++;

}else {

buf [appoggio] = v [secondo];secondo ++;

}appoggio++;

}

La procedura merge (cont.)

if (secondo > finale) /* è finito prima il secondo sottoarray; copia da v in v stesso tutti gli elementifino a med, cominciando dal fondo */

for (i= med; i>=primo; i--) { v[finale] = v[i];finale --;

}/* copia tutti gli elementi da iniziale a appoggio – 1 da buf a v */

for (i = iniziale; i < appoggio; i++)v[i] = buf[i];

}

Come funziona la procedura merge

Primo ciclo: Finché le due sottosequenze sono non vuote preleva l’elemento più piccolo in cima allesottosequenze.Secondo ciclo: Disponi in posizione corretta glielementi rimasti nella prima sottosequenza se non vuota.□ Osservazione: se la sottosequenza vuota è la prima non

occorre fare alcuna operazione poiché gli elementisono già in posizione corretta in base all’ordinamento.

Terzo ciclo: Trasferisci gli elementi dal vettoredi appoggio nella posizione corrispondente nelvettore di partenza.

Esempio di calcolo della procedura merge

0 1 2 3 4 5

98754321

6 7

0 1 2 3

83214 5

97546 7

0 1

81

2 3

32

4 5

75 94

6 7

0

1

1

8

2

3

3

2

4

5

5

7

6

4

7

9