Silvia Rossi » 9.Astrazione procedurale: Procedure e Funzioni

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

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

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

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.

Metodo dei raffinamenti successivi

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

Metodo dei raffinamenti successivi

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

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

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