Esistono alcune tipologie di problemi riconducibili a schemi di risoluzione standard:
Per ogni classe di problemi forniamo l’algoritmo in pseudo-codice, qualche indicazione sugli invarianti e un esempio:
Evento: istruzione che, una volta eseguita, cambia una parte dello stato del programma:
Supponiamo che:
Invarianti:
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”,
ContaEventi = “numero di tutti gli eventi della sequenza ottenuti finora”
con la struttura esegui …. fintanto che ….. si ha un algoritmo da adoperare solo se si è certi che la successione di eventi non è vuota
ContaEventi ← 0
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato):
ContaEventi ← ContaEventi + 1
ValoreEvento ← genera_evento(…)
ContaEventi ← 0
do:
ValoreEvento ← genera_evento(…)
If (ValoreEvento rappresenta un evento da contare )
ContaEventi ← ContaEventi + 1
while (ValoreEvento è un nuovo evento generato)
Esempio
Contare il numero di caratteri in una stringa (array di caratteri null-terminated)
int i=0;
while (stringa[i] != ‘\0′) {
i++;
}
contatore ← 0;
passo ← 0;
while stringa[passo] ≠ ‘\0′:
contatore ← contatore+1
passo ← passo+1
stampa(contatore)
Supponiamo che:
la funzione genera_evento(…) ad ogni invocazione generi (estragga) un nuovo evento di una sequenza;
bisogna contare solo eventi della sequenza che soddisfino una proprietà.
Invarianti:
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”,
ContaEventi = “numero degli eventi selezionati tra tutti quelli della sequenza ottenuti finora”
ContaEventi ← 0
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato):
if (ValoreEvento soddisfa la proprietà):
ContaEventi ← ContaEventi + 1
ValoreEvento ← genera_evento(…)
Esempio:
dato un array di N intericontare i numeri pari.
contatore ← 0;
passo ← 0;
while passo < N:
if (modulo(a[passo],2) = 0):
contatore ← contatore+1
passo ← passo+1
stampa(contatore)
Il valore di una variabile (di accumulazione) viene combinato mediante un operatore ∇ (es. somma, prodotto) con il valore di un nuovo evento.
Invarianti:
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”
Somma = “somma degli eventi selezionati tra tutti quelli della sequenza ottenuti finora”
Somma ← 0
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato):
Somma ← Somma ∇ ValoreEvento
ValoreEvento ← genera_evento(…)
Esempio
Dato un array di N interisommarli tutti.
somma ← 0;
passo ← 0;
while passo < N:
somma ← somma + a[passo]
passo ← passo+1
stampa(somma)
Il valore di una variabile (di accumulazione) viene combinato mediante un operatore ∇ (es. somma, prodotto) con il valore di un nuovo evento solo se soddisfa una proprietà.
Invarianti:
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”,
Somma = “somma degli eventi selezionati tra tutti quelli della sequenza ottenuti finora”.
Somma ← 0
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato):
if (ValoreEvento soddisfa la proprietà):
Somma ← Somma ∇ ValoreEvento
ValoreEvento ← genera_evento(…)
Esempio
Dati in input n numeri da tastiera sommare solo i numeri positivi (l’input si ferma quando si digita 0).
somma ← 0
leggi(num)
while num ≠ 0:
if (num > 0):
somma ← somma + num
leggi(num)
stampa(somma)
Valore sentinella
Una sequenza di eventi viene processata finché non viene generato (estratto) un evento che hauna certa proprietà (sentinella) producendo la terminazione di un ciclo
Invarianti
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”
“tutti gli eventi eccetto l’ultimo sono stati processati finora”
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato and not(ValoreEvento soddisfa la proprietà)):
processa(ValoreEvento)
ValoreEvento ← genera_evento(…)
Esempi
passo ← 0
while (passo < N e a[passo] ≠ 0):
passo ← passo + 1
stampa(passo)
leggi(cmd)
while cmd ≠ ’stop’:
esegui(cmd)
leggi(cmd)
Stabilire se, in una sequenza di eventi, ne esiste almeno uno avente una proprietà.
Invarianti
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”,
“nessun evento generato finora soddisfa la proprietà”.
Trovato ← ‘falso’
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato and Trovato = ‘falso’):
if (ValoreEvento soddisfa proprietà):
Trovato ← ‘vero’
ValoreEvento ← genera_evento(…)
Esempi
Dire se un array di N elementi contiene almeno un elemento nullo.
Trovato ← ‘falso’
passo ← 0
while (passo < N and Trovato = ‘falso’):
if (a[passo] = 0):
Trovato ← ‘vero’
passo ← passo + 1
stampa(Trovato)
Stabilire se, in una sequenza di eventi, tutti soddisfano una proprietà.
Invarianti
ValoreEvento = “ultimo valore ottenuto da una sequenza di eventi”,
“tutti gli eventi generati finora soddisfano la proprietà”.
Tutti ← ‘vero’
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato and Tutti = ‘vero’):
if not(ValoreEvento soddisfa proprietà):
Tutti ← ‘falso’
ValoreEvento ← genera_evento(…)
Esempi
Dire se un array di N elementi contiene tutti elementi pari.
Tutti ← ‘vero’
passo ← 0
while (passo < N and Tutti = ‘vero’):
if (modulo(a[passo],2) ≠ 0):
Tutti ← ‘falso’
passo ← passo + 1
stampa(Tutti)
Esercizi di ricapitolazione
1. Prime nozioni di Programmazione
2. C++ elementi di un programma
3. Le istruzioni di I/O standard
5. C++ funzioni matematiche ed espressioni booleane
6. Le strutture di controllo - parte seconda
8. Array di caratteri e tipi astratti
9. Astrazione procedurale: Procedure e Funzioni
10. Astrazione procedurale: Procedure e Funzioni -parte seconda
11. Astrazione procedurale: Procedure e Funzioni - parte terza
12. Librerie
13. Le strutture di controllo - parte terza
14. Algoritmi
16. I File di testo
17. La classe string