Metodo dei raffinamenti successivi

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ù facilmente

Ogni 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 fasi

1. Analisi del problema

2. Individuare un algoritmo

3. Verifica e raffinamento (dell’algoritmo) 4. Implementazione

Metodo dei raffinamenti successivi

1. Analisi del problema: capire bene il problema per convincersi che esiste una soluzione

input : di quale informazione si dispone

output: 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)

Metodo dei raffinamenti successivi

2. Individuare un algoritmo (G), ossia una successione finita di azioni che risolvono il problema

azione: 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 (P_G): comandi (in un linguaggio formale) interpretati dall’esecutore associando in modo univoco azioni

Metodo dei raffinamenti successivi

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.

Metodo dei raffinamenti successivi

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 cond then ...

else ...

azione1 azione2

printf(...)

problema G

G

P

P

...

...

Metodo dei raffinamenti successivi

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.

Metodo dei raffinamenti successivi

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 espr2 by espr3:

<blocco-istruzioni>

iteratore Ripete il <blocco-istruzioni> per ogni valore di var che va da espr1 a 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)

Metodo dei raffinamenti successivi

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

istruzione Tipo Descrizione

leggi(v₁, ..., v_n) input Legge n dati di input da tastiera e li assegna alle variabili v₁, ..., v_n

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 (v₁, ..., v_n):

<blocco-istruzioni>

return espr:

definizione Definisce una funzione con argomenti v₁, ..., v_n e con valore di ritorno dato da espr

Metodo dei raffinamenti successivi

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 Totale 1 1.000 10 100 1.100 2 1.100 10 110 1.210

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

Metodo dei raffinamenti successivi

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

Metodo dei raffinamenti successivi

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 ß CR

I ß calcola_interesse(C,T) CR ß calcola_totale(C,I) stampa(“2”,C,T,I,CR

)

C ß CR

I ß calcola_interesse(C,T) CR ß calcola_totale(C,I) stampa(“3”,C,T,I,CR)

1

anno

2

anno

3

anno

Metodo dei raffinamenti successivi

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”, ...) 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 ß CR

I ß calcola_interesse(C,T) CR ß calcola_totale(C,I) stampa(“2”,C,T,I,CR) C ß CR

I ß calcola_interesse(C,T) CR ß calcola_totale(C,I) stampa(“3”,C,T,I,CR)

Metodo dei raffinamenti successivi

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”, ...) for t from 1 to 3:

I ß C ´ (T / 100) CR ß C + I

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

Algoritmo

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

Metodo dei raffinamenti successivi

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;

}

leggi(C,T)

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

I ß C ´ (T / 100) CR ß C + I

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

Algoritmo

Metodo dei raffinamenti successivi

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 somma riduci num e den ai minimi termini

stampa(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*d2

num¬n1*d2+n2*d1

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

den¬den/k

Terzo raffinamento:

leggi(n1,d1,n2,d2) (precondizione: d1>0,d2>0) den¬d1*d2

num¬n1*d2+n2*d1 n=num

d=den

while d!=0 temp=n%d n¬d

d¬temp k=n

num¬num/k den¬den/k

Esercizi

Esercizi

1. 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 stampi

la 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’ altrimenti

un 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

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)

T1

in

T3

T2

T4 out T0 (problema)

Astrazione procedurale

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)

T1

in

T3

T2

T4 out

T0 (problema)

G₀

G₄ G₃ T0

T4

T3

T2 G₂

G₁ T1

Astrazione procedurale

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

T1

in

T3

T2

T4 out

T0 (problema)

T1

T2

T3

T4

T2,T3 T4,out

T4 out T2,T3

T1 T1 in

ordine di risoluzione

Astrazione procedurale

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

Astrazione procedurale

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

G₀

G₄ G₃ T0

T4

T3

T2 G₂

G₁ T1

leggi(in)

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

Task0

Task1 Task2 Task3

function task4(p1, p2):

<blocco-istruzioni>

return ... :

Task4

C funzioni

chiamata

Esistono due tipi di sottoprogrammi: le procedure e le funzioni

Le funzioni restituiscono sempre un solo valore Le procedure non restituiscono valori

In C esistono solo funzioni

una 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 ß b b ß r

r ß 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;

}