Programmazione Procedurale in Linguaggio C++

(1)

G. Mecca – Università della Basilicata – mecca@unibas.it

Linguaggio C++

Sottoprogrammi Parte 5

Metodologia di Sviluppo - a

versione 2.3

Questo lavoro è concesso in uso secondo i termini di una licenza Creative Commons (vedi ultima pagina)

2

Sommario

m

Metodologia per Raffinamenti

m

Esempio: Indovina il Numero

m

Esempio: “Sovrapposizione di Rettangoli”

Sottoprogrammi: Metodologia di Sviluppo >> Sommario

(2)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 3

Metodologia per Raffinamenti

m

Passi per la scrittura di programmi

ðeffettuare l’analisi delle specifiche ðscegliere l’algoritmo

ðscrivere il codice sorgente

ðcompilare e correggere gli errori sintattici ðverificare e correggere gli errori logici

m

I passi cruciali

ðalgoritmo, codice sorgente e verifica

Sottoprogrammi: Metodologia di Sviluppo >> Metodologia

Metodologia per Raffinamenti

m

Tecnica per raffinamenti successivi

ðindividuare (preliminarmente) una strategia di dichiarazioni per la rappresentazione dei dati ðpartire dalla specifica del problema

complessivo e sviluppare il main()

ðindividuare una prima divisione sommaria del problema in passi (sottoproblemi)

ðsupporre di disporre di un sottoprogramma per ciascun passo

(3)

m

Tecnica per raffinamenti successivi (cont.)

ðdefinire il prototipo del sottoprogramma

(modalità di comunicazione con l’esterno) ða questo punto è possibile scrivere una

prima versione del codice del main() usando sottoprogrammi che non esistono

ðaggiungendo scheletri “vuoti” dei

sottoprogrammi mancanti è già possibile compilare ed eseguire il codice per verificare

6

Metodologia per Raffinamenti

m

Tecnica per raffinamenti successivi (cont.)

ðper completare la soluzione, è necessario

scrivere il corpo dei sottoprog. mancanti ðin alcuni casi il sottoprogramma è

sufficientemente semplice da procedere per scrittura diretta del codice

ðin altri casi il sottoprogramma viene visto come un sottoproblema da affrontare e si riapplica il metodo

(4)

Metodologia per Raffinamenti

m

Tecnica per raffinamenti successivi (cont.)

ðquando devo sviluppare il sottoprogramma

p() divido il suo svolgimento in sottopassi ðindividuo un sottoprogramma p1()... pn() per

ciascun passo e ne definisco i prototipi ðscrivo il corpo di p() supponendo di usare i

nuovi sottoprogrammi

ðcompilo e verifico rapidamente il codice ðripeto ulteriormente il procedimento

Metodologia per Raffinamenti

m

Approccio dall’alto (“top-down”)

ðl’approccio procede da problemi più generali a problemi via via più specifici

m

Utilizzo di tecniche note “dal basso”

ðattenzione però ad individuare tutte le volte che è possibile procedere per scrittura diretta ðtipico caso: tecniche algoritmiche notevoli ðbisogna riconoscere l’applicabilità della

tecnica e programmarla senza risvilupparla

(5)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 9 main()

Sottoproblema n. 1 p1()

Scrittura diretta del codice Sottoproblema n. 1.1

p11()

Sottoproblema n. 1.2 p12()

Sottoproblema n. 3.1

Tecnica algoritmica

... nota

10

Metodologia per Raffinamenti

m

Caratteristica dell’approccio

ðla tecnica suggerita è centrata sulla scrittura del codice

ðil procedimento viene applicato lavorando direttamente sul codice sorgente

ðsi alternano fasi di riflessione sulla strategia a fasi di scrittura del codice

ða fasi di verifica incrementale del codice scritto (codice e test)

(6)

Metodologia per Raffinamenti

m

Riscontri frequenti e incrementali

ðcompilare frequentemente il codice scritto ðper intercettare precocemente gli errori

sintattici

ðeseguire il codice non appena si raggiungono punti stabili (es: lettura e stampa oppure soluzioni intermedie) ðper intercettare precocemente eventuali

errori logici

Indovina il Numero

m Specifica

ð il calcolatore acquisisce il nome del giocatore

ð il calcolatore sceglie un numero a caso compreso tra 1 e 100 ð il giocatore deve indovinare il numero facendo dei tentativi; ad

ogni tentativo, se il numero è corretto, il giocatore vince;

altrimenti il calcolatore risponde con un suggerimento che può essere “Prova con un numero più alto” oppure “Prova con un numero più basso”

ð il calcolatore tiene traccia del numero di tentativi effettuati dal giocatore

ð in qualsiasi momento il giocatore deve poter interrompere la partita e visualizzare il numero da indovinare

Sottoprogrammi: Metodologia di Sviluppo >> Indovina il Numero

(7)

m Analisi delle specifiche

ðdati di ingresso: nome del giocatore e sequenza dei tentativi

ðdati di uscita: messaggi del computer e numero di tentativi effettuati

m Domanda: come interrompere la partita ?

ðprima soluzione: un menu apposito presentato ogni volta (poco usabile)

ðseconda soluzione: valore 0 per il tentativo

m Algoritmo e codice (>>> scrittura del prog.)

14

Indovina il Numero

m

Riassumiamo il metodo

m

I iterazione: Programma principale

ðpasso n.1: inizia il gioco e acquisisci il nome ðpasso n.2: gioca le partite

m

Per ognuno dei passi (sottoproblemi)

ðun sottoprogramma

ðin alcuni casi è necessario ripetere il procedimento

(8)

Indovina il Numero

#include <iostream.h>

void schermoLeggiNome(string &nome);

void gioca(string nome);

void main() { string nome;

schermoLeggiNome(nome); // per il passo 1 gioca(nome); // per il passo 2 }

Indovina il Numero

m

schermoLeggiNome

ðscrittura diretta

m

gioca

ðapplico di nuovo il metodo

m

II iterazione: gioca

ðpasso 2.1: genera il numero ðpasso 2.2: gestisci tentativi

(9)

int generaNumero();

void gestisciTentativi(string nome, int numero);

void gioca(string nome) { int numero;

numero = generaNumero();

gestisciTentativi(nome, numero);

}

18

Indovina il Numero

m generaNumero

ðscrittura diretta

m III iterazione: gestisciTentativi

ðfinchè l’utente vuole andare avanti ðpasso 2.2.1: acquisisci il tentativo ðse il tentativo è uguale a 0

ðinterrompi il gioco

ðpasso 2.2.2: visualizza lo schermo di partita interrotta

ðaltrimenti se il tentativo è uguale al numero

ðpasso 2.2.3: visualizza lo schermo di vittoria

ðaltrimenti

ðpasso 2.2.4: analizza il tentativo e stampa l’esito Sottoprogrammi: Metodologia di Sviluppo >> Indovina il Numero

(10)

Indovina il Numero

// ...prototipi omessi per ragioni di spazio void gestisciTentativi(string nome, int numero) {

int giocata;

int tentativi = 0;

bool continua = true;

while (continua) {

giocata = schermoTentativo(nome, tentativi);

if (giocata == 0) { continua = false;

schermoInterruzione(nome, numero, tentativi);

} else { tentativi++;

if (giocata == numero) { continua = false;

schermoIndovinato(nome, tentativi);

} else {

schermoEsitoGiocata(nome, numero, giocata);

} } } return;

}

Indovina il Numero

m

schermoTentativo

ðscritura diretta

m

schermoInterruzione

ðscrittura diretta

m

schermoIndovinato

ðscrittura diretta

m

schermoEsitoGiocata

ðscrittura diretta

(11)

m

Tenere traccia dei tentativi effettuati

ðun classico problema di conteggio ðrisolvibile con una tecnica algoritmica

notevole: utilizzo di una variabile contatore ðriapplico la tecnica standard senza

riprogettarla

ðma semplicemente limitandomi ad adattarla al contesto applicativo specifico (tentativi)

22

Indovina il Numero

m

In sintesi quindi

ðil metodo guida il programmatore dall’inizio alla fine della scrittura del codice

ðapplicato sistematicamente consente di produrre abbastanza facilmente la soluzione ðconsente di ottenere riscontri rapidi su errori

sintattici ed errori logici e facilita la correzione

(12)

Sovrapposizione di Rettangoli

m Specifica

ðsiano dati due rettangoli nel piano cartesiano ðsi supponga che i due rettangoli abbiano i lati

paralleli agli assi cartesiani

ðanalizzare i rettangoli e stampare il quadrante in cui sono contenuti

ðverificare se i due rettangoli hanno una

sovrapposizione (una parte di piano che cade in entrambi i rettangoli)

ðse sì, stampare l’area della superficie comune

Sottoprogrammi: Metodologia di Sviluppo >> Rettangoli

Sovrapposizione di Rettangoli

m

Esempi

rettangoli nel I quadrante in questo caso c’è una superficie comune

I rettangolo a cavallo tra più quadranti

II rettangolo nel I quadrante

(13)

m

Analisi della specifica

ðè fondamentale l’ipotesi semplificativa per cui i lati sono paralleli agli assi

ðil problema principale è che i rettangoli possono essere in uno qualsiasi dei quadranti

ðe le posizioni reciproche possono essere varie (disgiunti, parz. sovrapp., tot. sovrapp.) ðla casistica è abbastanza ampia

26

Sovrapposizione di Rettangoli

m

Analisi della specifica (continua)

ðambiguità: nell’analisi del quadrante bisogna stabilire come considerare gli assi

ðsoluzione: stabiliamo di considerare gli assi come parte dei quadranti positivi

ðnel caso in cui il rettangolo non sia in un unico quadrante stamperemo un messaggio generico “Rettangolo tra più quadranti”

(14)

Sovrapposizione di Rettangoli

m

Strategia per la rappresentazione dei dati

ðci sono vari modi per rappresentare un

rettangolo

ðin questo caso utilizzeremo le coordinate di due dei vertici

ðogni rettangolo sarà rappresentato con 4 variabili reali

ð2 coordinate del vertice in basso a sinistra ð2 coordinate del vertice in alto a destra

Sovrapposizione di Rettangoli

m

Esempi

rettangolo 1: (1, 2) – (7, 6) rettangolo 2: (3, 1) – (8, 5)

rettangolo 1: (-2, 3.5) – (3, 5.5) rettangolo 2: (2, 1) – (6.2, 3)

(15)

m Per la scrittura del codice utilizzeremo il metodo

ðindividuazione di un modulo da scrivere (main o sottoprogramma)

ðdivisione in sottoproblemi (fase di progetto) ðscelta di un sottoprogramma per ciascun

sottoproblema

ðscrittura del modulo supponendo di avere a disposizione i sottoprogrammi

ðcompilazione e verifica parziale

ðripetizione dei passi precedenti per ulteriori moduli

30

Sovrapposizione di Rettangoli

m

Programma Principale: I Raffinamento

ðpasso 1: leggi i dati dei rettangoli

ðpasso 2: stampa i dati dei rettangoli ðpasso 3: analizza i quadranti

ðpasso 4: trova la superficie comune ðpasso 5: stampa il risultato

(16)

Sovrapposizione di Rettangoli

void leggiDatiRettangolo(float &x1,float &y1,float &x2,float &y2);

void stampaDatiRettangolo(float x1, float y1, float x2, float y2);

void stampaQuadrante(float x1, float y1, float x2, float y2);

float areaSovrapposizione(float x1,float y1,float x2,float y2, float x3,float y3,float x4,float y4);

void stampaRisultato(float superficie);

void main() {

float x1, y1, x2, y2, x3, y3, x4, y4;

float superficie;

leggiDatiRettangolo(x1, y1, x2, y2);

leggiDatiRettangolo(x3, y3, x4, y4);

stampaDatiRettangolo(x1, y1, x2, y2);

stampaQuadrante(x1, y1, x2, y2);

stampaDatiRettangolo(x3, y3, x4, y4);

stampaQuadrante(x3, y3, x4, y4);

superficie = areaSovrapposizione(x1,y1,x2,y2,x3,y3,x4,y4);

stampaRisultato(superficie);

}

NOTA: tutte le procedure sono

“schermi”

(il nome è abbreviato)

Sovrapposizione di Rettangoli

m II Raffinamento

ðpasso 1: procedura leggiRettangolo

> scrittura diretta del codice

ðpasso 2: procedura stampaRettangolo

ðpasso 3: procedura stampaQuadrante

> applico iterativamente il procedimento ðpasso 4: funzione areaSovrapposizione

> applico iterativamente il procedimento ðpasso 5: stampa il risultato

(17)

m

Come al solito

ðin generale scrivo prima il codice del modulo chiamante

ðe poi quello dei moduli chiamati

ðstabilisco un accordo relativo alla chiamata prima ancora di avere deciso i dettagli del codice

ðaccordo: nome del modulo, numero e tipo dei parametri, eventuale tipo del risultato

34

Sovrapposizione di Rettangoli

m

Passo 3: stampaQuadrante

ðpasso 3.1: trova il quadrante del vertice in basso a sinistra

ðpasso 3.2: trova il quadrante del vertice in alto a destra

ðse sono nello stesso quadrante ðstampa il quadrante

ðaltrimenti

ðstampa “Rettangolo tra quadranti diversi”

(18)

Sovrapposizione di Rettangoli

int quadrante(float x, float y);

void stampaQuadrante(float x1, float y1, float x2, float y2){

int q1, q2;

q1 = quadrante(x1, y1);

q2 = quadrante(x2, y2);

cout << "---\n";

if (q1 == q2) {

cout << "Rettangolo nel quadrante n. " << q1 << "\n";

} else {

cout << "Rettangolo a cavallo tra quadranti diversi \n";

}

cout << "---\n";

return;

}

Sovrapposizione di Rettangoli

m

Passo 3.1: quadrante

ðil passo 3.1 e il passo 3.2 richiedono la stessa funzione

ðdato un punto, deve restituire un numero intero corrispondente al quadrante

ðè possibile scrivere direttamente il codice analizzando il valore dell’ascissa e

dell’ordinata

(19)

int quadrante(float x, float y) { int q;

if (x >= 0 && y >= 0) { q = 1;

} else if (x < 0 && y >= 0) { q = 2;

} else if (x < 0 && y < 0) { q = 3;

} else { q = 4;

}

return q;

}

38

Sovrapposizione di Rettangoli

m

Passo 4: areaSovrapposizione

ðsi tratta di calcolare effettivamente l’area della sovrapposizione

m

In effetti

ðla sovrapposizione, se c’è, è un rettangolo ðposso pensare di calcolarne separatamente

la base e l’altezza ðe poi calcolarne l’area

(20)

Sovrapposizione di Rettangoli

m

Di conseguenza dovrei calcolare

ðl’eventuale sovrapposizione tra le due basi ðl’eventuale sovrapposizione tra le due

altezze

Sovrapposizione di Rettangoli

m

Passo 4: areaSovrapposizione

ðpasso 4.1: trova la lunghezza dell’eventuale sovrapposizione tra le basi

ðpasso 4.2: trova la lunghezza dell’eventuale sovrapposizione tra le altezze

ðse entrambe le lunghezze sono positive

ðcalcola il prodotto

ðrestituisci il prodotto calcolato

ðaltrimenti restituisci 0

(21)

m

In realtà

ðil passo 4.1 e il passo 4.2 corrispondono a ripetere due volte la stessa operazione ðtrovare la sovrapposizione tra due segmenti ðè un problema unidimensionale: dati due

generici segmenti su un asse, trovare la lunghezza dell’event. segmento comune ðla prima volta i segmenti sono le basi

ðla seconda volta i segmenti sono le altezze

42

Sovrapposizione di Rettangoli

m

Quindi

ðutilizzerò un’unica funzione

“lunghezzaSegmentoComune”

ðche lavora su due segmenti

ðogni segmento è rappresentato dalle coordinate dei due estremi su un asse

0 2 4 6 8

-2 I caso: segmento 1: (-1, 3)

segmento 2: (6, 8) II caso: segmento 1: (-1, 5)

segmento 2: (3, 8)

(22)

Sovrapposizione di Rettangoli

float lunghezzaSegmentoComune (float z1, float z2, float z3, float z4);

float areaSovrapposizione(float x1,float y1,float x2,float y2, float x3,float y3,float x4,float y4) { float sovrapposizioneBasi;

float sovrapposizioneAltezze;

float area = 0;

sovrapposizioneBasi = lunghezzaSegmentoComune(x1,x2,x3,x4);

sovrapposizioneAltezze =lunghezzaSegmentoComune(y1,y2,y3,y4);

if (sovrapposizioneBasi > 0 && sovrapposizioneAltezze > 0) { area = sovrapposizioneBasi * sovrapposizioneAltezze;

}

return area;

}

Sovrapposizione di Rettangoli

m

III Raffinamento

ðè necessario scrivere la funzione

“lunghezzaSegmentoComune”

m

Soluzione n.1

ðanalisi caso per caso

ðestremamente difficile da scrivere (casistica molto ampia)

(23)

m

Soluzione n.2

ðanalizzando il problema, è possibile trovare una formula compatta che risolve il problema ðdati due segmenti di estremi z1-z2 e z3-z4 ðcalcoliamo le lungh.: L1=|z2-z1|, L2=|z4-z3|

ðcalcoliamo la coordinata di valore più basso INF = min(z1, z3)

ðcalcoliamo la coordinata di valore più alto SUP = max(z2, z4)

46

Sovrapposizione di Rettangoli

m

Soluzione n.2 (continua)

ðcalcoliamo L = (L1 + L2) - |SUP - INF|

ðse L>0, i due segmenti hanno una porzione comune di lunghezza L

m

Intuizione

I caso: L1=5, L2=2, INF=1, SUP=8 L=5+2-|8-1|=0

II caso: L1=4, L2=2, INF=-1, SUP=8 L=4+2-|8+1|=-3

II caso: L1=6, L2=5, INF=-1, SUP=8 L=6+5-|8+1|=2

0 2 4 6 8

-2

(24)

Sovrapposizione di Rettangoli

m

Vantaggio della formula

ðfunziona in tutti i possibili casi (coordinate positive o negative, segmenti disgiunti, parzialmente o totalmente sovrapposti, ecc.) ðil codice è estremamente compatto

ðsoluzione elegante

ðma si tratta di un algoritmo per nulla scontato ðrichiede capacità di analisi e conoscenza

della geometria

Sovrapposizione di Rettangoli

m

A questo punto

ðil problema è praticamente risolto

ðè necessario utilizzare una funzione per il calcolo del minimo > scrittura diretta

ðè necessario utilizzare una funzione per il calcolo del massimo > scrittura diretta

ðla funzione lunghezzaSegmentoComune può essere scritta come segue

(25)

G. Mecca - Programmazione Procedurale in Linguaggio C++ 49 float minimo(float a, float b);

float massimo(float a, float b);

float lunghezzaSegmentoComune (float z1, float z2, float z3, float z4){

float lunghezza1, lunghezza2;

float estremoInferiore, estremoSuperiore;

float lunghezza;

lunghezza1 = fabs(z2-z1);

lunghezza2 = fabs(z4-z3);

estremoInferiore = minimo(z1, z3);

estremoSuperiore = massimo(z2, z4);

lunghezza = lunghezza1 + lunghezza2 -

fabs(estremoSuperiore - estremoInferiore);

return lunghezza;

}

50

Sovrapposizione di Rettangoli

m

Una volta completata la scrittura

ðè necessario verificare la correttezza

m

Verifica

ðè necessario costruire un insieme di dati di test per effettuare le verifiche

ðdevono rappresentare tutti o pressoché tutti i casi significativi

ðogni volta che il programma viene modificato, è necessario ripetere tutte le verifiche

(26)

Sovrapposizione di Rettangoli

m

Una porzione dei dati di test

rettangolo 1: (1, 2) – (7, 6) rettangolo 2: (3, 1) – (8, 5)

rettangolo 1: (-2, 3.5) – (3, 5.5) rettangolo 2: (2, 1) – (6.2, 3) sovrapposizione: 12 cm² sovrapposizione: 0

>> rettangoli1.cpp

Riassumendo

m

Metodologia suggerita

ðper raffinamenti successivi ðapproccio iterativo

ðe centrato sulla scrittura del codice

Sottoprogrammi: Metodologia di Sviluppo >> Sommario

(27)

m This work is licensed under the Creative Commons Attribution- ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-sa/1.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

m Questo lavoro viene concesso in uso secondo i termini della licenza “Attribution-ShareAlike” di Creative Commons. Per ottenere una copia della licenza, è possibile visitare

http://creativecommons.org/licenses/by-sa/1.0/ oppure inviare una lettera all’indirizzo Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.