Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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


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 (PG): 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

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


Metodo dei raffinamenti successivi

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


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:


Metodo dei raffinamenti successivi

2. Individuare un algoritmo:

Come partenza si individui una serie di macro azioni che risolvono il problema


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)


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)


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)


Metodo dei raffinamenti successivi

4. implementazione:

Ogni azione dell’algoritmo è traducibile in istruzioni del linguaggio C++

esercizio9.1.cpp


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

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)

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)

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

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

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


C++ funzioni → argomenti

esercizio9.2.cpp


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion