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
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Silvia Rossi » 15.Algoritmi - parte seconda


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


Conteggio di eventi (segue)

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 )

ContaEventiContaEventi + 1

while (ValoreEvento è un nuovo evento generato)


Conteggio di eventi (segue)

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”


Conteggio di eventi selezionati (segue)

ContaEventi ← 0
ValoreEvento ← genera_evento(…)
while (ValoreEvento è un nuovo evento generato):

if (ValoreEvento soddisfa la proprietà):

ContaEventiContaEventi + 1

ValoreEvento ← genera_evento(…)


Conteggio di eventi selezionati (segue)

Esempio:
dato un array di N interi contare i numeri pari.

contatore ← 0;
passo ← 0;
while passo < N:

if (modulo(a[passo],2) = 0):

contatorecontatore+1

passopasso+1

stampa(contatore)


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

SommaSommaValoreEvento
ValoreEvento ← genera_evento(…)


Accumulatore di eventi (segue)

Esempio
Dato un array di N interi sommarli tutti.
somma ← 0;
passo ← 0;
while passo < N:

sommasomma + a[passo]
passopasso+1

stampa(somma)


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(…)


Accumulatore eventi selezionati (segue)

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

sommasomma + num

leggi(num)

stampa(somma)


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(…)


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.

passo ← 0
while (passo < N e a[passo] ≠ 0):

passopasso + 1

stampa(passo)

leggi(cmd)
while cmd ≠ ’stop’:

esegui(cmd)
leggi(cmd)


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(…)


Algoritmo “esiste” (segue)

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’

passopasso + 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(…)


Algoritmo “tutti” (segue)

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’

passopasso + 1

stampa(Tutti)


Esercizi

Esercizi di ricapitolazione

  1. Utilizzando i costrutti while, do … while e for, scrivere un programma che stampi la tabella indicata in figura.
  2. Si scriva un programma che riceva da input una serie di interi non nulli e stampi su video il valore minimo, il valore massimo e la somma dei valori negativi.
  3. Dato un array di N elementi scrivere una funzione che restituisce il più piccolo indice, se esiste, cui corrisponde un numero primo, zero altrimenti.
  4. Dato un array di N elementi, scrivere una funzione che restituisca true se tutti gli elementi sono pari.

  • 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