Programmazione Procedurale in Linguaggio C++

(1)

G. Mecca – Università della Basilicata – [email protected]

Programmazione Procedurale in Linguaggio C++

Strutture di Dati Conclusioni – parte b

versione 2.2

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

Sommario

m

Alcune Tecniche Notevoli

ðVerifica di Condizioni Locali ðVerifica di Condizioni Globali

m

Tecniche Algoritmiche: Riassunto

m

Errori Frequenti

Strutture di Dati: Conclusioni >> Sommario

(2)

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

Alcune Tecniche Notevoli

m

Nel programma sul lotto

ðalcune tecniche notevoli

ðverifica di condizioni su una collezione

m

Verifica di condizioni

ðdue tipologie

ðverifica di condizioni “locali”

ðverifica di condizioni “globali”

4

Alcune Tecniche Notevoli

m

Condizione “locale”

ðcondizione su un numero limitato di valori vicini della collezione

ðes: la lista contiene almeno un numero superiore a 80

ðes: la lista contiene almeno un numero superiore al successivo

ðes: la lista contiene almeno tre numeri consecutivi minori di 0

Strutture di Dati: Conclusioni >> Tecniche Notevoli

(3)

Alcune Tecniche Notevoli

m

Condizione “globale”

ðcondizione sulla collezione nel complesso ðes: tutti i numeri sono compresi tra 1 e 90 ðes: tutti i numeri sono diversi tra di loro ðes: la lista contiene tre numeri negativi (in

posizioni qualsiasi)

Alcune Tecniche Notevoli

m

Differenza tra i due casi

ðla verifica di condizioni locali è algoritmicamente intuitiva

ðposso effettuarla durante la scansione ðla verifica di condizioni globali è meno

intuitiva

ðsembrerebbe che sia necessario esaminare tutti i valori contemporaneamente (?)

(4)

Verifica di Condizioni Locali

m

Un Esempio

ðverificare che la giocata contenga almeno un numero superiore a 80

m

Idea

ðfino a prova contraria, non è soddisfatta ðanalizzo con un ciclo i valori della giocata ðse trovo un numero che soddisfa, mi fermo e

restituisco vero, altrimenti restituisco falso

8

Verifica di Condizioni Locali

bool numeriAlti(lista giocata) { bool trovato;

int i;

trovato = false;

i = 0;

while (!trovato && i < giocata.indicatore) { if (giocata.valori[i] > 80) {

trovato = true;

} else { i++;

} }

return trovato;

}

fino a prova contraria la condizione non è soddisfatta

se trovo un valore > 80 la condizione è

soddisfatta e il ciclo si ferma

(5)

Verifica di Condizioni Locali

m

Nota

ðcondizione del ciclo

while (!trovato && i<giocata.indicatore) {...}

ðla variabile booleana “trovato” viene usata come flag (bandiera) per comandare il ciclo

m

Il ciclo si ferma se

ðviene trovato un elemento > 80 (è inutile a questo punto guardare i successivi)

ðoppure gli elementi sono finiti

Verifica di Condizioni Locali

m

Al solito

ðè possibile anche scrivere la funzione senza utilizzare il flag (programm. non strutturata)

bool numeriAlti(lista giocata) { int i;

for (i = 0; i < giocata.indicatore; i++) { if (giocata.valori[i] > 80) {

return true;

} }

return false;

}

(6)

Verifica di Condizioni Locali

m

Attenzione

ðviceversa è scorretta la versione:

esempio: <10, 85, 4, 3>

false 3

3

false 4

2

true 85

1

false 10

0

trovato giocata.valori[i]

i bool numeriAlti(lista giocata) {

int i;

bool trovato = false;

for (i = 0; i < giocata.indicatore; i++) if (giocata.valori[i] > 80) {

trovato = true;

} else {

trovato = false;

}

return trovato;

}

12

Verifica di Condizioni Locali

m

Attenzione allo sconfinamento

ðse la condizione locale richiede di

ispezionare più di un elemento alla volta, è necessario fermare il ciclo prima del solito

m

Esempio

ðverificare se la lista contiene tre elementi negativi consecutivi

(7)

Verifica di Condizioni Locali

bool treNumeriAltiConsecutivi(lista giocata) { bool trovato;

int i;

trovato = false;

i = 0;

while (!trovato && i < giocata.indicatore - 2) { if (giocata.valori[i] > 80 &&

giocata.valori[i+1] > 80 &&

giocata.valori[i+2] > 80) { trovato = true;

} i++;

}

return trovato;

}

Verifica di Condizioni Globali

m

Apparentemente più complessa

m

Due possibili tecniche

m

Conteggio

ðconto gli elementi che soddisfano la

condizione e poi confronto il risultato con un numero di riferimento

m

Riduzione a condizione locale

ðmi riduco se possibile a verificare una condizione locale equivalente

(8)

Verifica di Condizioni Globali

m Conteggio

ðscandisco per contare quanti elementi soddisfano la condizione

ðal termine verifico se la condizione globale è soddisfatta

m Esempi

ðes: la lista contiene almeno 3 numeri negativi; conto i numeri < 0; al termine verifico se sono almeno 3 ðes: tutti i numeri sono compresi tra 1 e 90

conto i numeri tra 1 e 90 e confronto con l’indicatore di riempimento

16

Verifica di Condizioni Globali

m

Nota

ðquesto approccio è relativamente inefficiente ðinfatti, per contare devo sempre esaminare

tutti gli elementi

ðutilizzo tipicamente un ciclo for per scandire la lista completamente

ðin molti casi questo è inutile

(9)

Verifica di Condizioni Globali

m

Riduzione a condizione locale

ðidea: molto spesso una condizione globale è la negazione di una condizione locale

ðes: tutti i numeri sono compresi tra 1 e 90

>> non esiste un numero <1 o >90 ðes: tutti i numeri sono diversi >>

non esiste un numero che compare più volte nella lista

ðposso quindi verificare la condizione locale

ATTENZIONE alla riduzione

Verifica di Condizioni Globali

m

Riduzione (continua)

ðdevo però ragionare al contrario: per

verificare se la cond. globale è soddisfatta, devo verificare se la cond. locale è violata ðfino a prova contraria, la condizione globale

è soddisfatta (tutti i numeri sono tra 1 e 90) ðscandisco la lista, e se verifico che

localmente la condizione è violata (c’è un numero <1 oppure >90), vuol dire che la condizione globale non è soddisfatta

(10)

Verifica di Condizioni Globali

bool valoriAmmessi(lista giocata) { bool ammessi;

int i;

ammessi = true;

i = 0;

while (ammessi && i < giocata.indicatore) {

if (giocata.valori[i]>90 || giocata.valori[i]<1) ammessi = false;

else i++;

}

return ammessi;

}

fino a prova contraria la condizione globale è soddisfatta

(tutti numeri ammessi)

se trovo un valore che viola

localmente la condizione, la condizione globale non è soddisfatta e il ciclo si ferma

20

Verifica di Condizioni Globali

bool valoriAmmessi(lista giocata) { int i;

for (i = 0; i < giocata.indicatore; i++) {

if (giocata.valori[i] > 90 || giocata.valori[i] < 1){

return false;

} }

return true;

}

(11)

Tecniche Algoritmiche: Riassunto

m

Riassumiamo le principali tecniche viste

ðsomma con accumulatore

ðconteggio con contatore

ðuso dei flag per controllare un ciclo ðricerca del minimo e del massimo ðverifica di condizioni locali e globali ðoperazioni sulle liste:

inserimenti, cancellazioni, ricerche

Tecniche Algoritmiche: Riassunto

m

Altre tecniche viste

ðutilizzo di menu con comandi numerici ðgenerazione di numeri casuali

ðtecniche per la gestione dei formati dei file

Strutture di Dati: Conclusioni >> Tecniche Algoritmiche

(12)

Tecniche Algoritmiche: Riassunto

m

Utilizzo delle tecniche

ðin fase di progetto dell’algoritmo, procedo per decomposizioni (“dall’alto in basso”)

ðutilizzo sottoprogrammi opportuni per eseguire le operazioni individuate

ðripeto il procedimento quando necessario ðcerco però di ridurmi, quando possibile, a

tecniche note, e di riutilizzarne il codice ðin questo caso procedo “dal basso in alto”

24

Il Gioco del Lotto: Esempio n.1

m

Verifica che i numeri siano tutti diversi

ðper la soluzione posso comporre due

tecniche algoritmiche notevoli

ðverifica di condizione globale per riduzione (non esiste un numero che compare più di una volta)

ðconteggio (conto il numero di occorrenze di ogni elemento della giocata)

(13)

Numeri Tutti Diversi

int contaOccorrenze (lista l, float elem) { int i;

int conta = 0;

for (i = 0; i < l.indicatore; i++) { if (l.valori[i] == elem) {

conta++

} }

return conta;

}

Numeri Tutti Diversi

bool tuttiDiversi(lista giocata) { bool diversi;

int i;

diversi = true;

i=0;

while (diversi && i<giocata.indicatore) {

if(contaOccorrenze(giocata,giocata.valori[i])>1){

diversi = false;

} else { i++;

} }

return diversi;

}

fino a prova contraria la condizione globale è soddisfatta (tutti numeri diversi)

se trovo un valore che viola localmente la condizione, la condizione globale non è soddisfatta e il ciclo si ferma

(14)

Numeri Tutti Diversi

m

Nota

ðil codice è scritto frammentando la soluzione in due sottoprogrammi

ðuna funzione apposita per il conteggio delle occorrenze

ðavrei anche potuto evitare di separare il codice per il conteggio delle occorrenze ðma il risultato sarebbe stato di qualità

inferiore (cicli nidificati)

28 bool tuttiDiversi(lista giocata) {

bool diversi;

int i;

diversi = true;

i = 0;

while (diversi && i < giocata.indicatore) { int conta = 0;

int j;

for (j = 0; j < giocata.indicatore; j++) { if (giocata.valori[i] == giocata.valori[j]) {

conta++;

} }

if(conta > 1) { diversi = false;

i++;

} }

return diversi;

}

conta il numero di occorrenze di giocata.valori[i] in giocata

Nel complesso: codice meno leggibile e più difficile da manutenere (cicli nidificati) E’ PREFERIBILE

LA SOLUZIONE PRECEDENTE

(15)

Il Gioco del Lotto: Esempio n.2

m Calcolo del punteggio della giocata

ðdate due liste, verificare quanti elementi della seconda sono contenuti nella prima

m Idea

ðscandisco la seconda lista per contare gli elementi contenuti nella prima

ðper ciascun elemento della giocata (giocata.valori[i]), verifico se è presente nella lista dei numeri estratti (estrazione) >> per farlo ho una funzione pronta (cercaPos)

Punteggio della Giocata

int valoriComuni(lista estrazione, lista giocata){

int conta, i;

conta = 0;

for (i = 0; i < giocata.indicatore; i++) { if (cercaPosizione(estrazione,

giocata.valori[i]) != -1) { conta++;

} }

return conta;

}

verifica se l’i-esimo numero della giocata (giocata.valori[i]) è contenuto o meno nella lista dei numeri estratti (estrazione)

(16)

Errori Frequenti

m

Errori frequenti

ðpunto e virgola mancante dopo il modello della lista

ðgestione scorretta dell’indicatore di riempimento

ðsconfinamenti nella scansione della lista ðomettere o utilizzare scorrettamente le

istruzioni cin.ignore

32

Punto e Virgola Mancante

m

Lista

ðrappresentazione con record e array ðquindi la lista è un record

ðuno o più modelli di record ðuno o più punto e virgola

m

In assenza

ðal solito errore sintattico

Strutture di Dati: Conclusioni >> Errori Frequenti

(17)

Gestione Scorretta dell’Indicatore

m Inserimenti e cancellazioni

ðoltre ad aggiungere/togliere gli elementi all’array è necessario modificare l’indicatore

m In caso di inserimenti

ðl.indicatore++

m In caso di cancellazioni

ðl.indicatore—

m Altrimenti

ðè come se non fosse successo nulla

>> gestioneTemperature1.cpp

Sconfinamenti

m

Alcune operazioni

ðpossono richiedere scansioni non “standard”

della lista

ðes: cancellazioni: è necessario spostare in alto gli elementi

ðes: verifica di condizioni: può essere

necessario analizzare più elem. consecutivi (es: trovare tre valori negativi consecutivi)

(18)

Sconfinamenti

m

In questi casi

ðè indispensabile analizzare con cura le condizioni sul valore finale nei cicli

m

Cancellazione in posizione pos

for (i = pos; i < l.indicatore - 1; i++) { l.valori[i] = l.valori[i+1];

}

l.indicatore--;

esito = true;

36

Sconfinamenti

m

Verifica su tre elementi consecutivi

trovato = false;

i = 0;

while (!trovato && i < l.indicatore - 2) { if (l.valori[i] < 0 && l.valori[i+1] < 0

&& l.valori[i+2] < 0) { trovato = true;

} }

(19)

Riassumendo

m

Alcune Tecniche Notevoli

ðVerifica di Condizioni Locali ðVerifica di Condizioni Globali

m

Tecniche Algoritmiche: Riassunto

m

Errori Frequenti

Termini della Licenza

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.

Termini della Licenza

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.