Esercitazione su algoritmi e diagrammi di flusso

(1)

Laboratorio di Informatica

Esercitazione su algoritmi e diagrammi di flusso

(2)

Algoritmi, programmi e dati

Algoritmo = insieme di istruzioni che indicano come svolgere operazioni complesse su dei dati attraverso successioni di operazioni elementari

Programma = algoritmo in un linguaggio

“comprensibile” dal computer.

Dato = informazione da elaborare rappresentata in

un formato che consenta al programma di operare su

di essa

(3)

Diagrammi di flusso

metti x+y in y

metti x-1 in x x = 0

Blocchi di elaborazione

contengono sequenze di azioni

Blocchi decisionali

contengono una condizione booleana; se vera, si segue la freccia vero, se falsa si segue la freccia falso.

vero falso

(4)

Strutture di controllo principali

selezione sequenza

falso vero

(5)

Strutture di controllo principali

iterazione

vero

falso

(6)

Esempio di decomposizione modulare

(7)

Simboli principali

• inizio o fine

• elaborazione

• decisione

• Connessione

• Operazione input/output

(8)

Processo di sviluppo di un programma

Il processo di sviluppo di un programma prevede le seguenti fasi:

– analisi del problema e specifica funzionale

• specificazione dei dati in ingresso e in uscita

– definizione dell’algoritmo risolutivo

• identificazione e formalizzazione di una soluzione, cioè dei contenitori di dati necessari e delle relative operazioni

– descrizione con un diagramma di flusso

• o con altro formalismo preciso e non ambiguo della successione di operazioni da eseguire.

– traduzione del diagramma di flusso in un programma

• in un linguaggio di programmazione “ad alto livello”;

– compilazione

• traduzione in linguaggio macchina;

– verifica

• esecuzione del programma.

(9)

Esercizi di sviluppo di algoritmi orientati alla programmazione

• Partiamo dall’analisi del problema

• Scriviamo la specifica funzionale

• Introduciamo i contenitori di dati necessari e le relative operazioni elementari

• Scriviamo l’algoritmo che opera su tali dati con un diagramma di flusso

(10)

Esempio 1

(11)

A) Problema e analisi del problema

• L’analisi del problema è il primo passo; deve fornire

– un nome e una breve descrizione di cosa si vuol fare;

– un elenco di requisiti: richieste a cui deve soddisfare il programma

(12)

Esempio di analisi del problema

Problema telefonata

• Descrizione:

– vogliamo chiamare un abbonato con il telefono.

• Requisiti, in cui prevediamo i diversi casi:

– la telefonata viene eseguita con successo

• messaggio “telefonata riuscita”

– la telefonata non può essere portata a termine

• messaggio “telefonata non riuscita”

(13)

B) Specifica funzionale

Una specifica funzionale indica

– quali sono i dati iniziali, cioè quelli da elaborare

• detti anche ingressi all’algoritmo

– che risultato si vuole, in funzione degli ingressi

• detto anche uscita dell’algoritmo

(14)

Esempio: specifica funzionale

• TELEFONATA: specifica funzionale

• Argomenti o ingressi:

– N : numero da comporre

• Risultati o uscite:

– messaggio “telefonata riuscita”

– messaggio “telefonata non riuscita”

(15)

C) I contenitori di dati

• Un algoritmo ha bisogno di tener traccia di ingressi e risultati:

– sia il risultato finale

– sia eventuali risultati intermedi

• Allo scopo, usa dei contenitori di dati

(16)

I contenitori di dati

• I contenitori di dati utilizzati per i risultati intermedi dipendono dall’algoritmo

– quindi, a meno di casi assai elementari, è necessario avere già un’idea dell’algoritmo per determinarli

– difficilmente sono TUTTI prevedibili sin dall’inizio;

man mano che l’algoritmo prende forma, si possono aggiungere al volo nuovi contenitori

(17)

I contenitori utilizzati da TELEFONATA

• Di quali contenitori abbiamo bisogno per TELEFONATA?

– Sicuramente di quello per contenere i dati di ingresso ed il risultato

• 1 contenitore per N (ingresso)

– Eventuali contenitori per i risultati intermedi – Contenitore per il risultato finale

(18)

• Relativamente agli ingressi, abbiamo il contenitore:

• Relativamente all’uscita, abbiamo il contenitore:

N N : int

m

m : string

In blu indichiamo il nome del contenitore, in rosso il numero contenuto in esso

Il tipo int corrisponde ai numeri interi; le operazioni che assumiamo disponibili per esso sono le solite: somma, prodotto, ….

(19)

D) L’algoritmo: primo passo

• Descrivere brevemente l’idea dell’algoritmo

– cioè i passi da eseguire per giungere alla soluzione usando i contenitori di dati e le operazioni disponibili su di essi in base al tipo di dati, a grandi linee

• Può darsi che una prima idea sia già stata raggiunta per trovare i contenitori dati più appropriati

– in tal caso si procede ad un eventuale raffinamento dell’idea

(20)

L’idea dell’algoritmo di soluzione di TELEFONATA

• Sollevo il ricevitore

• analizzo i vari casi di segnale:

– assente – presente

• se posso, procedo componendo il numero

• di nuovo analizzo i vari casi:

• e caso per caso costruisco il messaggio da inviare in uscita.

(21)

L’idea dell’algoritmo di soluzione di TELEFONATA

• Più in dettaglio:

– il telefono non dà segnale quando solleviamo la cornetta, non possiamo procedere e mettiamo giù

– altrimenti possiamo comporre il numero

– se il segnale è occupato o assente, non possiamo procedere e mettiamo giù

– altrimenti, aspettiamo la risposta

– se non arriva entro 10 squilli, mettiamo giù – altrimenti parliamo e poi mettiamo giù

• Passiamo al diagramma di flusso:

(22)

Leggere il numero da comporre.

Sollevare il ricevitore.

inizio

segnale?

Comporre il numero

libero?

risposta?

Messaggio

"Telefonata non riuscita".

no

sì

sì no

no

Diagramma di flusso Contenitori di dati

messaggio

m

N

(23)

risposta?

Parlare.

finito?

Appendere il ricevitore

fine Messaggio

Messaggio "Telefonata riuscita".

sì no

no sì

no

Diagramma di flusso

Contenitori di dati

messaggio

m

N

(24)

inizio

segnale?

Comporre il numero

libero?

risposta?

Messaggio

no

sì

sì no

no

Esecuzione Contenitori di dati

messaggio N

025031

(25)

inizio

segnale?

Comporre il numero

libero?

risposta?

Messaggio

no

sì

sì no

no

messaggio

m

N

025031

(26)

risposta?

Parlare.

finito?

fine Messaggio

sì no

no sì

no

messaggio N

025031

T. non r.

(27)

risposta?

Parlare.

finito?

fine Messaggio

sì no

no sì

no

Esecuzione

messaggio N

025031

T. non r.

(28)

risposta?

Parlare.

finito?

fine Messaggio

sì no

no sì

no

messaggio N

025031

T. non r.

(29)

Esempio 3

(30)

A) Analisi del problema

Problema MAGGIORE

• Descrizione: vogliamo il maggiore tra due numeri interi, x e y.

• Requisiti in cui prevediamo i diversi casi:

– se x - y > 0, il maggiore è x

– se x - y < 0, il maggiore è y

– se x - y = 0, x e y sono uguali

(31)

B) Specifica funzionale

• Una specifica funzionale indica

– quali sono gli argomenti o ingressi

– che risultato si vuole, in funzione degli ingressi

– x : numero intero – y : numero intero

• Il risultato o uscita è

– maggiore = x, se x-y > 0 – maggiore = y, se x-y < 0

(32)

I contenitori utilizzati dal nostro algoritmo

• Di quali contenitori abbiamo bisogno?

• Sicuramente di quelli per contenere i dati di ingresso ed il risultato

– Contenitore del primo numero (ingresso) – Contenitore del secondo numero (ingresso) – Contenitore del risultato (uscita)

• Dei contenitori per i risultati intermedi

– Contenitore della differenza

(33)

Abbiamo bisogno di x, y, dif, maggiore:

a

x maggiore

m b

y

• Sono tutti contenitori di dati;

• i loro contenuti sono di tipo intero e su di essi possiamo applicare le operazioni sugli interi somma, prodotto, ecc.

d

dif

ingressi ris. intermedi ris. finali

Abbiamo bisogno di operazioni (somme, confronti, ...)

(34)

Passiamo all’algoritmo: l’idea

• Leggo gli ingressi e li metto in x e y

• Calcolo la differenza d = x - y e la metto in dif

• Confronto dif con 0

• Se dif > 0, scrivo “max è x” e metto x in maggiore

• Se dif < 0, scrivo “max è y” e metto y in maggiore

• Fine

– a questo punto ho finito e maggiore contiene il risultato finale

(35)

Assegna ad x e y i valori d’ingresso

Metti il valore di x-y in dif

dif < 0 ^falso

vero

Messaggio: ‘max è y’

Metti il valore di y in maggiore

Messaggio: ‘max è x’

Metti il valore di x in maggiore

fine

inizio _x:int _y:int

dif:int

maggiore:int

Diagramma di flusso Contenitori di dati

(36)

Esecuzione a mano

• Valori in ingresso:

x: 10

y: 10

(37)

dif < 0 ^falso

vero

fine

dif:int

maggiore:int

(38)

dif < 0 ^falso

vero

Ingresso: 10, 10

fine

dif:int

maggiore:int

10 10

(39)

dif < 0 ^falso

vero

fine

dif:int

maggiore:int

10 10

0

(40)

dif < 0 ^falso

vero

fine

dif:int

maggiore:int

10 10

0

(41)

dif < 0 ^falso

vero

fine

dif:int

maggiore:int

10 10

0

10

(42)

dif < 0 ^falso

vero

fine

dif:int

maggiore:int

10 10

0

10

(43)

Esempio 4

(44)

A) analisi del problema

Problema prodotto

• Descrizione: vogliamo calcolare il prodotto di due numeri.

• Requisiti in cui prevediamo i diversi casi : dati due numeri x e y, il programma calcolerà il prodotto x _* y, utilizzando

l’addizione

– se y = 0, il prodotto è 0

– se y > 0, il prodotto è x + x + … + x ( y volte)

(45)

B) Specifica funzionale

– quali sono gli argomenti o ingressi

– che risultato si vuole, in funzione degli ingressi

– x : numero intero – y : numero intero

• Il risultato o uscita è

– prodotto = 0, se y = 0

– prodotto = x * y, se y > 0

(46)

I contenitori utilizzati dal nostro algoritmo

• Di quali contenitori abbiamo bisogno?

• Sicuramente di quelli per contenere i dati di ingresso ed il risultato

– Contenitore del primo numero (ingresso)

– Contenitore del secondo numero (ingresso)

– Contenitore del risultato (uscita)

(47)

Abbiamo bisogno di x, y, prodotto:

a

x prodotto

b p

y

• Sono tutti contenitori di dati;

• i loro contenuti sono di tipo intero e su di essi possiamo applicare le operazioni sugli interi somma, confronto, ecc.

ingressi ris. finali

Noi assumeremo di disporre della somma, ma non del prodotto.

(48)

Passiamo all’algoritmo: l’idea

• Leggo gli ingressi e li metto in x e y

• Calcolo la differenza d = x - y e la metto in dif

• Confronto y con 0

• Se y = 0, metto 0 in prodotto e scrivo “il prodotto è 0”

• Se y > 0, calcolo il prodotto con un numero opportuno di addizioni, metto il risultato in prodotto e scrivo “il

prodotto è prodotto ”

• Fine

(49)

L’idea si traduce nel seguente

diagramma di flusso

(50)

(ingressi) Leggi a.

Leggi b.

inizio

Metti il valore di (ris + a) in ris.

b = 0

fine vero

Diagramma di flusso per il prodotto a * b (b > 0)

b

ris a

Metti il valore di (b - 1) in ris.

Metti 0 in ris.

falso

Nota: ‘b’ svolge il ruolo di contatore.

Stampa ris.

(51)

Esempio 5

(52)

Analisi del problema

Problema CONVERSIONE BASE

• Vogliamo un algoritmo che operi la conversione di un numero da una rappresentazione in base B alla

rappresentazione in base 10.

• L’algoritmo sarà programmato in un linguaggio di programmazione.

(53)

Specifica funzionale

· quali sono gli argomenti o ingressi

· che risultato si vuole, in funzione degli ingressi.

· B : base compresa fra 2 e 16

· R : una rappresentazione in base B

• Il risultato o uscita dev’essere un numero N tale che

· N è la rappresentazione in base 10 del numero rappresentato da R nella base B

(54)

Contenitori di dati

• Di quali contenitori avrà bisogno il nostro algoritmo?

• Sicuramente di quelli per contenere i dati di ingresso ed il risultato:

– Contenitore della base (ingresso)

– Contenitore della rappresentazione (ingresso) – Contenitore del risultato (uscita)

(55)

Contenitori di dati

• Se non teniamo conto delle operazioni, abbiamo:

c_mc_m–1...c₁c₀

rappresentazione base

B

risultato

N

N = c_m^. B^m+ c_m–1^. B^m–1 + … + c₁^. B¹ + c₀^. B⁰ Dalla specifica:

Abbiamo bisogno, per i: 0,...n, del numero c_i rappresentato dalla cifra c_i

Abbiamo bisogno di somme, prodotti (e potenze?)

(56)

Contenitori di dati

• Per quanto riguarda rappresentazione, lo consideriamo contenitore di dati;

• il suo contenuto è di tipo array di interi e sugli elementi dell’array possiamo applicare le

operazioni sugli interi somma, prodotto, ecc.

• Per quanto riguarda risultato, il suo contenuto è di tipo intero e su di esso possiamo applicare le

operazioni sugli interi.

(57)

Passiamo all’algoritmo: l’idea

• Parto col contenuto iniziale di risultato = 0

• considero la cifra di rappresentazione più

significativa, c

_m

, ed uso il suo valore per aggiornare risultato

– Esempio: sommo c

_m^.

B

^m

al valore iniziale 0 di

risultato e risultato ora contiene c

_m^.

B

^m

(58)

Passiamo all’algoritmo: l’idea

• Considero la cifra immediatamente successiva, c

_m-1

₀

– a questo punto ho finito e risultato contiene il

risultato finale

(59)

L’idea si traduce nel seguente

diagramma di flusso

(60)

Usa un indice n

inizialmente uguale alla posizione più significativa di rappresentazione Poni il contenuto iniziale di risultato = 0

Tratta la cifra di indice n di rappresentazione, aggiornando il contenuto di risultato

Decrementa l’indice n di 1

fine inizio

COMMENTO:

Quando arrivo qui, risultato contiene il

risultato parziale relativo alla elaborazione delle cifre fra la posizione più significativa ed n+1

Nota: Tratta la cifra di posto n … ancora da dettagliare

indice n: contenitore inventato al volo

NO

SI n < 0

(61)

Un modo possibile di dettagliare “Tratta …”

• Tratta la cifra di indice n di

rappresentazione, aggiornando il contenuto di risultato si realizza come segue

• si somma a risultato il valore della cifra di posto

n della rappresentazione, moltiplicato per la base

B della rappresentazione elevata ad n

(62)

(ingressi)

Metti c_mc_m–1...c₁c₀ in rappresentazione.

Metti B in base.

Metti m in posizione.

Metti 0 in risultato. inizio

Metti il valore di c_posizione. B^posizione + risultato in risultato.

Metti il valore di posizione - 1 in posizione.

posizione < 0

fine

vero falso

Diagramma di flusso

c_mc_m–1...c₁c₀

rappresentazione

risultato

N

base

B

posizione

m

(63)

Esecuzione a mano

• Convertire 1101₂ in base 10

(64)

Metti 1101 in rappresentazione.

Metti 2 in base.

1101

risultato

1101

risultato

13

base

2

posizione

-1