Dal problema al programma
1.1 Introduzione intuitiva al concetto
di problema
Il problema è una situazione che pone delle domande alle quali si
devono dare delle risposte. Risolvere il problema vuol dire uscire dalla
situazione
Un problema è incertezza cioè mancanza di informazioni
Problemi e algoritmi
Un problema consta dei seguenti elementi
•Dati iniziali: ossia ciò che è noto (misura reale) e che
indichiamo col termine input
•Risultati o dati finali: gli elementi incogniti che si devono
determinare e che indicheremo con output
•Condizioni: le limitazioni o vincoli cui devono soggiacere i
risultati
Il “che cosa” e il “come”:
•
il problema descrive “che cosa” si deve calcolare
•
l’algoritmo descrive “come” effettuare un calcolo
1.2
Strategie per la risoluzione
dei problemi
Problema
Verifica dei risultati
Interpretazione
Esecuzione
Modello
Procedimento
risolutivo (algoritmo)
1.2 Strategie per la risoluzione
dei problemi
Interpretazione
TOP
DOWN
GRAFICO
Suddivide il problema in tanti
sotto-problemi fino ad
operazioni elementari
Utilizza uno schema
grafico a segmenti
Esempio di Problema
• Individuare il percorso più breve per andare a scuola
(scomponendo in sotto-problemi)
1.2 Strategie per la risoluzione
dei problemi
Algoritmo
Insieme dei comandi che definiscono una
sequenza finita di operazioni da eseguire
mediante le quali si risolve il problema
Deve essere :
finito
(numero limitato di passi: i comandi sono in numero finito
e vengono eseguiti un numero finito di volte);
definito
(ogni istruzione deve consentire un’interpretazione
univoca – non ambigua e precisa);
eseguibile
(la sua esecuzione deve essere possibile con gli
strumenti a disposizione);
deterministico
(ad ogni passo deve essere definita una ed una
sola operazione successiva).
Passo
• Azione elementare che deve essere intrapresa per procedere
nell’esecuzione dell’algoritmo.
Questo concetto richiede di stabilire l’insieme delle azioni che l’esecutore
dell’algoritmo (persona o la macchina) è in grado di svolgere.
Esempi di algoritmo
• Preparazione di una torta
Ricetta: descrizione precisa di un procedimento
“meccanico”
Esempi di algoritmo
• Prelevamento col Bancomat
Esempio di algoritmo (continua)
• L'algoritmo "va' dalla classe alla presidenza" si compone in realtà delle
seguenti istruzioni:
– esci dalla porta
– curva a destra
– attraversa la seconda porta sinistra
• L'algoritmo "attraversa la seconda porta sinistra " si compone di:
– controlla se la porta è aperta
– nel caso che la porta sia aperta salta il passo seguente
– apri la porta (cioè protendi braccio, afferra maniglia ….)
– avanza di un metro
Esempio di algoritmo
•
Un modo dettagliato di rappresentare l'algoritmo "attraversa la seconda porta
sinistra " specificando le sequenze sotto-algoritmiche è allora il seguente:
– controlla se la porta è aperta
– nel caso che la porta sia aperta salta il passo seguente
– apri la porta
─ protendi il braccio
─ afferra la maniglia
─ rotea la mano di 30 gradi in direzione antioraria
─ applica una pressione alla maniglia diretta di fronte a te
─ ...
– avanza di un metro
Esercizi
Spedire una lettera all’amico Giorgio che abita a Roma:
• 1 - Ordinare le seguenti operazioni:
- metto il foglio nella busta
- attacco il francobollo
- prendo una busta
- esco di casa
- imbuco la lettera nella cassetta
- aggiungo il c.a.p. di Roma
- prendo il francobollo
- vado all’ufficio postale
- scrivo sulla busta l’indirizzo di Giorgio
- chiudo la busta
- cerco il numero del c.a.p di Roma
- cerco l’indirizzo di Giorgio nella rubrica.
Esercizi
1. Elencare le azioni (passi) da eseguire per
risolvere i seguenti problemi:
1.
2.
3.
4.
Cucinare un piatto di pasta
Calcolare l’area di un quadrato noto il lato
Calcolare l’area di un quadrato noto il perimetro
Risolvere un’equazione di primo grado Ax=B noti
AeB
5. X casa: dati un cateto 10 cm e l’ipotenusa 20 cm di
un tr.rettangolo, trovare perimetro ed area.
Esercizi: soluzioni
1. Cucinare un piatto di pasta
1. Fare bollire l’acqua
2. Aggiungere la quantità di sale stabilita
3. Mettere la quantità stabilita di pasta nell’acqua
bollente
4. Fare cuocere la pasta per i minuti stabiliti
2. Calcolare l’area di un quadrato noto il lato
1. Ricevi in input la lunghezza del lato
2. Calcola l’area con la formula lato * lato
3. Comunica il risultato area
Esercizi: soluzioni
3. Calcolare l’area di un quadrato noto il perimetro
1.
2.
3.
4.
Ricevi in input la lunghezza del perimetro
Dividi il perimetro per 4 ottenendo il lato
Calcola l’area con la formula lato * lato
Comunica il risultato area
4. Risolvere un’equazione di primo grado Ax=B noti
AeB
1.
2.
3.
4.
5.
Inserire A
Inserire B
Verificare che A <> 0
Calcolare x = B/A
Comunicare il risultato x
1.2 Strategie per risoluzione dei
problemi
Rappresentazioni grafiche e
formalizzate di un algoritmo
La descrizione delle fasi esecutive del problema può
avvenire mediante la formalizzazione dei passi
elementari da effettuare che può essere realizzata con:
Diagramma a blocchi
o flow-chart
e/o
Pseudocodifica
1.2 Diagrammi a blocchi
Diagramma a blocchi o flow-chart
Ha il pregio di evidenziare visivamente l’avanzamento in
sequenza e le varie strutture che compongono l’algoritmo,
presenta istruzioni di input e/o output, calcolo e/o di
elaborazione, condizioni ed individua un inizio ed una fine.
inizio
OPERAZIONE
INPUT/OUTPUT
fine
1.2 Esempio di diagramma a
blocchi
Calcolare l’area di
un quadrato noto il
lato
inizio
lato
Area=lato * lato
Area
fine
1.2a Esercizi
Disegnare il diagramma a blocchi per gli esercizi
seguenti:
• Calcolare l’area di un quadrato noto il perimetro
• Risolvere un’equazione di primo grado Ax=B noti
AeB
1.2a Esempio di diagramma a
blocchi
inizio
Somma S di una
sequenza di N
numeri di valore
A variabile
N
S=
A
S= S+A
N=N-1
SI
N>
NO
S
fine