Paolo Amico
Problemi e Programmi
Informatica generale
Scienza della Comunicazione
CARATTERISTICHE FONDAMENTALI
DI UN ESECUTORE
Un’azione fondamentale presente in un processo eseguito da un
calcolatore è l’assegnamento.
V9
VE
E
Espressione, cioè una formula che specifica
sempre un valore.
Ogni espressione è composta da operandi e
operatori
Gli operandi possono essere costanti, espressioni o variabili
Gli operatori possono essere di tre tipi: aritmetici, di relazione e logici
CARATTERISTICHE FONDAMENTALE
DI UN ESECUTORE
Operatori aritmetici
+
addizione
-
sottrazione
*
moltiplicazione
div
Divisione tra numeri interi
/
Divisione tra numeri reali
mod
^
Calcolo del resto della divisione tra interi
Elevamento a potenza
CARATTERISTICHE FONDAMENTALE
DI UN ESECUTORE
Operatori di relazione
<
Minore di
<=
Minore o uguale di
>
Maggiore
>=
Maggiore o uguale di
<>
Diverso
CARATTERISTICHE FONDAMENTALI
DI UN ESECUTORE
Operatori logici
And
Per il prodotto logico (congiunzione)
Or
Per la somma logica (disgiunzione)
Not
Per la negazione
Xor
Per l’OR esclusivo
Diagrammi di flusso
•
•
•
Per la descrizione degli algoritmi si utilizzano particolari rappresentazioni
grafiche denominate diagrammi di flusso, schemi a blocchi o flowchart
Questa descrizione costituisce un efficace strumento per la descrizione
degli algoritmi, più valido di una esposizione di tipo discorsivo (troppo
generica e ambigua)
Qualsiasi algoritmo può essere decomposto in poche funzioni elementari
Trasferimento dati
Blocco operativo
Blocco decisionale
Inizio o fine
Simbolo di connessione
LA PSEUDOCODIFICA
La pseudocodifica è la descrizione di un algoritmo ottenuta utilizzando
termini e parole del linguaggio comune, ma applicando una serie di regole
che permettono di organizzare un tipo di testo formalmente rigoroso e
strettamente orientato alla stesura degli algoritmi.
La pseudocodifica utilizza delle regole per strutturare il testo:
 Le parole chiave che aprono e chiudono il testo di un algoritmo sono
INIZIO e FINE. Altre parole chiave sono A, ALLORA, ALTRIMENTI, CASO,
DA, DI, ESEGUI, FINCHE’, MENTRE, PASSO, PER, RIPETI, SE.
 Ogni istruzione è indicata con una frase del linguaggio corrente e può
contenere un’espressione di tipo aritmetico o logico
 Le istruzioni leggi(lista di variabili) e scrivi(variabili e costanti) vengono
utilizzate per descrivere le operazione di immissione ed emissione dei dati
 La richiesta all’utente per acquisire i dati necessari all’elaborazione può
essere indicata con chiedi(lista dei dati che servono)
 Le variabili, le costanti vengono indicate da parole in minuscolo dette
identificatori
ESEMPIO
h
b
A= b  h
Algoritmo rettangolo
Dati input
Base e altezza del rettangolo
Dati output
 Area del rettangolo
INIZIO
Chiedi(base, altezza)
Leggi(base, altezza)
Area  base * altezza
Scrivi area
FINE
ESEMPIO
Inizio
h
Chiedi base, altezza
b
A= b  h
Leggi base altezza
Dati input
Base e altezza del rettangolo
Dati output
 Area del rettangolo
Area base * altezza
Scrivi area
Fine
Programmazione Strutturata
La programmazione strutturata è una tecnica di programmazione che ha
lo scopo di semplificare la struttura di un algoritmo disciplinando
l'organizzazione di uno schema a blocchi
In particolare prevede l'uso di un numero limitato di strutture di controllo
fondamentali
Struttura di controllo: flowchart parziale da assumere come modello di
computazione, con un ingresso ed una uscita
La programmazione strutturata vincola quindi l'utilizzo delle strutture di
controllo, ma offre i seguenti vantaggi:
rende possibile una progettazione di tipo Top-Down
permette la definizione di algoritmi più leggibili, essendo più facile
individuare i moduli corrispondenti alle varie parti di cui si
compone l'algoritmo
test, correzione e manutenzione del programma sono perciò più
semplici
Programmazione strutturata
• Si assumono come strutture di controllo fondamentali:
A
Sequenza
B
Vero
Falso
p
A
B
Selezione binaria
A
While do (ripeti mentre)
Vero
p
Istruzioni per il controllo di flusso
•
Forniscono al programmatore il meccanismo per decidere se e come
eseguire blocchi di istruzioni condizionatamente a meccanismo decisionali
definiti all’interno della applicazione
Istruzioni per il controllo di flusso
Istruzione
Descrizione
if
Esegue o no un blocco di codice a seconda del valore restituito da
una espressione booleana
Esegue permette di selezionare tra due blocchi di codice quello da
eseguire a seconda del valore restituito da una espressione
booleana
Esegue ripetutamente un blocco di codice controllando il valore di
una espressione booleana
if-else
while
do-while
Esegue ripetutamente un blocco di codice controllando il valore di
una espressione booleana
Sequenza
• Flowchart della struttura sequenza
– Due azioni eseguite in ordine
somma l’inverso del
cubo di i ad s
Incrementa il contatore
Ciclo while
Vero
p
A
Esegue una istruzione mentre una condizione è verificata
Ciclo do-while
A
p
Falso
Vero
Esegue una istruzione finché una condizione diventa falsa
La selezione binaria if
• È usata per scegliere fra due alternative
– Pseudocodice
• Se il voto è maggiore di 18 allora l’esame è superato
Vero
Falso
voto>=18
stampa
Esempio di flowchart della
struttura if
if è una struttura con un solo
punto di uscita
La selezione binaria if/else
• Strutture di selezione
– if
• Esegui una singola operazione se la condizione è vera
– if/else
• Esegui operazioni diverse quando la condizione è vera
o quando è falsa
• Pseudocodice
•
Se il voto è maggiore o uguale di 18
Stampa “Esame superato”
altrimenti
Stampa “Esame non superato”
La selezione binaria
if/else
falso
vero
voto >= 18
Stampa “Esame non superato”
Stampa “Esame superato”
Ciclo controllato da un contatore
START
stampa 30 volte
la parola TRE
C := 1
stampa “TRE”
V
END
C = 30
F
C := C + 1
Ciclo controllato da un contatore
• Media dei voti:
– Descrizione del problema:
• Una classe di 10 studenti affronta un quiz. I
risultati sono interi fra 0 e 100. Calcolare la media
complessiva.
• È una iterazione controllata da un contatore
– Il ciclo viene ripetuto finché un contatore non
raggiunge un determinato valore
– Il numero di iterazioni è noto: si usa un contatore
• Descrizione a parole:
1. azzera somma parziale - accumulatore
2. azzera il contatore dei numeri già introdotti
3. leggi un dato
4. somma il dato all’accumulatore
5. incrementa il contatore
6. se il numero di dati letti (contatore) è minore di 10 torna a 3,
altrimenti continua
Inizio
7. stampa la media
I=0
S=0
I contatore
S accumulatore
I=I+1
Vero
Falso
I<10
Lettura
dato Di
S: = S + Di
Stampa media
Fine
START
AeB>0
somma due
numeri avendo a
disposizione solo
l’operazione di
incremento
unitario
(macchina a
strati)
dati A B
RIS := A; CON := 1
RIS := RIS + 1
V
stampa RIS
END
CON = B
F
CON := CON + 1
START
AeB>0
moltiplica due
numeri avendo
a disposizione
solo
l’operazione di
somma
(macchina a
strati)
dati A B
RIS := 0; CON := 1
RIS := RIS + A
V
stampa RIS
END
CON = B
F
CON := CON + 1
Ciclo controllato da una sentinella
Problema: costruire un algoritmo che, assegnati N dati numerici
A1, A2, A3, …, AN
Con N non noto a priori, sia capace di:
1)
2)
Contare i dati, ossia determinare N
Calcolare la somma S dei Dati
Occorre un contatote Ct che, inizialmente azzerato, viene incrementato di una
unità ogni volta che uno dei dati viene introdotto in memoria
Occorre una sentinella (flag) adibita a segnalare il momento in cui si realizza
L’evento: “la lettura dei dati è terminata”
A tale scopo si usa una variabile che chiameremo spia e che manterremo
Spenta (spia=0) per tutta la durata della lettura dei dati eche accenderemo
(spia=1) subito dopo l’immissione dell’ultimo dato
Algoritmo
INIZIO
Spia:=0
Ct:=0
S:=0
Ripeti
Introduzione del dato in A
Introduzione di 0 o 1 in spia a seconda che la lettura dei dati non sia, o sia
terminata
Incrementa il contatore
Incrementa la somma
Finché (spia=1)
Visualizza contatore
Visualizza somma
FINE
Inizio
Spia: = 0
Ct: = 0
S:=0
Lettura
dato A, spia
Ct: = Ct+1
S:=S+A
falso
Spia=1
vero
N=Ct
Somma=S
Fine
MCD(m,n) m,n >0
Leggi m
Leggi n
m>n
minm
1. Leggi m e n;
2. considera il minore tra i due
numeri (min)
3. verifica se min è divisore sia di m
che di n. In caso positivo min è il
MCD cercato altrimenti
3.1 sottrai 1 a min e torna al punto
3
si
minn
r1m mod min
r2n mod min
(r1=0 and r2=0)
si
minmin-1
Stampa min