AN FI 98-99 Metodologie1

Metodologie di progetto

Metodologie top-down e bottom-up

AN FI 98-99 Metodologie1

Metodologia top-down

Si parte dal problema e dalle proprieta’ note sul dominio dei dati

Si disgrega il problema in sottoproblemi Si affronta ciascun sottoproblema (con la

stessa metodologia) fino a raggiungere problemi risolubili con le mosse elementari

AN FI 98-99 Metodologie1

Impostazione ricorsiva

Si esprime la soluzione di un caso particolare

Si tenta di disgregare il problema in modo da ricondurre la soluzione del caso generale al caso particolare

AN FI 98-99 Metodologie1

Problema H(n)

Determinare il valore

H(n) = 1 + 1/2 +1/3 + ... + 1/n

AN FI 98-99 Metodologie1

H(n): progetto

H(n): nat -> double

IPOTESI: n >0Riscrittura della relazione:

H(n) = (1 + 1/2 + … + 1/(n-1)) + 1/n

H(n) vale 1 per n = 1

H(n) vale 1/n + H(n-1) per n >1

AN FI 98-99 Metodologie1

H(n): codifica

double H( int n ){

return

(n==1) ? 1: 1.0/n + H(n-1);

}

AN FI 98-99 Metodologie1

Problema: bk

Scrivere una funzione che restituisce il valore dell’espressione che segue:

bk

con b reale, k intero, k>= 0

AN FI 98-99 Metodologie1

bk : progetto

power(b,k) double x nat -> double

IPOTESI: k >= 0Riscrittura della relazione:

b0 = 1

bk = b * bk-1 per k > 0

power(b,k) -> 1 per k = 0

power(b,k) -> b*power(b,k-1) per k > 0

AN FI 98-99 Metodologie1

bk : codifica

double power(double b,int k){

return

(k==0)? 1 : b*power(b,k-1);

}

AN FI 98-99 Metodologie1

Valore di un polinomio a coeff 1

Scrivere una funzione che restituisce il valore dell’espressione che segue:

xn + xn-1 + ... + x + x0

con x reale, n intero, n>= 0

AN FI 98-99 Metodologie1

Polinomio: progetto

Riscrittura della relazione:

polin(x,n)= xn + xn-1 + ... + x + x0 =

xn + (xn-1 + ... + x + x0) =xn + polin(x,n-1)

AN FI 98-99 Metodologie1

Polinomio: codifica

double pol( double x, int n ){

return

(n==0)?1:power(x,n)+pol(x,n-1);

}

AN FI 98-99 Metodologie1

Polinomio: un altro ragionamento

polin(x,n)= xn + xn-1 + ... + x + x0 =( ... ( (x + 1 ) *x + 1 ) * x + ... +1)* x + 1

v

v = 1v = v*x + 1 n volte

AN FI 98-99 Metodologie1

Polinomio: un altro ragionamento

x4 + x3 + x2 + x1 + x0=(( ( x + 1 ) *x + 1 ) * x +1) *x

+1v = 1

v = v*x + 1

v = v*x + 1

v = v*x + 1

v = v*x + 1

0

1

2

3

4

AN FI 98-99 Metodologie1

Polinomio: un altro ragionamento

so che al passo k=0, il valore corrente del polinomio vale 1

sapendo che, al passo k, il valore corrente del polinomio vale v, al passo k+1 il valore corrente del polinomio vale v*x+1

AN FI 98-99 Metodologie1

Polinomio

double pol( double x, int n ){return polin(x,n,1,0);

}

double polin (double x,int n,double v,int k){return(k==n)?v:polin(x,n,v*x+1,k+1);}

AN FI 98-99 Metodologie1

Fattoriale

N! = 1*1*2*3*…*N

so che al passo k=0, n! vale 1 sapendo che, al passo k, n! vale v, al passo

k+1 n! vale v*k

AN FI 98-99 Metodologie1

Fattoriale

int fact( int n ){//so che al passo 0 n! vale 1

return factIter(n,1,0); }

int factIter (int n,int v,int k){//so che al passo k n! vale v//dunque al passo k+1 n! vale v*k

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

AN FI 98-99 Metodologie1

Contaminuscole

Definire una funzione ContaMinuscole che restituisca il numero di lettere minuscole del tipo prededfinito char

int ContaMinuscole ()

AN FI 98-99 Metodologie1

Contaminuscole: progetto

Partendo dal carattere ‘a’ e procedendo con il carattere successivo, si incrementa un contatore, fino a raggiungere il carattere ‘z’

IPOTESI:– la funzione Succ(char c) restituisce il

carattere ASCII successivo al carattere c

AN FI 98-99 Metodologie1

Contaminuscole: riprogetto

detto chIn il carattere di partenza e chEnd il carattere finale,– se chIn e’ uguale a chEnd il il numero dei

caratteri e’ uguale al 1;– se chIn precede chEnd il numero dei

caratteri e’ uguale al 1 piu’ il numero dei caratteri da Succ(chIn) a chEnd

AN FI 98-99 Metodologie1

Contaminuscole: codifica

int ContaMinuscole () {return contaChar(‘a’,’z’);

}

La soluzione introduce un componente software (la funzione contaChar) che risolve un problema piu’ generale di quello dato

AN FI 98-99 Metodologie1

contaChar

int contaChar(char chIn, char chEnd){// chIn: carattere iniziale

// chEnd: carattere finale

return(chIn == chEnd) ? 1 :

1+contaChar(Succ(chIn),chEnd);

}

AN FI 98-99 Metodologie1

La funzione succ sui caratteri

char Succ(char ch){

int succRep = ord(ch)+1;

return (succRep<=255)?((char)succRep):‘\0’;

}

AN FI 98-99 Metodologie1

Le funzioni ord e chr

int ord(char ch){

return (int)ch; }

char chr(int rapCh){

return

((rapCh>=0)&&(rapCh<=255))?

(char)rapCh:‘\0’; }

AN FI 98-99 Metodologie1

Scorciatoie

int contaChar(char chIn, char chEnd){// chIn: carattere iniziale

// chEnd: carattere finale

return( chIn==chEnd ) ? 1 :

1+contaChar((int)chIn+1,chEnd);

}

AN FI 98-99 Metodologie1

Un altro ragionamento contaChar puo’ ricevere come informazione di

ingresso:– un carattere generico ch compreso tra chIn e chEnd ;– il valore nc del numero di caratteri che va dal carattere

di inizio a ch

contaChar(contaChar(charchar ch, ch,int int ncnc,char,char chEnd) chEnd) In tal caso:

AN FI 98-99 Metodologie1

Un ragionamento iterativo

Se ch coincide con chEnd, allora il numero dei caratteri compresi tra chIn e chEnd vale nc

Se ch precede chEnd, allora il numero dei caratteri compresi tra chIn e chEnd puo’ essere denotato dall’espressione:

contaChar(Succ(ch),nc+1,chEnd)

AN FI 98-99 Metodologie1

contaCharTl

intint contaCharTl( contaCharTl(charchar ch, ch, int int ncnc, char, char chEnd){ chEnd){// ch: carattere corrente

// nc: numero dei caratteri dall’inizio a ch

// chEnd: carattere finale

return(ch==chEnd)? nc :

contaCharTl(Succ(ch),nc+1,chEnd);

}

AN FI 98-99 Metodologie1

ContaMinuscole

int ContaMinuscole () {return contaCharTlcontaCharTl(‘a’,1,’z’);

}

AN FI 98-99 Metodologie1

Una strada molto breve

Avendo realizzato una funzione di trasformazione da caratteri a interi, la soluzione del problema e’:

ord(‘z’)-ord(‘a’)+1;

AN FI 98-99 Metodologie1

Numero cifre

Determinare il numero di cifre decimali che compaiono in una stringa data

AN FI 98-99 Metodologie1

Numero cifre: progetto

int numCifre( String s )

sapendo che nella sottostringa da 0 a k di s vi sono n digit, nella sottostringa da 0 a k+1:– vi sono n+1 digit se il carattere di posizione k+1

e’ un digit– vi sono n digit se il carattere di posizione k+1 non

e’ un digit

AN FI 98-99 Metodologie1

Numero cifre: codifica

int numCifre( String s ){

return numCifre1( s,0,0 ); }

int numCifre1(String s,int n,int k){

return (k==s.length()) ? n :

((isDigit(s.charAt(k))) ? numCifre1( s,n+1,k+1 ):

numCifre1( s,n,k+1 ) );

}