AN FI 98-99 Metodologie1 Metodologie di progetto Metodologie top-down e bottom-up.

AN FI 98-99 Metodologie1

Metodologie di progetto

Metodologie top-down e bottom-up


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


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


Problema H(n)

Determinare il valore

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


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


H(n): codifica

double H( int n ){

return

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

}


Problema: bk

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

bk

con b reale, k intero, k>= 0


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


bk : codifica

double power(double b,int k){

return

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

}


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


Polinomio: progetto

Riscrittura della relazione:

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

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


Polinomio: codifica

double pol( double x, int n ){

return

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

}


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



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



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


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);}


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


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; }


Contaminuscole

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

int ContaMinuscole ()


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


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


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


contaChar

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

// chEnd: carattere finale

return(chIn == chEnd) ? 1 :

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

}


La funzione succ sui caratteri

char Succ(char ch){

int succRep = ord(ch)+1;

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

}


Le funzioni ord e chr

int ord(char ch){

return (int)ch; }

char chr(int rapCh){

return

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

(char)rapCh:‘\0’; }


Scorciatoie

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


return( chIn==chEnd ) ? 1 :

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

}


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:


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)


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


return(ch==chEnd)? nc :

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

}


ContaMinuscole

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

}


Una strada molto breve

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

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


Numero cifre

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


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


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 ) );

}

AN FI 98-99 Metodologie1 Metodologie di progetto Metodologie top-down e bottom-up.

Documents

Transcript of AN FI 98-99 Metodologie1 Metodologie di progetto Metodologie top-down e bottom-up.