Dal problema all’algoritmo Problema.
• Problema
Chiamiamo problema una qualsiasi situazione per cui è
• Algoritmo
necessario elaborare una strategia per identificare una
• Flow Chart (Diagramma sua soluzione, ovvero una serie azioni da compiere per
raggiungere il risultato.
a Blocchi)
• Esempi di Flow Chart
Ad esempio sono problemi le seguenti situazioni:
• disporre una lista di nomi in ordine alfabetico;
• Esercizi
•
calcolare l’area di un rettangolo conoscendone le
dimensioni
Non esiste un’unica soluzione per un problema.
Prima di identificare una strategia è necessario
distinguere i dati conosciuti (INPUT) dalle incognite che
bisogna determinare (risultati: OUTPUT).
Dal problema all’algoritmo Algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Chiamiamo algoritmo una sequenza ordinata di istruzioni
che descrivono tutte le azioni che è necessario eseguire per
arrivare alla soluzione di un problema.
Una definizione più rigorosa:
•
Un algoritmo è un insieme finito di istruzioni,
chiare e non ambigue, effettivamente calcolabili,
che, eseguito, fornisce un risultato , in una quantità
di tempo finita.
La sequenza di istruzioni che compone un algoritmo deve
essere:
• finita (l’esecutore deve arrivare prima o poi al risultato
richiesto, quindi le azioni descritte sono un numero
finito e ciascuna azione deve essere eseguita un numero
finito di volte)
• non ambigua (ciascuna istruzione deve essere descritta
chiaramente ed interpretata univocamente, di modo
che l’azione descritta sia effettuata allo stesso modo da
qualsiasi esecutore)
• eseguibile - effettivamente calcolabili(ciascuna azione
deve rientrare nelle effettive capacità dell’esecutore).
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Algoritmo
• Ciascuna istruzione può essere classificata come
istruzione di:
• input (lettura di un dato)
• output (scrittura di un dato o di un risultato)
• assegnazione (memorizzazione di un dato o di un
risultato)
• controllo (confronto tra valori, verifica di una
condizione e scelta del passo successivo in funzione
che la condizione verificata sia VERA o FALSA
Un algoritmo può essere graficamente schematizzato
attraverso i diagrammi di flusso (flow chart) detti anche
diagrammi a blocchi, che evidenziano il flusso delle
istruzioni nel processo di elaborazione dei dati del
problema.
Ciascun tipo di istruzione è rappresentato graficamente
attraverso simboli la cui forma indica il tipo di azione da
essi descritta.
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Diagramma a Blocchi
Un flow chart è un insieme di blocchi , contenenti le
istruzioni, collegati secondo il flusso (flow) di esecuzione
dell’algoritmo.
I blocchi contenenti le singole istruzioni sono collegati
tra loro da frecce, che evidenziano l’ordine in cui
eseguire le azioni descritte.
L’inizio e la fine dell’algoritmo sono rappresentati da
blocchi ovali. Sono gli unici blocchi da cui parte o arriva
una sola freccia.
Inizio
Fine
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Diagramma a Blocchi
Un flow chart è un insieme di blocchi , contenenti le
istruzioni, collegati secondo il flusso (flow) di esecuzione
dell’algoritmo.
I blocchi contenenti le singole istruzioni sono collegati
tra loro da frecce, che evidenziano l’ordine in cui
eseguire le azioni descritte.
ISTRUZIONI DI INGRESSO/USCITA (INPUT/OUTPUT)
Le istruzioni di ingresso e di uscita (input / output) sono
contenute in blocchi a forma di parallelogramma.
ISTRUZIONE DI INPUT
ISTRUZIONE DI OUTPUT
Leggi dato
Scrivi dato
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Diagramma a Blocchi
Un flow chart è un insieme di blocchi , contenenti le
istruzioni, collegati secondo il flusso (flow) di esecuzione
dell’algoritmo.
I blocchi contenenti le singole istruzioni sono collegati
tra loro da frecce, che evidenziano l’ordine in cui
eseguire le azioni descritte.
BLOCCO ISTRUZIONE O DI ELABORAZIONE
Le istruzioni contenenti operazioni sui dati
(assegnazione o calcolo di espressioni) sono
rappresentate all’interno di blocchi rettangolari.
Area = (base * Altezza) / 2
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Diagramma a Blocchi
Un flow chart è un insieme di blocchi , contenenti le
istruzioni, collegati secondo il flusso (flow) di esecuzione
dell’algoritmo.
I blocchi contenenti le singole istruzioni sono collegati
tra loro da frecce, che evidenziano l’ordine in cui
eseguire le azioni descritte.
BLOCCO DI CONTROLLO O CONDIZIONALE
Un blocco a forma di rombo contiene una condizione di
controllo che deve essere valutata; presenta pertanto un
solo ingresso ma due uscite, in corrispondenza del
valore (vero / falso) assunto dalla condizione descritta.
V
F
A > 10
Dal problema all’algoritmo
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Diagramma a Blocchi
Nella prossima slide è illustrato un diagramma a
blocchi relativo a un Algoritmo che risolve il problema
di identificare se un numero inserito in INPUT è
multiplo di 3 restituendo in OUTPUT un messaggio
sull’esito del risultato.
(Per verificare se un numero è multiplo di 3 è
sufficiente verificare che la divisione del numero con 3
fornisca resto uguale a 0. )
Esiste un operatore chiamato modulo che restituisce il
resto della divisione tra due numeri.
Esempio: 9 mod 3 = 0; 11 mod 3 = 2;
L’algoritmo legge in INPUT un numero, poi controlla
se il numero restituisce resto 0 nella divisione con 3 e
, in base al valore del resto, visualizzerà in OUTPUT il
messaggio.
Dal problema all’algoritmo
MULTIPLI DI 3
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Inizio
Leggi NUMERO
V
NUMERO mod 3 = 0
F
SCRIVI NUMERO non è
multiplo di 3
SCRIVI NUMERO è
multiplo di 3
Fine
Dal problema all’algoritmo
Diagramma a Blocchi
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Esercizi
Esercizi
1. Costruire un diagramma di flusso che rappresenti un
algoritmo per calcolare l’area di un qualsiasi
rettangolo.
2. Costruire un diagramma di flusso che rappresenti un
algoritmo che confronti 3 numeri naturali e scriva il
maggiore di essi.
3. Costruire un diagramma di flusso che rappresenti un
algoritmo che calcoli la potenza ennesima di un
numero sfruttando solo la moltiplicazione.
an = a ∙ a ∙ a ∙ …… ∙ a (numero di fattori a uguale a n)
Dal problema all’algoritmo
Diagramma a Blocchi
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Soluzione Esercizi
Esercizio 1
Inizio
Leggi BASE
Leggi ALTEZZA
AREA = BASE * ALTEZZA
Scrivi AREA
Fine
Dal problema all’algoritmo
Diagramma a Blocchi
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Soluzione Esercizi
Esercizio 2
V
SCRIVI il massimo è N1
Inizio
Leggi N1,N2,N3
V
F
N1 > N2
N1 > N3
F
F
N2 > N3
SCRIVI il massimo è N3
Fine
V
SCRIVI il
massimo è N2
Dal problema all’algoritmo
Diagramma a Blocchi
• Problema
• Algoritmo
• Flow Chart (Diagramma
a Blocchi)
• Esempi di Flow Chart
• Soluzione Esercizi
Esercizio 3
Inizio
Leggi BASE
Leggi ESPONENTE
I=1,POTENZA=1
I=I+1
ESEGUIRE L’ALGORITMO
PASSO PASSO SUL
SEGUENTE INPUT
BASE =3
ESPONENTE=4
POTENZA=POTENZA*BASE
F
I=ESPONENTE
V
Scrivi POTENZA
Fine
A cura di Alberto Landi