Per la costruzione di un programma conviene · abbastanza vicino ai linguaggi di programmazione ......

Sviluppo di programmi

Per la costruzione di un programma conviene: 1. condurre un’analisi del problema da risolvere

2. elaborare un algoritmo della soluzione rappresentato in un linguaggio adatto alla comprensione degli esseri umani ma abbastanza vicino ai linguaggi di programmazione

3. produrre un programma scritto nel linguaggio di programmazione scelto


• FASE 1: Dare un nome al problema partendo dall’analisi del problema

• FASE 2: Scrivere la specifica funzionale • FASE 3: Scrittura dell’algoritmo

– FASE 3.1: Introduzione dei contenitori di dati (variabili) necessarie e delle relative operazioni elementari

– FASE 3.2: Specifica di un diagramma di flusso ( o di uno pseudo codice) che descrive in modo preciso e non ambiguo la sequenza di operazioni da eseguire

• FASE 4: Traduzione del diagramma di flusso ( o dello pseudo codice) in un programma in un linguaggio di programmazione

FASE 1: problema e sua analisi

• L’analisi di un problema è la primissima cosa da fare quando si è di fronte alla richiesta di risolverlo

• Bisogna capire bene il problema prima di pensare di risolverlo!

• L’analisi del problema deve fornire come prodotto: – un nome ed una breve descrizione di cosa si vuol fare

– un elenco di requisiti, ovvero, di richieste, vincoli che il programma deve soddisfare

Esempio di Analisi del problema: ax2+bx+c

• Problema: CALCOLO RADICI

• Descrizione: calcolare le soluzioni reali di una equazione di secondo grado

• Requisiti: l’equazione può avere nessuna soluzione reale, due soluzioni coincidenti, o due soluzioni distinte. Si devono, in questi casi, evidenziare il messaggio

– nessuna radice

– radici coincidenti r (dove r è il valore delle radici)

– radici distinte r1 ed r2 (dove r1 ed r2 sono il valore delle radici)

FASE 2: specifica funzionale

• Una specifica funzionale descrive: – quali sono i dati iniziale, ovvero i dati di input (ingresso) da

elaborare

– qual è il risultato atteso in funzione dei dati in ingresso (output, uscita dell’algoritmo)

Esempio di specifica funzionale

CALCOLO RADICI: specifica funzionale

• INPUT: i numeri reali a,b,c che sono i coefficienti dell’equazione da risolvere

• OUTPUT: i messaggi – “nessuna radice reale”

– “x1=x2=r” se l’equazione ha due radici reali coincidenti pari ad r

– “x1=r1, x2=r2” se l’equazione ha due radici reali distinte pari ad r1 ed r2

FASE 3: scrittura dell’algoritmo

• Descrizione dell’algoritmo, ovvero, dei passi da eseguire per giungere al risultato di uscita partendo dai dati in input

• La prima stesura non necessariamente deve essere completa di ogni dettaglio. in genere, si procede per raffinamenti successivi (analisi TOP-DOWN del problema)

Esempio di stesura preliminare di algoritmi

CALCOLO RADICI: stesura preliminare dell’algoritmo • risolvo il problema calcolando il discriminante (delta)

dell’equazione • analizzo i vari casi di delta

– <0 – =0 – >0

• costruisco per ognuno di questi casi il messaggio da produrre in output

• Successivamente si definiscono le variabili (contenitori di dati) coinvolte e dettaglio la specifica dell’algoritmo usando un diagramma di flusso o lo pseudo codice.




– FASE 3.1: Introduzione delle variabili (contenitori di dati) necessarie e delle relative operazioni elementari



FASE 3.1: definizione delle variabili

• Ogni algoritmo deve tenere traccia (memorizzare) i valori dei dati in input, dei risultati in output, e dei valori intermedi calcolati durante l’esecuzione dei passi

• A questo fine si usano delle variabili (contenitori di dati). Ogni variabile ha un nome associato al dato (valore) memorizzato.

• Una variabile è una astrazione (semplificazione) della nozione di area di memoria (una o più celle della RAM, un registro generale) contenente i bit rappresentanti i dati

• I dati contenuti in una variabile hanno un tipo (si dice che una variabile è di un certo tipo) che caratterizza un insieme di elementi e le operazioni che sono possibili su di essi


• Ogni variabile memorizza il valore di un dato

• Ogni dato appartiene ad un tipo di dato

• Un tipo di dato è: un insieme di elementi, rappresentabili in modo finito, dotato di operazioni primitive su di esso

• ESEMPIO: il tipo di dato intero – è l’insieme dei numeri interi, sequenze di cifre, con segno

– dotato di operazioni primitive ed effettivamente eseguibili come somma (+), differenza (-), prodotto (*), divisione intera (/), resto.


• Le variabili da usare per memorizzare i valori dei dati intermedi dipendono dall’algoritmo

• All’inizio della stesura di un algoritmo difficilmente si è già a conoscenza di quante e quali variabili si dovranno usare

• Ad ogni raffinamento dell’algoritmo si possono aggiungere o togliere variabili fino ad arrivare all’uso corretto di ognuna

Esempio di definizione di variabili

CALCOLO RADICI: variabili usate

• ci vogliono tante variabili quanti sono i dati in input. In questo caso ci vogliono tre variabili che chiamiamo a,b,c per i coefficienti dell’equazione

• ci vogliono tante variabili quanti sono i dati in uscita. In questo caso, servono due variabili r1,r2 per il valore delle radici dell’equazione

• ci vogliono alcune variabili per tenere conto di dati intermedi da calcolare e modificare per ottenere la soluzione. In questo caso, potremmo usare una variabile per memorizzare il valore del discriminante. La variabile la chiamiamo delta

• Il tipo di tutte queste variabili è float (numeri reali).

Descrizione di un algoritmo

• Si descrive un algoritmo cercando di sintetizzare il più possibile la sua sequenza di passi;

• Non si utilizza un linguaggio di programmazione specifico, ma è meglio utilizzare qualcosa di più generale;

• Pseudo-codici o Diagrammi di Flusso


• Un algoritmo descrive due tipi fondamentali di operazioni: – calcoli ottenibili tramite le operazioni primitive su tipi di dato

(valutazione di espressioni)

– azioni che consistono nella modifica del valore associato alle variabili

Calcoli: espressioni valutabili

• L’esecutore dell’algoritmo valuta espressioni dove gli elementi possono essere variabili o valori costanti

– 3 * X + sin (Y * sqrt(z))

– b*b-4*a*c

– h/j

– k / 2.23

– 192

Calcoli: espressioni booleane (logiche)

• Ci sono anche particolari tipi di espressioni chiamate booleane o logiche

• Sono espressioni che possono dare origine a due soli possibili valori: VERO o FALSO

• Una proposizione della quale dobbiamo valutare se è vera o falsa

• Per costruire un’espressione logica si possono usare le seguenti relazioni: – = (uguaglianza); – < (minore); <= (minore o uguale); – > (maggiore); >= (maggiore o uguale); – <> (diverso);

Calcoli: espressioni logiche complesse - NOT

• Possiamo costruire espressioni booleane più complesse grazie ad alcune regole della cosiddetta algebra booleana;

• Se A è un’espressione logica, anche Not A (la negazione logica di A) lo è

A Not A Vero Falso

Falso Vero

Congiunzione (AND)

• Se A e B sono espressioni logiche, anche A and B lo è;

A B A and B Vero Vero Vero

Vero Falso Falso

Falso Vero Falso

Falso Falso Falso

Disgiunzione (OR)

• Se A e B sono espressioni logiche, anche A or B lo è;

A B A or B Vero Vero Vero

Vero Falso Vero

Falso Vero Vero

Falso Falso Falso


• Un algoritmo descrive due tipi fondamentali di operazioni: – calcoli ottenibili tramite le operazioni primitive su tipi di dato

(valutazione di espressioni)

– azioni che consistono nella modifica del valore associato alle variabili

Azioni: modifica valori delle variabili

L’esecutore di un algoritmo deve poter compiere azioni che hanno un effetto sui dati gestiti

Le azioni più semplici sono assegnamenti a variabili

Un assegnamento ad una variabile si denota con

VARIABILE:= ESPRESSIONE

con il seguente significato: 1. l’esecutore valuta l’espressione a destra del :=

2. e poi modifica il valore della variabile con il risultato della valutazione dell’espressione

Esempi di azioni: assegnamenti a variabili

• L’esecutore valuta espressioni dove gli elementi possono essere variabili o valori costanti e se ne assegna il valore ad una variabile

pippo := 3 * X + sin (Y * sqrt(z))

delta := b*b-4*a*c

a := h / j

W := k / 2.23

M := 192

T := p

x := x + 1

• Una variabile non può essere “vuota”: ad una variabile deve sempre essere associato un valore

• Il valore contenuto in una variabile è l’ultimo assegnatole e resta inalterato finché una successiva assegnazione non modifica il valore stesso

Formalismi per la descrizione di algoritmi

• Per descrivere in passi di un algoritmo bisogna essere precisi e non ambigui

• Il linguaggio naturale degli esseri umani si presta a interpretazioni non univoche

• Si usano due formalismi: – diagrammi di flusso: formalismo grafico

– pseudo-codice: linguaggio con istruzioni simili a quelle dei linguaggi di programmazione

• si possono usare in alternativa

Specifica di inizio e di fine

• Ogni algoritmo deve avere un inizio ed una fine

start start

…

…

…

…

…

…

end end

Input ed output di dati

• Ogni algoritmo parte da dati in ingresso per produrre dati in uscita (problema computazionale)

…

read X readX …

… write Z write Z

…

Specifica delle azioni

• Ogni algoritmo specifica azioni che l’esecutore deve compiere del tipo descritto in precedenza

…

Z := X + 1 Z := X + 1 …

Specifica delle condizioni logiche

• Alcuni passi di un algoritmo si devono eseguire se sono verificate condizioni logiche su valori di variabili

• In genere, questi salti dell’algoritmo sono sottoposti ad una condizione logica (risposta vero o falso);

• Si parla di blocchi decisionali


azioni ……

azioni

if (condizione logica) then condizione azioni caso vero logica

vero falso else azioni azioni azioni caso falso

caso vero caso falso end if

azioni seguenti comuni azioni seguenti

comuni ……


azioni ……

azioni

if (condizione logica) then condizione

logica azioni caso vero vero

end if azioni falso azioni seguenti comuni caso vero

……

azioni seguenti comuni

Condizioni logiche Annidate: esempio ……

azioni azioni

if (condizione logica 1) then condizione if (condizione logica 2) then

logica 1 vero falso azioni vero 2

else vero condizione falso condizione azioni falso 2

logica 2 logica 3 vero end if

falso else

azioni vero 2 azioni falso 2 azioni vero 3 if (condizione logica 3) then

azioni vero 3

end if

end if azioni seguenti azioni seguenti comuni

comuni ……

Flusso di esecuzione

• I singoli diagrammi devono essere uniti tramite i connettori (linee e frecce in un flow chart);

• L’esecuzione dei passi deve essere fatta sequenzialmente, ovvero seguendo i connettori, partendo dall’inizio dell’algoritmo fino a raggiungere la sua fine

• Quando si scrive l’algoritmo bisogna fare molta attenzione alla direzione del flusso di esecuzione

Strutture di controllo: iterazione

azioni … azioni while (condizione logica)

azioni da azioni da ripetere ripetere

end while condizione

azioni seguenti logica vero …

falso

azioni seguenti

Strutture di controllo: iterazioni annidate

azioni …

azioni

while (condizione logica esterna) azioni iterazione

interna da ripetere while (condizione logica interna)

azioni iterazione interna da ripetere vero azioni iterazione condizione end while

logica esterna da ripetere interna

azioni iterazione esterna da ripetere falso

end while vero condizione

logica azioni seguenti esterna

… falso

azioni seguenti

Esempio di algoritmo

• Scrivere l’algoritmo che esegue la somma di due numeri

start

start read X

read X

read Y read Y

Z := X + Y

write Z Z := X + Y

end

write Z

end

Esempio: massimo tra due numeri

Dati due numeri, dire qual è il massimo tra i due. start start

read X read X

read Y read Y if (X > Y) then

vero falso max := X X>Y

else max := X max := Y

max := Y

end if write max

write max end end

Esempio di algoritmo: calcolo radici start

start read a,b,c

read a,b,c delta := b*b-4*a*c delta:=b*b-4*a*c if (delta < 0) then

falso vero write “nessuna radice” delta < 0

else r1 := (-b + sqrt(delta))/2*a r1 := (-b+sqrt(delta))/2*a

write r2 := (-b-sqrt(delta))/2*a r2 := (-b - sqrt(delta))/2*a "nessuna radice"

write r1,r2 write r1,r2 if (delta = 0) then

write “radici coincidenti” delta = 0

vero falso else write write

"radici coincidenti" "radici distinte" write “radici distinte” end if

end if end end

Esercizio: massimo di una sequenza

• Si supponga di fornire in input ad un programma un numero indefinito di interi positivi. L’inserimento verrà terminato dall’utente quando questi inserirà uno zero (0). Il programma deve restituire il valore massimo tra quelli introdotti. Disegnare il diagramma di flusso di tale Programma e scrivere lo stesso tramite in pseudo linguaggio (o linguaggio di progetto).

Per la costruzione di un programma conviene · abbastanza vicino ai linguaggi di programmazione ......

Documents

Transcript of Per la costruzione di un programma conviene · abbastanza vicino ai linguaggi di programmazione ......