Il metodo dei raffinamenti successivi top-down) è una ... · for var from espr1 to espr2 by espr3:...

Metodo dei raffinamenti successivi

Il metodo dei raffinamenti successivi (top-down) è una metodologia di programmazione basata sui seguenti principi:Divide-et-impera: il problema da risolvere è scomposto in

(sotto)problemi “più piccoli” che possono essere gestiti più facilmenteOgni sottoproblema verrà successivamente risolto con una codifica

diretta, oppure a esso si riapplicherà lo stessa tecnica (raffinamento)

Astrazione: il problema viene inizialmente affrontato nel suo complesso, studiandone i particolari in un secondo momento

È organizzato nelle seguenti fasi1. Analisi del problema2. Individuare un algoritmo3. Verifica e raffinamento (dell’algoritmo)4. Implementazione


1. Analisi del problema: capire bene il problema per convincersi che esiste una soluzioneinput : di quale informazione si disponeoutput: che cosa esattamente si vuole ottenere

spesso ci si convince di aver trovato una soluzione al problema ma questa risolve un problema più semplice di quello dato

Output?Input?

soluzione(algoritmo)


2. Individuare un algoritmo (G), ossia una successione finita di azioni che risolvono il problemaazione: una serie di operazioni che

quando effettuate producono un risultato previsto e ben determinato (determinismo)

si compiono in un certo intervallo di tempo (discretismo: finitezza dell’azione). Ogni azione modifica lo stato di uno o più oggetti

ci rendiamo conto che l’azione ha prodotto un risultato proprio dal cambiamento di stato dell’oggetto stesso.

istruzioni di programma (PG): comandi (in un linguaggio formale) interpretati dall’esecutore associando in modo univoco azioni


3. Verifica e raffinamento: verificare che la successione di azioni risolve veramente il problema …

… se la risposta è affermativa allora abbiamo un algoritmo che risolve il problema … per ogni azione dell’algoritmo:• se corrisponde ad una istruzione del linguaggio utilizzato (C), o

può essere facilmente tradotta in una breve successione di istruzioni in C vai al punto 4.

• altrimenti si assuma l’azione come un sottoproblema di quello originario e riapplicare per esso i punti 2. e 3.

… altrimenti tornare al punto 1.


4. Implementazione: traduci le azioni in istruzioni del programma• Il risultato di questo processo è la scrittura del programma

sorgente• Il programma sorgente è una tra le tante possibili implementazioni

(software) dell’algoritmo• Anche l’algoritmo è una delle possibili soluzioni ad un problema

dato

if condthen ...else ...

azione1

azione2

printf(...)

problemaG1

G2

P1G1P2

G1

......


Il metodo dei raffinamenti successivi può essere così schematizzato:

1. Attenta lettura iniziale del problema per convincersi che ammette soluzione.

2. Se esiste almeno una soluzione, descrivere in modo sommario le azioni da eseguire per poter determinare tale soluzione.

3. Se la successione di azioni porta alla soluzione allora possiamo raffinare ogni azione in altre azioni più dettagliate.

4. Il passo 3 termina quando il dettaglio è tale che ogni azione corrisponde ad una istruzione del linguaggio utilizzato (C nel nostro caso), o può essere facilmente tradotta in una breve successione di istruzioni in C.


Lo pseudocodice è un linguaggio artificiale e parzialmente formalizzato per esprimere le (macro)azioni di un algoritmo

istruzione Tipo Descrizione

var ß espr assegnazione Assegna il valore della espressione espr alla variabile var

if espr:<blocco1-istruzioni>

else:<blocco2-istruzioni>

selezione Esegue il <blocco1-istruzioni> se espr ha valore ‘vero’, altrimenti esegue <blocco2-istruzioni>

for var from espr1 to espr2by espr3:

<blocco-istruzioni>

iteratore Ripete il <blocco-istruzioni> per ogni valore di var che va da espr1a espr2 con passo espr3

while espr:<blocco-istruzioni>

iteratore Ripete il <blocco-istruzioni> finché il valore di espr è ‘vero’

do:<blocco-istruzioni>

while espr:

iteratore Ripete il <blocco-istruzioni> finché il valore di espr è ‘vero’ (esegue almeno una volta)


Lo pseudocodice è un linguaggio artificiale e parzialmente formalizzato per esprimere le (macro)azioni di un algoritmo

istruzione Tipo Descrizione

leggi(v1, ..., vn) input Legge n dati di input da tastiera e li assegna alle variabili v1, ..., vn

stampa(a1, ..., an) output Stampa n dati di output a schermo: a1, ..., an possono essere variabili o espressioni

foo(a1, ..., an) funzione Esegue una funzione sui parametri di input a1, ..., an e restituisce un valore (usato come espr negli altri costrutti)

function (v1, ..., vn):<blocco-istruzioni>

return espr:

definizione Definisce una funzione con argomenti v1, ..., vn e con valore di ritorno dato da espr


Problema:Dati un capitale iniziale C ed un tasso di interesse annuo T calcolare e

stampare l’interesse maturato (I) ed il capitale risultante (CR) dopo un anno, dopo due anni e dopo tre anni.

La stampa deve essere del tipo:Anno Capitale Tasso % Interesse Totale1 1.000 10 100 1.1002 1.100 10 110 1.2103 1.210 10 121 1.331

1. Analisi del problema: • I = C * T/100• CR = C + I = C * T = C (1 + T/100)• Dopo un anno il capitale iniziale C diventa il capitale risultante dell’anno

precedente (CR)


2. Individuare un algoritmo:Come partenza si individui una serie di macro azioni che risolvono il

problema

leggi(C,T)stampa(“Anno”,”Capitale”, ...)calcola_e_stampa_interesse_e_capitale_anno_1()calcola_e_stampa_interesse_e_capitale_anno_2()calcola_e_stampa_interesse_e_capitale_anno_3()

Algoritmo


3. Verifica e raffinamento:L’algoritmo risolve il problema posto se si conoscono le formule per il

calcolo dell’interesse maturato (I) e del capitale risultante (CR)

leggi(C,T)stampa(“Anno”,”Capitale”, ...)

calcola_e_stampa_interesse_e_capitale_anno_1()calcola_e_stampa_interesse_e_capitale_anno_2()calcola_e_stampa_interesse_e_capitale_anno_3()

Algoritmo

leggi(C,T)stampa(“Anno”,”Capitale”

, ...)I ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“1”,C,T,I,CR)C ß CRI ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“2”,C,T,I,CR)C ß CRI ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“3”,C,T,I,CR)

1o anno

2o anno

3o anno




leggi(C,T)stampa(“Anno”,”Capitale”, ...)for t from 1 to 3:

Algoritmo

I ßcalcola_interesse(C,T)

CR ß calcola_totale(C,I)stampa(t,C,T,I,CR)C ß CR

leggi(C,T)stampa(“Anno”,”Capitale”,...)I ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“1”,C,T,I,CR)C ß CRI ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“2”,C,T,I,CR)C ß CRI ß calcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(“3”,C,T,I,CR)





I ß C ´ (T / 100)CR ß C + Istampa(t,C,T,I,CR)C ß CR

Algoritmo


Algoritmo

I ßcalcola_interesse(C,T)CR ß calcola_totale(C,I)stampa(t,C,T,I,CR)C ß CR


4. implementazione:Ogni azione dell’algoritmo è

traducibile in istruzioni del linguaggio C

int main () {float Totale, Capitale, Tasso, Interesse;printf("Inserisci il Capita = ”); scanf(“%f”,&Capitale);printf("Tasso d'interesse(%) = "; scanf(“%f”,& Tasso);printf("Anno Capitale Tasso % Interesse Totale\n”);int i;for(i=1;i<=3; i++) {

Interesse=Capitale*Tasso/100;Totale=Capitale +Interesse;printf("%3d %10.2f %6.2f %10.2f %12.2f\n", i,

Capitale,Tasso,Interesse,Totale);Capitale=Totale;

}return 0;

}


I ß C ´ (T / 100)CR ß C + Istampa(t,C,T,I,CR)C ß CR

Algoritmo


Problema: Calcolare la somma di due frazioni n1/d1, n2/d2 e ridurla ai minimi termini.

Primo raffinamento:leggi(n1,d1,n2,d2)calcola il numeratore, num, ed il denominatore, den, della sommariduci num e den ai minimi terministampa(num e den)

I quattro numeri in input non possono essere quattro interi qualsiasi perché un denominatore non può mai essere zero.

Quindi precondizioni: d1≠0 e d2≠0 Per ridurre num e den ai minimi termini dobbiamo prima trovare il massimo

comun divisore k, e successivamente effettuare le operazioni num¬num/k, den¬den/k.

Calcolare la somma di due frazioni n1/d1, n2/d2 e ridurla ai minimi termini.

Secondo raffinamento:leggi(n1,d1,n2,d2) (precondizione: d1≠0 e d2≠0)

den¬d1*d2num¬n1*d2+n2*d1

Calcola k, massimo comun divisore di num e dennum¬num/kden¬den/k

Terzo raffinamento:

leggi(n1,d1,n2,d2) (precondizione: d1>0,d2>0)den¬d1*d2num¬n1*d2+n2*d1n=numd=denwhile d!=0

temp=n%dn¬dd¬temp

k=n num¬num/kden¬den/k

Esercizi

Esercizi1. Scrivere un programma che, dato in input un intero positivo, calcola

separatamente le cifre del numero e le stampa separate da uno spazio– Esempio: 4523 à “4 5 2 3”– Suggerimento: si usi la divisione intera (\) e l’operatore resto (%)

2. Sulla base del programma precedente scrivere un programma che dato in input un intero positivo, dia come risultato il numero con le cifre in ordine inverso:– Esempio: 4523 à 3254

3. Due numeri interi a e b si dicono coprimi se MCD(a,b) = 1. Scrivere un programma che dati in input due numeri interi stampi a video ‘vero’ se sono coprimi, ‘falso’ altrimenti

4. Un numero si dice primo se è divisibile solo per 1 e per sé stesso.Scrivere un programma che, dato in input un numero intero positivo stampi a video ‘vero’ se è primo, ‘falso’ altrimenti

Esercizi

Esercizi:1. Un commerciante, per vendere di più un suo prodotto, il cui prezzo

è di 15,75 €, propone uno sconto del 12% per i clienti che ne acquistano più di 500 unità. Scrivere un programma che calcoli il ricavo effettivo per un acquisto di x unità.

2. Quali sono i cambiamenti da apportare al programma dell’esercizio precedente nel caso in cui il commerciante applichi uno sconto ulteriore del 10% quando un cliente acquisti almeno 1000 unità?

3. Scrivere un programma che chieda in input esattamente N numeri interi relativi compresi tra 100 e -100 e li stampi. Utilizzando tale programma scrivere un altro programma che stampila quantità di numeri positivi e negativi generati;il massimo ed il minimo dei valori generati;la differenza massima in valore assoluto tra ogni termine e il

precedente (non il primo)la differenza minima in valore assoluto tra ogni termine e il

precedente (non il primo)

Esercizi

Esercizi:4. Scrivere un programma che assegnato un numero intero positivo

stampi la somma dei suoi divisori ( escluso se stesso )5. Scrivere un programma che assegnato un numero intero positivo

stampi ‘vero’ se il numero è perfetto, ‘falso’ altrimentiun numero è perfetto se e solo la somma dei suoi divisori, escluso

se stesso, è uguale al numero stesso: 6=1+2+3 è perfetto 8=1+2+4 non lo è.

6. Per produrre una vernice sono necessari 10 grammi di un certo additivo per ogni chilo di prodotto fino a 10 chili e 5 grammi al chilo per i chili eccedenti. Scrivere un programma che fornisca la quantità di additivo necessaria in base al quantitativo di vernice richiesto

Astrazione procedurale

L’astrazione procedurale consiste nel descrivere tutti i sottoproblemi in cui un problema è descrivibile sostituendo poi a queste descrizioni una chiamata ad un sottoprogramma, non ancora scritto, il cui compito sarà quello di risolvere il corrispondente sottoproblema.

Il sottoprogramma dovrà ricevere tutta l’informazione (i dati) necessari per poter risolvere il problema.

• E’ necessario precisare quale è lo stato del sistema all’atto della chiamata del sottoprogramma (le precondizioni)

• quale sarà lo stato del sistema dopo l’esecuzione del sottoprogramma (le postcondizioni).

A questo punto si scrive lo pseudo codice per ognuno dei sottoprogrammi.

Naturalmente può accadere che qualcuno dei sottoprogrammi sia ancora così complesso da richiedere a sua volta la sua scomposizione in ulteriori sottoprogrammi.


Astrazione procedurale è una tecnica di sviluppo dei programmi in forma di procedure che realizza il metodo dei raffinamenti successivi• La scomposizione del problema in sottoproblemi più semplici si

traduce in una strutturazione del programma in un flusso di esecuzione di procedure• La procedura principale implementa una soluzione generale del problema

che nasconde i dettagli delle singole soluzioni parziali• Ogni procedura è un sottoprogramma che risolve un problema più

semplice (eventualmente usando la stessa tecnica di raffinamento)

T1in

T3

T2

T4 out

T0 (problema)


1. Decomposizione problema:• Il problema viene scomposto in un insieme di sottoproblemi (task)

• Si identifica un algoritmo per il problema principale• Ogni task utilizza dei dati (input) e genera nuovi o modifica dati

esistenti (output)

T1in

T3

T2

T4 out

T0 (problema)

G0

G4

G3

T0

T4T3

T2 G2

G1T1


2. Identificare dipendenze, cioè l’ordine di risoluzione dei task• Individuare per ogni task i dati

di input e da quali task sono elaborati• Definire i dati di output (prodotti o modificati)

dal task che saranno usati da altri task• L’ordine di risoluzione non è

necessariamente unico

T1in

T3

T2

T4 out

T0 (problema)

T1

T2

T3

T4

T2,T3

T4,out

T4

outT2,T3

T1

T1

in

ord

ine

di

riso

luzi

one


3. Individuare precondizioni (postcondizioni)• che i dati di input (output) devono soddisfare affinché ogni task

operi correttamente su di essi (e generi dati utilizzabili da altri task) • tipo dei dati e intervallo di valori• invarianza di dati passati in input al task e

emessi in output


4. Implementazione algoritmo• Traduzione degli algoritmi individuati in sequenze di istruzioni

(programma e sottoprogrammi) in pseudocodice o nel linguaggio di programmazione (C)• Definire per ogni task un nome (del sottoprogramma corrispondente)• Scrittura del programma (principale) sostituendo l’esecuzione di ogni

task con una chiamata al nome del sottoprogramma corrispondente• Scrittura a parte dei sottoprogrammi corrispondenti ad ogni task

• Può accadere che qualcuno dei sottoprogrammi sia ancora così complesso da richiedere a sua volta la sua scomposizione in ulteriori sottoprogrammi

• ritorna al punto 1

G0

G4

G3

T0

T4T3

T2 G2

G1T1

leggi(in)a ß task1(in)b ß task2(a)c ß task3(a)d ß task4(b,c)stampa(b,d)

Task0Task1Task2Task3

function task4(p1, p2):<blocco-istruzioni>

return ... :

Task4

C funzioni à chiamata

Esistono due tipi di sottoprogrammi: le procedure e le funzioniLe funzioni restituiscono sempre un solo valoreLe procedure non restituiscono valori

In C esistono solo funzioniuna procedura è una funzione che ritorna il valore void

Una chiamata di funzione ha la seguente sintassi:

nome(parametri);

• è a tutti gli effetti una istruzione del programma• Il valore dell’istruzione è il valore ritornato dalla funzione• parametri è la lista dei parametri (eventualmente nulla) cioè dei

dati passati dal programma chiamante alla funzione

Esempio: k = mcd(a,b); calcola il massimo comun divisore di due numeri interi

C funzioni à chiamata

La chiamata di una funzione non di tipo void può essere inserita come:

• operando in qualsiasi espressione• parametro nella chiamata di un'altra funzione

• il compilatore controlla che il tipo della funzione sia ammissibile

• la chiamata viene eseguita con precedenza rispetto alle altre operazioni e al suo posto viene sostituito il valore di ritorno restituito dalla funzione

Se la funzione è di tipo void (procedura), la chiamata non può essere inserita in una espressione, ma deve assumere la forma di un'istruzione a se stante

Esempio: k = (mcd(a,b) * n) / 2;

foo(mcd(a,b), d);

C funzioni à definizione

La definizione di funzione ha la seguente sintassi: tipo nome(argomenti) {

istruzione1; ...

}

Dove:• tipo è il tipo del valore di ritorno della funzione, detto anche tipo della

funzione;• se la funzione non ha valore di ritorno (procedura), bisogna specificare void

• nome: è l'identificatore della funzione• segue le regole generali di specifica degli identificatori

• argomenti è la lista di argomenti (dati) passati dal programma chiamante • vanno specificati insieme al loro tipo (come nelle dichiarazioni delle

variabili) e, se più d'uno, separati da virgole;• se non vi sono argomenti, si può specificare void (o, più

comodamente, non scrivere nulla fra le parentesi).

C funzioni à definizione

La definizione di funzione ha la seguente sintassi: tipo nome(argomenti) {

istruzione1; ...

}

Esempio: char MiaFunz(int dato, float valore)

la funzione di nome MiaFunz riceve dal programma chiamante gli argomenti:

dato (di tipo int), e valore (di tipo float),

e ritorna un risultato di tipo char.

C funzioni à return

Nel codice di implementazione di una funzione l'istruzione di ritorno al programma chiamante é:

return espressione;

• il valore calcolato dell'espressione viene restituito al programma chiamante come valore di ritorno della funzione

• se il tipo non è quello dichiarato della funzione, il compilatore segnala un errore, oppure, quando può, esegue una conversione implicita (con warning se c'é pericolo di loss of data)

• Non é necessario che tale istruzione sia l'ultima (ma è bene farlo)• Non é necessario che ve ne sia una sola

• dipende dalla presenza delle istruzioni di controllo, che possono interrompere l'esecuzione della funzione in punti diversi

• Se la funzione non ha valore di ritorno (procedura), bisogna specificare return; (da solo).

• può essere omessa quando il punto di ritorno coincide con la fine della funzione

C funzioni à esempio

Definiamo una funzione per l’algoritmo (di Euclide) che calcola il MCD di due interi a e b:

Si tratta di una vera funzione perché gli argomenti sono usati solo per il calcolo del MCD

function mcd(a,b):r ß modulo(a,b)while (r > 0):

a ß bb ß rr ß modulo(a,b)

return b:

pseudocodice

int mcd (int a, int b) {

int r;r = a % b;while (r>0) {

a = b;b = r;r = a % b;

}return b;

}

codice C

C funzioni à argomenti

int main () {int a,b,m;printf("Calcolo del M C D\n”);printf("Assegnare a e b :”); scanf(“%d”,&a);scanf(“%d”,&b);printf("MCD di %d e %d = ”, a, b);m = mcd(a,b);printf(“%d \n”, m);return 0;

}

Il metodo dei raffinamenti successivi top-down) è una ... · for var from espr1 to espr2 by espr3:...

Documents

Transcript of Il metodo dei raffinamenti successivi top-down) è una ... · for var from espr1 to espr2 by espr3:...