Università degli Studi di Brescia Elementi di Informatica ... · Quindi tutti i divisori comuni di...

Docente: Alessandro Saetti ‐ Elementi di informatica e programmazione – Università degli studi di Brescia D.I.M.I ‐ A.A. 2016/2017Dipa

rtim

ento di Ing

egne

ria dell'Informazione

Corsi di Lau

rea di In

g. In

form

atica, In

g. Elettronica e delle Telecom

unicazioni, Ing

. dell'A

utom

azione

Indu

stria

leElem

enti di in

form

atica e prog

rammazione

Elementi di Informatica e Programmazione

Docente: A. SaettiEsercitatori: M. Sechi, A. Lazzaroni

Università degli Studi di Brescia

ESERCITAZIONE

Vers. 06/10/2016

Docente: A.Saetti ‐ Elementi di informatica e programmazione – Esercitatori: M. Sechi, A. Lazzaroni A.A. 2016/2017

2Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire interi fintantoché differenti da 0 e successivamente visualizzare la media dei numeri positivi

Suggerimenti•Devo ripetere più volte l’acquisizione di un dato, l’eventualesomma dell’ultimo intero immesso e l’eventuale incremento di una unità della quantità di numeri immessi Quindi mi serve un ciclo.

•Almeno un dato deve essere acquisito, quindi meglio un ciclo a condizione finale


3Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


ciclo a condizione finale ciclo a condizione iniziale


4Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Per la media:

1) Saper contare i numeri letti

2) Sapere calcolare la somma totale dei numeri letti

3) Saper dividere il valore al punto 2 per il risultato del punto 1

Duello tra Orazi e Curiazi – Roma e Alba Longa


5Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Saper contare i numeri letti

Sapere calcolare la somma totale dei numeri letti


6Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Calcolare la media

Diagramma di flusso dell’algoritmo che calcola la

media


7Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Calcolare il massimo comune divisore tra 2 interiSuggerimenti Per individuare se un candidato divisore i è un effettivo divisore

devo verificare se x mod i == 0 AND y mod i == 0 Questa verifica deve essere effettuata per tutti i candidati divisori

da 1 a MIN, ovvero MIN volte Quando il corpo del ciclo deve essere ripetuto un determinato

numero di volte è facile impostare la condizione di permanenza del ciclo in funzione del numero di iterazioni

In questo caso non c’è convenienza ad utilizzare il ciclo a condizione finale (non c’è alcuna duplicazione di blocchi). Quando non c’è convenienza si preferisce lo schema a blocchi a condizione iniziale per facilità di lettura


8Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


MCD1 X Y


9Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne



10Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Diagramma di flusso dell’algoritmo che calcola

il MCD

E' l'unica soluzione ?


11Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne

ria dell'InformazioneX Y

MCD

1

Versione 2


12Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


MCD

1

Versione 2B


13Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


MCD

1

Versione 2B


14Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


xy

x < y

contatore<=min

sì

no sì

fine

inizio

min x

no

contatore 1

mcd contatore‘MCD =’, mcd

min y

(x mod contatore == 0) AND(y mod contatore == 0)

contatore contatore + 1

sì

no

Ciclo a condizione iniziale

3

1 e 2

3 3

4 e 5

6

10 7 8

911

… e se x e ysono uguali?

Diagramma di flusso dell’algoritmo che calcola il MCD


15Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Calcolare il massimo comune divisore tra 2 interi

Suggerimenti – Algoritmo di EuclideSi basa sulla constatazione che:

Se x = y allora MCD(x,y) = x (oppure y)Se x ≠ y t.c. x>y, allora MCD(x,y) = MCD(x‐y,y)

Infatti k è divisore di x,y↔ k è divisore di x‐y e y:1. Se x > y e k è un divisore comune a x e a y, allora k è anche un

divisore di x‐y. Infatti x = k * d e y = k * r per qualche intero positivo d e r. Quindi: x‐y = k*(d‐r), essendo (d‐r) ancora un intero positivo

2. Allo stesso modo è possibile dimostrare che se k è un divisore comune ad x‐y e a y allora è un divisore anche di x

3. Quindi tutti i divisori comuni di x e y coincidono con i divisori comuni di x‐y e y, dunque anche i massimi comuni divisori fra le due coppie di numeri coincidono.


16Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Diagramma di flusso dell’algoritmo di Euclide che calcola il MCD

xy

x y

x > ynosì

fine

inizio

z y

‘MCD =’, z

x x – y y y – x

sì

no

Ciclo a condizione iniziale


17Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Visualizzare tutti i numeri primi inferiori a 1000

Suggerimento:Devo visualizzare tanti numeri. Quindi la visualizzazione è un’operazione che va ripetuta. Quindi mi serve un ciclo. In particolare devo effettuare la visualizzazione se il candidato numero primo è un effettivo numero primo. Quindi l’eventuale visualizzazione va ripetuta per tutti i candidati numeri primi ovvero da N che va da 2 a 1000, ovvero 999 volte. Quindi meglio un ciclo a condizione iniziale. Le operazioni che devono essere ripetute sono il calcolo della quantità di divisori del candidato numero primo e l’eventuale visualizzazione. Un numero è primo se è divisibile solo per 1 e per sé stesso, quindi se non ha divisori

maggiori di 1 e minori di sé stesso. Posso quindi determinare se un numero è primo conteggiando la quantità di suoi divisori e verificando se tale quantità è pari a 2.

Presentare il conteggio dei divisori tramite uso di un sottoprogramma: K= divisori(N) Per conteggiare i divisori devo incrementare una variabile di conteggio di 1 unità più

volte. Quindi mi serve un ciclo. I candidati divisori sono quelli maggiori di 2 ed inferiori al numero stesso. Quindi

imposto un ciclo che effettua un’interazione per ogni candidato divisore. Se il candidato divisore è effettivamente un divisore incremento il conteggio sui divisori di 1 unità.

Esercizio per casa: Visualizzare i primi 1000 numeri primi


18Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Ciclo FOR da start a endcon step passo


19Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


inizio

No

fine

N = 2

Diagramma di flusso dell’algoritmo che visualizza i numeri primi inferiori a 1000

N <= 1000

Sì

No

N = N + 1

idx = 1div= 0

div= div+ 1

idx = idx + 1

Sì

No

Sì N

idx<= num div == 2

num mod idx == 0

No

Sì


20Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire da tastiera una successione di interi che termina col prima intero pari x. Visualizzare i due numeri primi la cui somma è x

Suggerimento: Per ogni coppia di candidati numeri primi la cui somma è pari a devo calcolare

la quantità di loro divisori. Questa operazione va ripetuta fino alla prima coppia di effettivi numeri primi la cui somma è pari a x. Almeno per una coppia devo calcolare la quantità dei loro divisori, quindi il corpo del ciclo va ripetuto almeno una volta, quindi meglio un ciclo a condizione finale.

Detto a1 il primo addendo e a2 il secondo. Affinché la somma di a1 e di a2 sia pari a x, il secondo addendo a2 deve essere necessariamente uguale ad x‐a1

La condizione di terminazione del ciclo è che entrambi i numeri siano primi, quindi div1 == 0 AND div2 == 0. Negando la condizione ed applicando De Morgan si ottiene la condizione di permanenza.

Esercizio per casa: Visualizzare i tre numeri primi la cui somma è pari ad un intero maggiore di 5 acquisito da tastiera


21Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


L'esercizio prende spunto dalla congettura di Goldbach che è uno dei più vecchi problemi irrisolti nella teoria dei numeri. Essa afferma che qualsiasi numero pari maggiore di 2 può essere scritto come somma di due numeri primi (che possono essere anche uguali).

Dato un numero N tutte le scomposizioni additive tali per cui X=a1+a2 possono essere ottenute ponendo a1=i e a2=X‐i con i che scorre da 2 fino a i ≤ X/2. In realtà tale condizione non ci serve. Poiché per via della congettura tali primi esistono!

N a1+a2N 2+(N‐2)N 3+(N‐3)…N i+(N‐i)…N (N‐3)+3N (N‐2)+2


22Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


x

div1== 0 && div2=0 Si

No fine

inizio

a1= 2

a1 a2

div1 = divisori(a1)div2 = divisori(a2)

a2 = x– a1

x mod 2 == 0

sìno

Diagramma di flusso dell’algoritmo che esprime un numero pari come somma di due numeri primi

a1= a1+ 1

Versione 1


23Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


x

div1 != 0 OR div2 != 0nosì

fine

inizio

a1= 1

a1 a2

div1 = divisori(a1)

div2 = divisori(a2)

a1= a1+ 1a2 = x– a1

x mod 2 == 0

sì

no

Versione 2

Ulteriore diagramma di flusso dell’algoritmo che esprime un numero pari come somma di due numeri primi


24Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire da tastiera una sequenza di interi che termina col primo 0. Successivamente determinare se la sequenza di interi (0 escluso) acquisiti è palindromaSuggerimento: Per determinare se una sequenza è palindroma devo confrontare il primo e l’ultimo

elemento, il secondo ed il penultimo, ecc. Quindi prima di effettuare la verifica sulla simmetria della sequenza devo prima averla completamente acquisita. Quindi mi serve una sequenza di variabili. Chiamiamo questa sequenza X e facciamo riferimento alle variabili che compongono la sequenza con la notazione xi

Utilizziamo 2 variabili i (inizio) ed f (fine) per fare riferimento alla prima e ultima variabile della sequenza da confrontare. Devo confrontare progressivamente variabili verso il centro quindi i deve essere incrementata mentre f deve essere progressivamente decrementata di 1 unità. Queste due operazioni devono essere ripetute per cui mi serve un ciclo. Nel caso in cui la sequenza contiene 1 singolo intero (i è uguale a f) posso concludere subito che la sequenza è palindroma senza alcun incremento o decremento. Per cui il corpo del ciclo può essere eseguito 0 volte. Quindi meglio un ciclo a condizione iniziale.

Devo interrompere l’incremento di i ed il decremento di f anche se xi è differente da xf. Quindi la condizione di permanenza è i < f AND xi == xf.

Al termine del ciclo posso concludere che la sequenza è palindroma nel caso in cui i >= f.

Esercizio per casa: Inizializzare una sequenza di n interi con dati acquisiti da tastiera. Ribaltare la sequenza e visualizzarla ribaltata.


25Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


OKOK

NOT OK


26Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


OKOKOKOK

I>=F


27Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


xn

sì

fine

inizio

“palindroma”

n = 0

xn != 0

no

n = n + 1

i = 1f = n

i < f AND xi == xf

i = i + 1f = f - 1

i >= f

sì

no no

sì

Leggo un

a sequ

enza di valori

che term

ina con zero

Diagramma di flusso dell’algoritmo che determina se una sequenza di interi è palindroma


28Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire da tastiera una sequenza di 100 interi e visualizzare la lunghezza della più lunga sottosequenza di numeri pari.Suggerimento:

Ad esempio con 6 4 3 2 4 2 1 2 1 … ho una sottosequenza di 2 pari, una sottosequenza di 3 pari ed una sottosequenza di 1 pari, per cui la soluzione è 3

Ho bisogno di una variabile l per la memorizzazione della lunghezza della sottosequenza di pari che sto leggendo e una variabile max per la memorizzazione della massima lunghezza.

Leggendo la sequenza dall’inizio alla fine devo incrementare l di 1 unità ogni volta che leggo un numero pari ed azzerarlo ogni volta che leggo un numero dispari

Queste operazioni azzeramento ed incremento vanno ripetute per tutti gli interi della sequenza ovvero 100 volte. Quindi meglio un ciclo a condizione iniziale.


29Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne



30Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Leggo un

a sequ

enza di N

valori

xi

inizio

i = 1

i <= 100no

i = i + 1

i = 1l = 0

max = 0sì

i <= 100

xi mod 2 == 0

l = l + 1l = 0

l > max max = l

i = i + 1

sì

no

sì

sì

no

no

fine

max

Diagramma di flusso dell’algoritmo che determina la lunghezza della più lunga sottosequenza di interi pari


31Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire da tastiera una sequenza X di 100 interi. Acquisire da tastiera una sequenza Y di 100 interi o con meno interi e che termina con 0. Successivamente visualizzare quante volte la sequenza di interi Y è contenuta nella sequenza di interi X.Suggerimenti: Ad esempio supponendo che la sequenza X sia pari a 3 1 1 1 2 … 1 2 e la sequenza Y sia pari a 1 1, la

risposta dovrebbe essere 2 Devo effettuare un conteggio, quindi devo incrementare più volte la variabile cont che utilizzo per il

conteggio, quindi mi serve un ciclo. Il numero di possibili incrementare è pari a 100-n+1 (dove n è la lunghezza della sequenza). Quindi è semplice scrivere la condizione di permanenza in funzione del numero di iterazioni, quindi meglio un ciclo a condizione iniziale.

Utilizzo la variabile i per conteggiare il numero di iterazioni. Alla prima iterazione del ciclo verifico che Y corrisponde con la sottosequenza di X che parte da x_1. Alla seconda iterazione verifico che Y corrisponde con la sottosequenza di X che parte da x_2. Ecc. Quindi i identifica anche i punti di partenza delle sottosequenza di X che verifico corrispondere ad Y.

La condizione per incrementare la variabile cont dipende dal numero j di variabili di Y che combaciano con quelle confrontate di X. Se questo numero j è pari ad n significa che Y corrisponde interamente alla sottosequenza di X confrontata e quindi cont è da incrementare.

Siccome devo effettuare un conteggio mi serve un ciclo. Alla prima iterazione del ciclo interno confronto x_i+0 ed y_1+0, alla seconda x_i+1 ed y_1+1, ecc. Quindi j piò essere usata anche per rappresentare lo scostamento da x_i e da y_1 di modo da confrontare via via coppie di variabili diverse. Nella prima iterazione j vale 0, nella seconda j vale 1, ecc.

Devo terminare l’incremento di j quando j ==n oppure quando x_i+j != y_j+1


32Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


1° step

dove m è la dimensione dell'array X e n dell'array Y


33Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


2° step



34Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


ultimo step



35Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne



36Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


xi

inizio

i = 1

i <= 100no

i = i + 1

sì

yn

n = 1

yn-1 != 0 AND n <= 100 no

n = n + 1

sì

fine

i <= 100 – n + 1

Sì

No

i = i + 1

j = 0

j = j + 1

Sì

No

cont

j < n ANDxi+j == yj+1

j == n

No

Sì

cont = 0i = 1, n = n -1

cont = cont + 1

Leggo la se

quen

za X

Leggo la se

quen

za Y

Quante volte una sotto‐sequenza è contenuta nella sequenza?


37Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisire una sequenza di interi che termina con zero. Successivamente ordinare gli interi della sequenza (zero escluso)Suggerimenti: Devo effettuare più scambi quindi mi serve un ciclo. In una sequenza con n variabili il numero di

eventuali scambi è uguale a n‐1. Quindi è facile scrivere la condizione di permanenza del ciclo in funzione del numero di iterazioni. Quindi meglio un ciclo a condizione iniziale. Utilizzo la variabile i per conteggiare il numero di iterazioni

Nella prima iterazione del ciclo scambio la prima variabile della sequenza con la più piccola delle altre. Nella seconda iterazione scambio la seconda variabile della sequenza con la più piccola delle altre. Quindi utilizzo i per indicare anche la variabile da scambiare. Inizialmente i vale 1 e ad ogni iterazione del ciclo i è incrementato di 1 unità.

Utilizzo min e posmin per identificare il minimo e la posizione del minimo. Durante il corpo del ciclo reimposto eventualmente min e posmin. Alla fine del corpo del ciclo scambio xposmin ed xi.

All’inizio del corpo del ciclo devo inizializzare min. Una possibilità è inizializzare min a infinito ma l’esecutore potrebbe non intendere questo simbolo (nel caso l’esecutore fosse il calcolatore non esisterebbe una codifica per questo simbolo). Una migliore possibilità è inizializzare min con il primo intero della sequenza: perché in una sequenza con un solo valore il minimo valore è il valore stesso.

Per reimpostare min e posmin devo effettuare tanti confronti. Quindi mi serve un ciclo. Il numero di confronti da effettuare sono n‐i‐1. Quindi è semplice scrivere la condizione di permanenza in funzione del numero di iterazioni.

Utilizzo j per contare il numero di iterazioni. Anziché farlo andare da 1 ad n‐i‐1 lo faccio andare da i+1 ad n di modo che ad ogni iterazione j identifichi anche una delle variabili del confronto


38Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Ordinamento per selezione

L'idea di base è quella di suddividere la sequenza X in due sottosequenza Sk={X0, ... Xk} e Dk={Xk+1, ... Xn-1}. Immaginiamo che la sottosequenza a sinistra Sk sia ordinata (questa ipotesi è plausibile se iniziamo col considerare la sottosequenza iniziale S0 che è composta da un solo elemento: { X0}). Per l'altra sequenza D0 non possiamo ipotizzare nulla relativamente all'ordinamento.

Step iniziale: Iniziamo considerando k=0. L'algoritmo seleziona l'elemento minore Xkmin nella sequenza D0 e se questo risulta inferiore con l'unico elemento X0 di S0 lo sposta, mediante uno scambio con X0, nella sottosequenza ordinata S0.

Step k-esimo: Generalizziamo: dovendo ordinare un array X di lunghezza n, si fa scorrere l'indice k da 1 a n-1 ripetendo i seguenti passi: si cerca il più piccolo elemento Xkmin della sottosequenza Dk={Xk+1, ... Xn-1}; se Xkmin risulta minore dell'ultimo elemento Xk di Sk lo si scambia con

l'elemento Xk di Sk.


39Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Un inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dare informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega più o meno lo stesso tempo sia su file già ordinati che su file con tutte le chiavi uguali, o anche su file ordinati in modo casuale.

L'ordinamento per selezione ha un'importante applicazione: poiché ciascun elemento viene spostato al più una volta, questo tipo di ordinamento è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione

La complessità di tale algoritmo è dell'ordine di θ(n2). Infatti il ciclo interno è un semplice test per confrontare l'elemento corrente con l'elemento minimo trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero massimo di scambi è pari a N-1 (dato che l'ultimo elemento non deve essere scambiato).Il selection sort è un algoritmo di ordinamento che opera in place.


40Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne



41Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Calcolo il Min(Di)

X[i]>Min(Di)

Swap(X[i],Min(Di))


42Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


xn

n = 1

xn-1 != 0no

n = n + 1

sì

inizio

No

fine

i = 1

i < n

Sì

No

j= i+1posmin=imin = xi

min = xjposmin = j

j = j+ 1

Sì

No

Sì

j <= n

xj <= min

xposmin = xixi = mini = i +1

Diagramma di flusso dell’algoritmo che

ordina una sequenza di n interi

(Selection Sort)

Leggo un

a sequ

enza di valori

che term

ina con zero

Determino il minimo della sottosequenza Di

Swap tra xi e Min(Di)


43Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


APPROFONDIMENTI


44Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne

ria dell'InformazionePROBLEMA:

«Stabilire se un numero è pari o dispari ?»


45Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


PARI O DISPARI ?Questo è il dilemma!

PARI!

Il problema potrebbe essere schematizzato semplicemente in questo modo:

Determinazione dell'Algoritmo


46Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisisco il dato da analizzare (un numero) e lo tengo a mente.

Valuto, in base alla mia esperienza, se il numero è pari o dispari. Nel flow chart il rombo indica una decisione.

Espongo il risultato (soluzione) della mia analisi

Il seguente diagramma di flusso (flow chart) evidenzia con maggior dettaglio i singoli passaggi: INIZIO

Acquisisco N

E’ pari ?

Espongo la soluzione

FINE

SI NO

Soluzione="Pari" Soluzione="Dispari"

1) INPUT

3) OUTPUT

2) ALGORITMO


47Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


La fase di acquisizione dei dati coincide con l'esplicita richiesta (A)seguita dalla relativa risposta (B). Ottenuto il dato lo memorizzo (C)per utilizzarlo nella fase successiva (algoritmo).

(A) Dammi un numero:

1 – INPUT: ACQUISIZIONE DEI DATI

12

(B) (C)

Acquisisco N


48Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


"E’ PARI ?" è una domanda astratta. Devo trasformarla in una sequenza di istruzioni elementari che io, utente umano, posso svolgere. Tale sequenza rappresenta il corretto «procedimento» da seguire per risolvere il problema. Questa «procedura» risolutiva prende il nome di ALGORITMO. Il risultato (soluzione), ottenuto eseguendo l’algoritmo, deve essere "ricordato" per poi essere impiegato nella fase successiva (output).

E’ pari ?

SI NO

DATO

2 – ALGORITMO: PROCEDIMENRI PER RISOLVERE UN PROBLEMA

Il rombo indica una decisione basata sulla condizione riportata al suo interno.

SI NO

DATO

Soluzione="Dispari"Soluzione="Pari"

E’ divisibile per 2 ? E’ multiplo di 2 ? Il resto della divisione

per 2 è zero ?


49Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


La fase di output coincide con l'esposizione dei risultati.

Signori: il numero è pari!

3 – OUTPUT: ESPOSIZIONE DEI RISULTATI


Soluzione:"Pari"

Soluzione:"Dispari"


50Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


SI

N

NO

3 ‐ OUTPUT

Il flusso delle attività svolte per risolvere il problema "E' pari?" viene riassunto in questa porzione di flow chart :

Soluzione

2 ‐ ALGORITMO:

N è divisibile per 2 ?N è multiplo di 2 ?N Diviso per 2 da resto zero ?

Soluzione="dispari"

Soluzione="pari"


51Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


DISPOSITIVIDI INPUT

DISPOSITIVIDI OUTPUT

PROBLEMA DA RISOLVERE

Generalizzando un algoritmo risolve un problema rispetto a dei dati in ingresso e produce dei risultati in uscita. L'algoritmo viene costruito sulla base della nostra conoscenza/esperienza.

ESPERIENZA + ANALISI

ALGORITMO


52Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Stesura di un programma

DISPOSITIVIDI INPUT

DISPOSITIVIDI OUTPUT

PROBLEMA DA RISOLVERE

La procedura che permette di trasferire un algoritmo all'interno di un calcolatore può essere così schematizzata:

ISTRUZIONI PC + ALGORITMO

PROGRAMMA DA ESEGUIRE


53Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Vediamo ora come trasformare l’algoritmo in un programma:

INIZIO

Acquisisco N

E’ pari ?


FINE

SI NO

Soluzione=«Pari» Soluzione=«Dispari»

PARI O DISPARI ?Questo è l’algoritmo!

PARI O DISPARI ?Questo è il programma!

#include <stdio.h>#include <string.h>int main() {

int n;char soluzione[20];printf("Digita un numero intero : ");scanf("%d", &n);if(n % 2 == 0)

strcpy(soluzione,"pari");else

strcpy(soluzione,"dispari");printf("%d: %s!\n", n, soluzione);

}


54Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


2 ‐ ALGORITMO:Se N … E’ divisibile per 2 ? E’ multiplo di 2 ? Diviso per 2 da resto zero ?

Allora Memorizzo come soluzione …

Altrimenti Memorizzo come soluzione …

Prima di tutto occorre avere a disposizione un set di comandi che il computer sia in grado di comprendere ed eseguire: ad esempio le macro di Excel/Opencalc.

L’algoritmo utilizza «istruzioni umane» elementari (comprensibili ed eseguibili da una persona!) per risolvere un determinato problema. Per creare un programma, che sia comprensibile ed eseguibile sul calcolatore, occorre tradurre le «istruzioni umane» in comandi specifici del computer.

1 ‐ INPUTLeggo, Ascolto, …

3 ‐ OUTPUTScrivo, Dico, …

TRADUCO

1 ‐ INPUTscanf(), cin >>, int N, char Esito[10] …

2 ‐ ALGORITMO: if ( N

Non traducibile Non traducibile % 2== 0) strcpy(Esito, "Pari")

else strcpy(Esito , "Dispari")

3 ‐ OUTPUTprintf(), cout << …


55Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne



La fase di acquisizione dei dati inizia con l’esplicita richiesta …

… seguita dalla digitazione del dato desiderato. Dobbiamo inoltre tradurre l’azione di "ricordare il dato letto" e questo è ottenuto utilizzando come input la cella B3.

B3 11


56Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


C:\Laboratorio>pariDigita un numero intero:

La fase di acquisizione dei dati inizia con l’esplicita richiesta (A) …printf("Digita un numero intero: ");

… seguita dalla lettura del dato digitato (B) scanf("%d", &n);

(B)

(A)

int n;Dobbiamo anche tradurre l’azione di «ricordare» il dato appena letto (C) definendo una variabile che lo contenga:



57Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Dobbiamo trasformare la domanda "E’ pari ?" in una sequenza di istruzioni elementari che possiamo «umanamente eseguire».

2 – PROGRAMMA: TRADUCO L’ALGORITMO CON UN LINGUAGGIO COMPRENSIBILE PER IL PC

E’ pari ?

E’ divisibile per 2 ?

E’ multiplo di 2 ?

Il resto della divisione per 2 è zero ?

Dobbiamo vedere se il programma utilizzato dispone di istruzioni equivalenti a quelle «umanamente eseguibili».

NON ESISTE

NON ESISTE

ESISTE N % 2 == 0


58Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Dobbiamo ora tradurre l’«istruzione umana» che consente di decidere quale sia la soluzione corretta partendo da una condizione

Resto della divisione

per 2 uguale a zero

VERA

FALSA


Dobbiamo anche tradurre l’azione di «ricordare il risultato» ottenuto

2 – PROGRAMMA: TRADUCO L’ALGORITMO CON UN LINGUAGGIO COMPRENSIBILE PER IL PC

ESISTE

ESISTE

#include <string.h>char Esito[10];strcpy(Esito, "Pari");strcpy(Esito, "Dispari");58

if (N % 2 == 0)…

else…


59Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


3 – OUTPUT: ESPOSIZIONE DEI RISULTATI

L’esposizione dei risultati corrisponde alla visualizzazione a video della soluzione.

C:\Laboratorio>pariDigita un numero intero:12

printf("%d: %s!\n", n, Esito);

59

12: pari!

ESISTE

INIZIO

Acquisisco N

E’ pari ?


FINE

SI NO

Soluzione=«Pari» Soluzione=«Dispari»


60Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Acquisisco i dati

Elaboro e valuto …

Espongo il risultato

INIZIO

Acquisisco N

E’ pari ?


FINE

SI NO


1) INPUT

3) OUTPUT

2) ALGORITMO

Possiamo ora stendere il programma in C che implementa il nostro algoritmo.

#include <stdio.h>#include <string.h>int main(){

int n;char risp[20];

Predispongo la sintassi iniziale

printf("Dammi un numero: ");scanf("%d",&n);

if (n % 2 == 0) strcpy(risp,"pari");

elsestrcpy(risp,"dispari");

printf("%d:%s\n",n,risp);

} Predispongo la sintassi finale


61Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Il generico diagramma di flusso per un singolo ciclo

potrebbe essere schematizzato in questo modo

Riassumibile in un blocco unico:INIZIALIZZAZIONE

Inizializzazione


62Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Loop


63Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Per ottimizzare la disposizione dei blocchi su un foglio di carta è consigliabile disporre gli elementi del flow chart seguendo una disposizione spaziale che dia ampio spazio alla «parte iterata» che solitamente risulta essere quella più articolata.


64Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Il generico diagramma di flusso con due

cicli annidati non è altro che un

singolo ciclo dove la sua parte

iterata contiene a sua volta un

singolo ciclo (loop)

Loop interno

Loop esterno


65Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Loop interno

Loop esterno

Loop esterno


66Università

degli stud

i di B

rescia ‐Dipa

rtim

ento di Ing

egne


Per ottimizzare la disposizione dei blocchi su un foglio di carta è consigliabile disporre gli elementi del flow chart seguendo una disposizione spaziale che dia ampio spazio alla «parte iterata» che solitamente risulta essere quella più articolata.

Parte iterata esterna

Università degli Studi di Brescia Elementi di Informatica ... · Quindi tutti i divisori comuni di...

Documents

Transcript of Università degli Studi di Brescia Elementi di Informatica ... · Quindi tutti i divisori comuni di...