Classi di algoritmi
Esistono alcune tipologie di problemi riconducibili a schemi di risoluzione standard
• una volta individuato lo schema opportuno si dovrà solo adattarlo al caso particolare per poter scrivere l’algoritmo in pseudocodice
Per ogni classe di problemi forniamo l’algoritmo in pseudo-codice, qualche indicazione sugli invarianti e un esempio
• si consiglia di tradurre ogni esempio nel linguaggio C
Evento: istruzione che, una volta eseguita, cambia una parte dello stato del programma
• una istruzione di assegnazione,
• un accesso a un elemento di un array
Iterazione controllata da un contatore
Ripetizione definita
• Il numero di iterazioni è già noto prima dell’inizio del ciclo
Conteggio di eventi
Supponiamo che
la funzione genera_evento(…) ad ogni invocazione generi (estragga) un nuovo evento di una sequenza
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):
genera_evento()
conta
Conteggio di eventi
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)
Conteggio di eventi selezionati
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(…)
genera_evento()
conta
Conteggio di eventi selezionati
Esempio:
dato un array di N interi contare i numeri pari
contatore ß 0;
passo ß 0;
while passo < N:
if (modulo(a[passo],2) = 0):
contatore ß contatore+1 passo ß passo+1
stampa(contatore)
genera_evento()
conta
Accumulatore di eventi
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(…)somma
Ñ
genera_evento()
Accumulatore di eventi
Esempio:
dato un array di N interi sommarli tutti
somma ß 0;
passo ß 0;
while passo < N:
somma ß somma + a[passo]
passo ß passo+1 stampa(somma)
somma
Ñ
genera_evento()
Accumulatore eventi selezionati
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(…)
somma
Ñ
genera_evento()
Accumulatore eventi selezionati
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)
somma
Ñ
genera_evento()
Iterazione controllata da sentinella
Valore sentinella
• Ha lo scopo di indicare la fine dei dati
• Ripetizioni indefinite
• Non scegliere un valore sentinella che può essere anche un
valore legittimo di input
Tecnica della sentinella (skipping)
Una sequenza di eventi viene processata finché non viene generato (estratto) un evento che ha
una 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(…)s
genera_evento()
processa processa
STOP
Tecnica della sentinella (skipping)
Esempi:
Dare la posizione del primo elemento nullo di un array di N elementi
Ciclo di esecuzione di comandi con arresto se si digita 'stop'
Tutte le volte che si processano gli
elementi di un array di dimensione N
s
genera_evento()
processa processa
STOP
leggi(cmd)
while cmd ¹ 'stop':
esegui(cmd) leggi(cmd) passo ß 0
while (passo<N e a[passo] ¹ 0):
passo ß passo + 1 stampa(passo)
Algoritmo "esiste"
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(…)
genera_evento()
Algoritmo "esiste"
Esempi:
Dire se un array di N elementi contiene almeno un elemento nullo
genera_evento()
Trovato ß 'falso' passo ß 0
while (passo < N and Trovato = 'falso'):
if (a[passo] = 0):
Trovato ß 'vero' passo ß passo + 1 stampa(Trovato)
Algoritmo "tutti"
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(…)
genera_evento()
Algoritmo "tutti"
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)
genera_evento()
