RICORSIONE & ITERAZIONE Riconsideriamo lesempio del Massimo Comun Divisore visto tempo addietro: m,...

RICORSIONE & ITERAZIONE

Riconsideriamo l’esempio del MassimoComun Divisore visto tempo addietro:

m, se m=n

MCD(m, n-m), se m<n

MCD(m, n) = MCD(m-n, n), se m>n


Questo esempio era stato traspostonella funzione seguente:

int mcd(int m, int n){ return (m==n) : m ? (m>n) ? mcd(m-n, n) : mcd(m, n-m);

}

L’esempio era particolare perché il risultatoveniva sintetizzato in avanti, anziché all’in-dietro come nei processi ricorsivi.


Ogni processo computazionale che computi “in avanti”, per accumulo, costituisce una ITERAZIONEossia è un processo computazionale iterativo.

Ogni soluzione sintatticamente ricorsiva che dia luogo a un processo computazio-nale iterativo costituisce una ricorsione solo apparente: una ricorsione tail.


La caratteristica fondamentale di unprocesso computazionale ITERATIVOè che a ogni passo è disponibile un risultato parziale

dopo k passi, si ha a disposizione il risultato parziale relativo al caso k

questo non è vero nei processi computazionali ricorsivi, in cui nulla è disponibile finché non si è disgregato il problema fino al caso elementare.

IL RAGIONAMENTO ITERATIVO

Si basa sulla disponibilità di una variabile, detta accumulatore, destinata a esprimere in ogni istante la soluzione corrente

Si imposta identificando quell’operazione di modifica dell’accumulatore che lo porta a esprimere, dal valore relativo al passo k, il valore relativo al passo k+1.

ESEMPIO: CALCOLO DEL FATTORIALE

Definizione:

n! = 1 * 2 * 3 *… * n

Detto vk = 1 * 2 * 3 *… * k:

1! = v1 = 1

(k+1)! = vk+1 = (k+1) * vk per k1

n! = vn per k=n

ESEMPIO: CALCOLO DEL FATTORIALE

int fact(int n){

return factIter(n,1,1);

}

int factIter(int n, int v, int k){

return (k==n) ? v :factIter(n, (k+1)*v, k+1);

}

INVARIANTI

Un invariante di programma è una relazionesempre vera in un dato punto del program-ma.

Esempio:

double power(double b, int k){ return (k<=0) ? 1 : powerIt(b,k,b,1);}

Invariante di programma:è sempre vero che qui k>0

INVARIANTI DI CICLO

Un invariante di ciclo è una relazione sem-pre vera, in un dato punto del programma,a ogni iterazione.

• Identificare un invariante di ciclo è una forma di progetto.

• Invarianti diversi suggeriscono di norma algoritmi diversi, che quasi sempre hanno diversa efficienza.

PROBLEMA: CALCOLO DI bk

Un approccio iterativo

Posto bk = vk, si può scrivere:

b0 = v0 = 1 per i=0

bi = vi = b * bi-1 = b * vi-1 per i>0in particolare:

bk = vk per i=k

Un possibile invariante: bk = vi * bk-i


Perché bk = bk-i *vi è un invariante?

Al generico passo 0<i<k, bk = vi * bk-i

Moltiplicando e dividendo per b:

bk = (vi *b) * bk-i-1 = vi+1 * bk-(i+1)

che è l’invariante al passo (i+1)-esimo.In particolare:• per i=0, bk = v0 * bk = bk purché v0 =1

• per i=k, bk = vk * b0 = vkcondizione iniziale


Come usarlo per progettare l’algoritmo?• inizialmente, v = v0 =1

• a ogni passo si deve trasformare l’invariante bk = vi * bk-i nella formabk = vi+1 * bk-(i+1) che deve assumere al passo successivo

• ciò si ottiene ponendo, a ogni passov’ = b * v i’ = i + 1

CALCOLO DI bk : L’INVARIANTE

double powerIt(double b, int k, double v, int i){

return (i==k) ? v :powerIt(b,k,v*b,i+1);

}

double power(double b, int k){ return (k==0) ? 1 : powerIt(b,k,1,0);}

V0=1 i=0

V’ = Vi+1 = Vi* b

i’ = i+1

PROGETTARE bk PER INVARIANTI

Partendo da relazioni diverse si ottengonoapprocci diversi, con diversa efficienza.

Un diverso invariante:

• k=0 b0 = 1• k>0 k pari bk = (b2) k/2

k dispari bk = b * bk-1

b*b: non richiede disaper fare potenze

richiede di saper fare un prodotto


Come usarlo per progettare l’algoritmo?

• a ogni passo si deve riscrivere bk in una delle due forme date

• ciò si ottiene ponendo, a ogni passo– se k è pari: b’ = b * b k’ =

k/2– se k è dispari: b’ = b k’ = k-1

e moltiplicando per brichiede una operazione dopo la fase

di modifica di b e k soluzione ricorsiva


boolean odd(int n){return n%2==1;

}

double pow(double b, int k){

return (k==0) ? 1 :

odd(k) ? pow(b, k-1) * b :

pow(b*b, k/2);

}

ricorsione non-tail

(Complessità dell’ordine di log2 k)


UN APPROCCIO ITERATIVO

Un ulteriore invariante: bk = t * vn

• k=0 n=0, t=1 bk = t * v0 = 1• k>0

– se n è pari: bk = t * (v2) n/2

– se n è dispari: bk = t * v * vn-1


Progetto dell’algoritmo:• a ogni passo si deve trasformare

l’invariante bk = t * vn in una delle due forme date

• ciò si ottiene ponendo:– se n è pari n’ = n/2, t’ = t, v’ = v2

– se n è dispari n’ = n-1, t’ = t*v, v’ = v

Interessante: b e k in realtà non si usano!


boolean odd(int n){return n%2==1;}

double powIt(double b, int k, double t, double v, int n){

return (n==0) ? t :

odd(n) ? powIt(b,k,t*v,v,n-1) :

powIt(b,k,t,v*v,n/2);

}Come previsto, b e k non servono!Quindi li possiamo togliere…!!



double powIt(double t, double v, int n){return (n==0) ? t : odd(n) ? powIt(t*v, v, n-1) :

powIt(t, v*v, n/2);}

double power(double b, int k){ return (k==0) ? 1 : powIt(1,b,k);}

ESERCIZIO: MOLTIPLICAZIONE

Obiettivo: calcolare p = x* y

Sfruttiamo l’invariante: y = Q * B + R

dove• B è un intero positivo• Q (quoziente) = y/B• R (resto) = y%B


Obiettivo: calcolare p = x* y

Sostituendo:p = x * y = x* (Q * B + R) = = x * (B * (y/B)) + x*(y%B)

Caso particolare: y=0p = x * y = x*0 = 0


Approccio ricorsivo: si applica direttamente la relazionetrovata p = x*B * (y/B) ) + x*(y%B)

Ad esempio, scegliendo B=2:

int MulNatR(int x, int y){return (y==0) ? 0 :

MulNatR(x*2, y/2) + x*(y%2);}

Occorre fare un’operazione dopo la chiamata ricorsiva ricorsione non-tail


Approccio ricorsivo: si applica direttamente la relazionetrovata p = x*B * (y/B) ) + x*(y%B)

Ad esempio, scegliendo B=2:

int MulNatR(int x, int y){return (y==0) ? 0 :

MulNatR(x*2, y/2) + x*(y%2);}

Operazione primitiva che suppo-niamo di saper già fare (è una moltiplicazione per 0 o per 1)

Operazioni primitive che supponiamo di sa-per già fare (moltiplicazione/divisione per 2)


Verso un approccio iterativoCerchiamo un invariante di ciclo

p = x * y + zPonendo y=Q*B+R e trasformando:

p = (x*B) * Q + (x*R + z) = x’ * y’ + z’

dove si è posto

y’ = Q = y/B, x’ = x*B, z’ = z + x*R

Caso particolare: y=0 p = z


Invariante di ciclo: p = x * y + z

Trasformazione: p = x’ * y’ + z’y’ = Q = y/B, x’ = x*B, z’ = z + x*R

int MulNatIt(int x, int y, int z){ return(y==0) ? z : MulNatIt(x*2, y/2, z+x*(y%2));

}

Operazioni primitive: supponiamo di saper giàmoltiplicare, dividere e modulare per 2.


Perché supponiamo di saper già moltiplicare,e dividere per 2 (trovando anche il resto) ?

Perché l’elaboratore è intrinsecamente capacedi farlo nella propria ALU:• moltiplicazione per 2 = shift a sinistra (<<) • divisione per 2 = shift a destra (>>) • moltiplicazione per (y%2) =

0, se y è pari (y%2 vale 0)y, se y dispari (y%2 vale 1)


Il codice finale che ne risulta:

int MulNatIt(int x, int y, int z){ return (y==0) ? z : odd(y): MulNatIt(x<<1, y>>1, z+x) : MulNatIt(x<<1, y>>1, z);

}


y%2 = 1

y%2 = 0y/2x/2

UNA RIFLESSIONE DI FONDO

• L’impostazione funzionale è sempre costruttiva. Ma si può sempre solo creare?

• Perché creare una versione nuova di un accumulatore ad ogni passo, quando l’elaboratore di Von Neumann permette la modifica del contenuto di una cella di memoria?

UNA PROPOSTA

• È possibile riusare una stessa area dati senza bisogno di crearne una nuova ad ogni passo computazionale?

• Ci sono controindicazioni?

VARIABILI NEI LINGUAGGI IMPERATIVI

Una variabile in un linguaggio imperativo non è solo un sinonimo per un dato come

in matematica è un’astrazione della cella di memoria associata a due diverse informazioni:

il contenuto (R-value) l’indirizzo a cui si trova (L-value)

3.22x

ESPRESSIONI CON EFFETTI COLLATERALI

Le espressioni che contengono variabili, oltre a denotare un valore, possono a volte comportare effetti collaterali sulle variabili coinvolte.

Un effetto collaterale è una modifica del valore della variabile (R-value) causato da particolari operatori: operatore di assegnamento operatori di incremento e decremento

ASSEGNAMENTO

• L’assegnamento è un particolare tipo di espressione– come tale denota comunque un valore!!

con un effetto collaterale: quello di cambiare il valore della variabile.

• Sintassi

variabile = espressione

• Esempi di espressioni di assegnamento:j = 0 k = j + 1

ASSEGNAMENTO

L’espressione di assegnamento

variabile = espressione denota il valore dell’ espressione ma cambia anche il valore della

variabile: il nuovo valore della variabile è quello denotato dalla espressione.

ESEMPIO

Se k valeva 2, l’espressione

k = 7 denota il valore 7 e cambia il valore di k,

che d’ora in poi vale 7 (non più 2)

ESEMPIO

Se k valeva 2, l’espressione

j = k+1 denota il valore 3 e cambia il valore di j,

che d’ora in poi vale 3 (qualunque valore avesse prima)

L’assegnamento è distruttivo

ESPRESSIONI DI ASSEGNAMENTO

Il valore denotato dall’espressione diassegnamento può essere usato in altreespressioni. Ad esempio,

3 + (k=7) denota il valore 10 e cambia in 7 il valore di k

ASSEGNAMENTO & VARIABILI

Una variabile in una espressione diassegnamento: è intepretata come il suo R-value, se

compare a destra del simbolo =

è intepretata come il suo L-value, se compare a sinistra del simbolo =

3.22x

ESEMPIO

Se x valeva 2, l’espressione

x = x + 1 denota il valore 3 e cambia in 3 il valore di x

il simbolo x a destra dell’operatore = denota il valore attuale (R-value) di x, cioè 2

il simbolo x a sinistra dell’operatore = denota la cella di memoria associata a x (L-value), a cui viene assegnato il valore dell’espressione di destra (3)

l’espressione nel suo complesso denota il valore della variabile dopo la modifica, cioè 3.

ASSEGNAMENTO: ASSOCIATIVITÀ

• Come tutti gli operatori, anche l’operatore di assegnamento deve avere una sua associatività

k = j = 1

Prima k=j, o prima j=1 ?

l’operatore di assegnamento è associativo a destra: ciò consente espressioni di assegnamento multiplo

ASSEGNAMENTO: ASSOCIATIVITÀ

Esempi

k = j = 1 interpretato come k = (j = 1)

i = j = k = 0 interpretato come i = (j = (k=0))

i = k + 5 = 6 NO: k+5 non ha un L-value!

Nota: anche volendo, sarebbe stato impossibile farloassociativo a sinistra, in quanto ciò avrebbe resomolte espressioni prive di significato. Ad esempio:

k = j = 2 interpretato come (k=j) = 2 ???Equivarrebbe a scrivere 1 = 2 !!!!

INCREMENTO (++) E DECREMENTO (--)

Gli operatori di incremento e decrementosono usabili in due modi

• come pre-operatori: ++v

• come post-operatori: v++

prima incremento, poi uso

prima uso, poi incremento

ESEMPI

int i, j, k = 5;i = ++k /* i vale 6, k vale 6 */

i = k++ /* i vale 5, k vale 6 */

int i=4, j, k = 5;j = i + k++; /* j vale 9, k vale 6 */

j = ++k - k++; /* in cerca di guai! */

ATTENZIONE…!!

int k = 6;j = ++k - k++; /* in cerca di guai! */

Detti x = ++k e y = k++,• è certo che l’espressione venga valutata

come j = x - y (da sinistra a destra)• è certo che alla fine k valga 8• ma non si sa se venga calcolato prima x o

prima y, e qui la cosa fa molta differenza!– se prima x, poi y j = 7 - 7 = 0– se prima y, poi x j = 8 - 6 = 2

UN ESEMPIO

main() { int f, c = 20;

f = 32 + c * 9 / 5;}

L’espressione f = 32 + c * 9 / 5 recupera l’ R-value della variabile c calcola il corrispondente valore Fahrenheit e lo

assegna alla variabile f (interpretata come L-value effetto collaterale)

scarta il valore denotato dall’espressione di assegnamento (che non viene più utilizzato)

Ad esempio, se c vale 20, l’espressione vale 68...

… quindi a f viene asse-gnato il valore 68.

L’espressione f=68 denotaancora 68, che però viene

scartato.

ISTRUZIONI

• Le istruzioni esprimono azioni che, una volta eseguite, comportano una modifica permanente dello stato interno del pro-gramma o del mondo circostante.

• Le strutture di controllo permettono di aggregare istruzioni semplici in istruzioni più complesse.

ISTRUZIONI

• Una istruzione C è espressa dalle seguenti produzioni:

<istruzione> ::= <istruzione-semplice>

<istruzione> ::= <istruzione-di-controllo>

<istruzione-semplice> ::= <espressione> ;

• Quindi, qualsiasi espressione seguita da un punto e virgola è una istruzione semplice.

ESEMPI DI ISTRUZIONI SEMPLICI

x = 0; y = 1; /* due istruzioni */

x = 0, y = 1; /* una istruzione */

k++;

3; /* non fa nulla */

; /* istruz. vuota*/

ISTRUZIONI DI CONTROLLO

Una istruzione di controllo può essere:• una istruzione composta (blocco)• una istruzione condizionale (selezione)• una istruzione di iterazione (ciclo)

come specificato dalla produzione:

< istruzione-di-controllo > ::=<blocco> | <selezione> | <iterazione>

ISTRUZIONI DI CONTROLLO

Le istruzione di controllo sono alla base dellaprogrammazione strutturata (Dijkstra, 1969).

Concetti chiave:• concatenazione o composizione • selezione o istruzione condizionale

ramifica il flusso di controllo in base al valore vero o falso di una espressione (“condizione di scelta”)

• ripetizione o iterazioneesegue ripetutamente un’istruzione finché rimane vera una espressione (“condizione di iterazione”)

TEOREMA DI JACOPINI-BÖHM

• Le strutture di concatenazione, iterazione e selezione costituiscono un insieme completo in grado di esprimere tutte le funzioni calcolabili.

• Dunque, l’uso di queste sole strutture di controllo non limita il potere espressivo.

• La dimostrazione del teorema è basata sulla Turing-equivalenza di un “mini-linguaggio” che fornisca solo tali strutture di controllo.

BLOCCO

<blocco> ::= { [ <dichiarazioni e definizioni> ]

{ <istruzione> }

}• dopo un blocco non occorre il

punto e virgola (esso termina le istruzioni semplici, non separa istruzioni)

I1

I2

I3

In

Lo scope dei simboli che compaiono entro il blocco è il blocco stesso

ESEMPIO DI BLOCCO

main() { /* INIZIO BLOCCO */ const float F1=9.0, F2=5, SH=32; int c, f, temp = 20; char scala = 'C'; c = (scala != 'F') ? temp : (F2 / F1 * (temp - SH)) ; f = (scala != 'F') ? (SH+temp*F1/F2)

: temp;} /* FINE BLOCCO */

..una nota “en passant”...

main() { /* INIZIO BLOCCO */ const float F1=9.0, F2=5, SH=32; int c, f, temp = 20; char scala = 'C'; c = (scala != 'F') ? temp : (F2 / F1 * (temp - SH)) ; f = (scala != 'F') ? (SH+temp*F1/F2)

: temp;} /* FINE BLOCCO */

Il qualificatore const rendequeste variabili non modificabili

ESEMPIO DI BLOCCHI ANNIDATI

main() { /* INIZIO BLOCCO ESTERNO */ const float F1=9.0, F2=5, SH=32; int c, f, temp = 20; { /* INIZIO BLOCCO INTERNO */ char scala = ‘C’; c = (scala != 'F') ? temp : (F2 / F1 * (temp - SH)) ; f = (scala != 'F') ? (SH+temp*F1/F2)

: temp; } /* FINE BLOCCO INTERNO */} /* FINE BLOCCO ESTERNO */

ISTRUZIONI CONDIZIONALI

<selezione> ::=

<scelta> | <scelta-multipla>• la seconda non è essenziale, ma migliora

l’espressività.• l’espressione condizionale ternaria (.. ? … : …)

fornisce già un mezzo per fare scelte, ma è poco leggibile in situazioni di medio/alta complessità. L’istruzione di scelta fornisce un altro modo per esprimere alternative.

ISTRUZIONE DI SCELTA SEMPLICE

<scelta> ::= if <condizione> <istruzione1> [ else <istruzione2> ]

condizionevera falsa

istruzione2istruzione1

Una espressione logica o relazionale,che viene valutata al momento della

esecuzione dell’istruzione if.

ISTRUZIONE DI SCELTA SEMPLICE

<scelta> ::= if <condizione> <istruzione1> [ else <istruzione2> ]

condizionevera falsa

istruzione2istruzione1

La parte else è opzionale:se omessa, in caso di

condizione falsa si passasubito all’istruzione che

segue l’if.

ESEMPIO DI ISTRUZIONE if

• <istruzione1> e <istruzione2> sono ciascuna una singola istruzione

• Qualora occorra specificare più istruzioni, si deve quindi utilizzare un blocco.

if (n > 0) { /* inizio blocco */

a = b + 5;

c = (x<3) ? a : b;

} /* fine blocco */else n = b;

ISTRUZIONE if ANNIDATE

• Come caso particolare, <istruzione1> o <istruzione2> potrebbero essere un altro if

• Occorre attenzione ad associare le parti else (che sono opzionali) all’ if corretto

if (n > 0) if (a>b) n = a; else n = b; /* riferito a if(a>b) */

if (n > 0) { if (a>b) n = a; }else n = b; /* riferito a if(n>0) */

Regola semantica:l’else è sempre associato

all’if più interno

Se ciò non soddisfa occor-re inserire esplicitamente

un blocco.

ISTRUZIONE DI SCELTA MULTIPLA

• Consente di scegliere fra molte istruzioni (alternative o meno) in base al valore di una espressione di selezione.

• L’espressione di sele-zione deve denotare un valore numerabile (intero, carattere,…).

espressione di selezione

caso Aistruzioni1

caso Bistruzioni2

defaultistruzioni

…

break

break

break


<scelta-multipla> ::=switch (selettore) {case <etichetta1> : < istruzioni> [ break; ]case <etichetta2> : < istruzioni> [ break; ]

…[ default : < istruzioni> ]}

Il valore dell’espressione selettore viene confron-tato con le etichette dei vari casi: l’esecuzioneprosegue dal ramo corrispondente (se esiste).

Se nessuna etichetta corri-sponde, si prosegue col il

ramo default.

Se neanche quello esiste, si prosegue con l’istruzione

successiva allo switch.


<scelta-multipla> ::=switch (selettore) {case <etichetta1> : < istruzioni> [ break; ]case <etichetta2> : < istruzioni> [ break; ]

…[ default : < istruzioni> ]}

Il valore dell’espressione selettore viene confron-tato con le etichette dei vari casi: l’esecuzioneprosegue dal ramo corrispondente (se esiste).

Le etichette sono costantidello stesso tipo del

selettore.

Attenzione: <istruzioni> denota una sequenza di

istruzioni (non occorre un blocco)


espressione di selezione

caso Aistruzioni1

caso Bistruzioni2

defaultistruzioni

…

break

break

break

I vari rami non sono mutua-mente esclusivi: imboccato un ramo, si eseguono anche

tutti i rami successivi...

… a meno che non ci siail comando break a forzare

esplicitamente l’uscita.

ISTRUZIONI DI ITERAZIONE

<iterazione> ::=

<while> | <for> | <do-while>• Per il Teorema di Jacopini-Böhm, una struttura

di controllo iterativa sarebbe sufficiente: averne di più migliora l’espressività del linguaggio.

• Le istruzioni di iterazione: hanno un solo punto di ingresso e un solo punto di

uscita nel flusso del programma perciò possono essere interpretate come una

singola azione in una computazione sequenziale.

ISTRUZIONE while

<while> ::= while( <condizione> ) <istruzione>

condizione

vera

falsa

istruzione

L’istruzione viene ripetuta pertutto il tempo in cui la condi-

zione rimane vera.

Se la condizione è falsa, l’iterazione non viene eseguita

neppure una volta.

In generale, non è noto quantevolte l’istruzione sarà ripetuta.

ISTRUZIONE while

<while> ::= while( <condizione> ) <istruzione>

condizione

vera

falsa

istruzione

Prima o poi, direttamente oindirettamente, l’istruzione

deve modificare la condizione:altrimenti, l’iterazione durerà

per sempre!

Perciò, quasi sempre istruzioneè un blocco, al cui interno simodifica qualche variabile

che compare nella condizione.

ISTRUZIONE do...while

<do-while> ::=do <istruzione> while( <condizione> );

È una “variazione sul tema” della precedente: la condizione

viene verificata dopo aver eseguito l’istruzione.

Se la condizione è falsa, l’iterazione viene comunque ese-

guita almeno una volta.

condizione

vera

falsa

istruzione

particolarmente adatta alleverifiche dopo un input

ISTRUZIONE for

È una evoluzione dell’istruzione whilerispetto a cui mira a eliminare alcunefrequenti sorgenti di errore:

mancanza delle necessarie inizializza-zioni delle variabili

mancanza della fase di modifica del ciclo(rischio di ciclo senza fine)

ISTRUZIONE for<for> ::=for( <espr-i> ; <cond> ;<espr-m>) <istruzione>

condizione

vera

falsa

istruzione

espr-inizializzazione

espr-modifica

Struttura del while


condizione

vera

falsa

istruzione


espr-modifica

Espressione di inizia-lizzazione: valutata una e una sola volta prima di iniziare l’itera-zione.

Espressione di inizia-lizzazione: valutata una e una sola volta prima di iniziare l’itera-zione.


Condizione:valutata a ogni interazione,per decidere se proseguire(come in un while)

condizione

vera

falsa

istruzione


espr-modifica

Condizione:valutata a ogni interazione,per decidere se proseguire(come in un while)Se manca si assume vera!


Condizione:valutata a ogni interazione,per decidere se proseguire(come in un while)

condizione

vera

falsa

istruzione


espr-modifica

Espressione di modifica:valutata a ogni interazione,dopo aver eseguito l’istru-zione.

UN ESEMPIO

Il solito problema: calcolo del fattoriale

• Dall’approccio ricorsivo…

• ...all’approccio sintatticamente ricorsivo, ma computazionalmente iterativo (ricorsione tail)...

• ...all’approccio iterativo tramite istruzioni di iterazione.

IL FATTORIALE ITERATIVO TRAMITE ESPRESSIONE CONDIZIONALE...

int factIter(int n, int i, int v){

/* inizialmente, v = 1 */

/* invariante di ciclo: v = i! */ return (i==n) ? v :

factIter(n,i+1,(i+1)*v);

}

Chiamata: factIter(n,0,1)

... IL FATTORIALE ITERATIVO TRAMITE ISTRUZIONE CONDIZIONALE...

int factIter(int n, int i, int v){

/* inizialmente, v = 1 */

/* invariante di ciclo: v = i! */if (i==n) return v;

else return factIter(n,i+1,(i+1)*v);

}

Chiamata: factIter(n,0,1)

...IL FATTORIALE ITERATIVO TRAMITE ISTRUZIONE DI ITERAZIONE: while

int fact(int n){int v=1; /* inizialmente, v = 1 */int i=0; /* inizialmente, i = 0 */while (i<n) { /* invariante: v = i! */

v = (i+1)*v;i = i+1;

}return v;

}

I valori iniziali, prima forniti dl-l’esterno, divengono ora varia-bili locali della funzione interfaccia utente più pulita

...IL FATTORIALE ITERATIVO TRAMITE ISTRUZIONE DI ITERAZIONE: do...while

int fact(int n){int v=1; /* inizialmente, v = 1 */int i=0; /* inizialmente, i = 0 */do { /* invariante: v = i! */

v = (i+1)*v;i = i+1;

} while (i<n);return v;

}

La condizione è ora verificatadopo ogni interazione anzichéprima.

Problema: che succede se siinvoca fact(-3) ???

...IL FATTORIALE ITERATIVO TRAMITE ISTRUZIONE DI ITERAZIONE: for

int fact(int n){int v=1; /* inizialmente, v = 1 */int i;for (i=0;i<n; i+1) v = (i+1)*v; /* invariante: v = i! */return v;

} Le fasi di inizializzazione e dimodifica della variabile di con-trollo del ciclo sono ben in evi-denza nella struttura del for.

ITERAZIONE & RICORSIONE TAIL

Poiché la ricorsione tail dà luogo a un processo computazionale di tipo iterativo, deve essere possibile trasformare un ciclo in ricorsione tail e viceversa.

COME FARLO?

il corpo del ciclo rimane immutato il ciclo diventa un if con, in fondo, la chiamata tail-ricorsiva.

ITERAZIONE & RICORSIONE TAIL

• il corpo del ciclo rimane immutato

• il ciclo diventa un if con, in fondo, la chiamata tail-ricorsiva.

Naturalmente, può essere necessario aggiungere nuovi parametri nell’intestazione della funzione tail-ricorsiva, per “portare avanti” le variabili di stato.

while (condizione) {

<corpo del ciclo>

}

if (condizione) {

<corpo del ciclo>

<chiamata ricorsiva>}

ESEMPIO: Massimo Comun Divisore

La soluzione tail-ricorsiva già vista...int mcd(int m, int n){if (m!=n) if (m>n) return mcd(m-n, n);

else return mcd(m, n-m);else return m;

}… opportunamente riscritta...int mcd(int m, int n){if (m!=n) { if (m>n) m=m-n; else n=n-m; return mcd(m,n);} else return m;

}

ESEMPIO: Massimo Comun Divisore

… opportunamente riscritta...int mcd(int m, int n){if (m!=n) { if (m>n) m=m-n; else n=n-m; return mcd(m,n);} else return m;

} … traslata in ciclo:int mcd(int m, int n){while (m!=n) if (m>n) m=m-n; else n=n-m;return m;

}

ESERCIZIO 1

Dati tre valori a b c che rappresentano le lunghezze di tre segmenti, valutare se posso-no essere i tre lati di un triangolo, e se sì deci-derne il tipo (scaleno, isoscele, equilatero).

Vincolo: deve essere c < (a+b)

Rappresentazione delle informazioni:• la variabile booleana triangolo indica se i tre segmenti possono costituire un triangolo• le variabili booleane scaleno, isoscele e equil indicano il tipo di triangolo.

ESERCIZIO 1Specifica:se a+b>c

triangolo = verose a=b=c { equil=isoscele=vero

scaleno=falso }altrimenti se a=b o b=c o a=c { isoscele=vero;

equil=scaleno=falso } altrimenti

{ scaleno=vero; equil=isoscele=falso }

altrimentitriangolo = falso

ESERCIZIO 1

main (){ float a=1.5, b=3.0, c=4.0; int triangolo, scaleno, isoscele, equil; triangolo = (a+b>c); if (triangolo) {

if (a==b && b==c) { equil=isoscele=1; scaleno=0; }else if (a==b || b==c || a==c) { isoscele=1; scaleno=equil=0;}

else { scaleno=1; isoscele=equil=0;}

}}

ESERCIZIO 1

main (){ float a=1.5, b=3.0, c=4.0; int triangolo, scaleno, isoscele, equil; triangolo = (a+b>c); if (triangolo) {

if (a==b && b==c) { equil=isoscele=1; scaleno=0; }else if (a==b || b==c || a==c) { isoscele=1; scaleno=equil=0;}

else { scaleno=1; isoscele=equil=0;}

}}

Attenzione! Una espressionecome a==b==c sarebbe stataformalmente lecita, ma avreb-be avuto tutt’altro significato!

Non si può usare l’istruzione di scelta multipla (switch) perchéle condizioni da verificare sonouguaglianze fra variabili, nonsemplici confronti con etichettepredefinite.

ESERCIZIO 2

Dati due valori positivi X e Y, calcolarne ladivisione intera X/Y come sequenza disottrazioni, ottenendo quoziente e resto.

Invariante di ciclo:

X = Q * Y + R, con R 0

• inizialmente, Q=0, R=X (R>Y)• a ogni passo, Q’=Q+1, R’=R-Y (R>Y)• alla fine, X = Q(n) * Y + R (n) (0<R<Y)

che è la definizione di divisione intera.

ESERCIZIO 2Specifica:

sia Q il quoziente, inizialmente pari a 0sia R il resto, inizialmente pari a Xwhile (R Y)

incrementare il quoziente Qdecrementare R di una quantità Y

Codifica

main(){ int x = 20, y = 3, q, r; for (q=0, r=x; r>=y; q++, r=r-y);}

Notare l’uso di una espressioneconcatenata per concatenare dueassegnamenti e inizializzare cosìdue variabili.

Idem per le operazionidi modifica

OPERATORI DI ASSEGNAMENTO “COMPATTI”

Il C introduce una forma particolare di assegnamento che ingloba anche un’operazione aritmetica o bit a bit:

l-espr = <espressione>

è “quasi equivalente” a

l-espr = l-espr <espressione>

dove indica un operatore fra+, –, *, /, %, >>, <<, &, ^, |


Perché “quasi” equivalente ? nel primo caso, l-espr viene valutata

una sola volta

nel secondo, invece, viene valutata due volte

Quindi, le due forme sono equivalenti solo se la valutazione di l-espr non comporta effetti collaterali


Esempik += j equivale a k = k + j

k *= a + b equivale a k = k*(a+b)*/

v[i++] *= n non equivale av[i++] = v[i++]*n */

ESERCIZIO 3

Dati tre valori a, b, c, rappresentanti i coeffi-cienti di un’equazione di secondo grado a x2 + b x + c = 0, calcolarne le radici (reali).

Specifica:Calcolare il valore delta = b2 - 4acSe delta0

calcolare d = deltacalcolare le due radici x1, x2 = - (b d) / 2a

altrimenti (radici complesse: halt)

ESERCIZIO 3

#include <math.h>main (){ float a=1.0, b=2.0, c=-15.0; float delta, d, x1, x2;

delta = b*b-4*a*c; if (delta>=0){

d = sqrt(delta);x1 = -(b+d)/(2*a);x2 = -(b-d)/(2*a);

}}

Direttiva al preprocessore: include la libreria matematica(fornisce la funzione sqrt)

ESERCIZIO 4

Scrivere una funzione che verifichi se un naturale N è primo.

Specifica di I° livello (Crivello di Eratostene):

Occorre provare a dividere N per tutti i numeri K N: se nessuno risulta essere un divisore, allora N è primo

Specifica di II° livello:

Se N è 1, 2 o 3, allora è primo senz’altro. Altrimenti, se è un numero pari, non è primo.Se invece N è dispari e >3, occorre tentare tutti i possibili divisori da 3 in avanti, fino a N.

ESERCIZIO 4

#include <math.h>int isPrime(int n) {int max,i;if (n>=1 && n<=3) return true; /* 1,2,3 ok */if (n%2==0) return false; /* numeri pari no */max = sqrt(n);for(i=3; i<=max; i+=2)

if (n%i==0) return false;return true;

}

ESERCIZIO 5

Scrivere una funzione radice che calcoli la radice quadrata (intera) di un naturale N.

Specifica di I° livello:

int radice(int n);

restituisce il massimo intero X tale che X*X N Specifica di II° livello:

Considera un naturale X dopo l’altro a partire da 1, e calcolane il quadrato X*X: fermati appena tale quadrato supera N.Il precedente numero considerato (X-1) è il risultato.

ESERCIZIO 5

int radice(int n) {int x;for(x=0; x*x <= n; x++);return x-1;

}Il corpo del ciclo è vuoto: ineffetti, l’elaborazione consistesolo nell’incrementare x perun opportuno numero di volte.

ESERCIZIO 6

Scrivere una funzione che, dato un carattere C, restituisca il corrispondente maiuscolo.

Specifica di I° livello:

char maiuscolo(char c);restituisce il maiuscolo di C

Specifica di II° livello:

Se C non è una lettera minuscola, restituiscilo tale e quale. Altrimenti, per calcolare il corrispondente maiu-scolo, sfrutta l’ ordinamento della codifica dei caratteri:– ogni carattere è associato a un intero– le lettere da ‘A’ a ‘Z’ sono in sequenza– le lettere da ‘a’ a ‘z’ sono in sequenza

ESERCIZIO 6

char maiuscolo(char c) {if (c<'a' || c>'z') return c;else return c – 'a' + 'A';

}

Aritmetica fra caratteri: possibileperché le operazioni vengonosvolte sul corrispondente codice(ASCII o UNICODE)

Attenzione! Una espressione come 'a’<c<'z' è lecita, ma ha tutt’altro significato!

RICORSIONE & ITERAZIONE Riconsideriamo lesempio del Massimo Comun Divisore visto tempo addietro: m,...

Documents

Transcript of RICORSIONE & ITERAZIONE Riconsideriamo lesempio del Massimo Comun Divisore visto tempo addietro: m,...