Dagli algoritmi ai programmi

Testo completo

(1)Calcolo della moltiplicazione Dagli Algoritmi ai Programmi. Calcolo della moltiplicazione fra due numeri naturali x e y utilizzando solo operazioni di somma e sottrazione Scomposizione in sottoproblemi:. Fondamenti di Informatica A. 1. 2. 3. 4. 5. 6. 7. 8. 9.. Ingegneria Gestionale Università degli Studi di Brescia Docente: Prof. Alfonso Gerevini. Leggi un valore dall’esterno e inseriscilo nella variabile x Leggi un valore dall’esterno e inseriscilo nella variabile y z←0 Se y > 0 allora vai al passo 5 altrimenti vai al passo 8 z←z+x y←y–1 Vai al passo 4 Stampa/visualizza la frase “Prodotto = ” seguita dal valore in z Fine. Docente: A. Gerevini. x← y←. 1. z←0. 2 3 4 5 6 7 8 9 10 11 12 13 14. y>0. no. sì z←z+x y←y–1. ‘Prodotto =’, ← z. fine. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 2. Esecuzione passo passo dell’algoritmo. inizio. Diagramma di flusso dell’algoritmo della moltiplicazione. Fondamenti di Informatica A – Università di Brescia. 3. Lettura di un numero e memorizzazione nella variabile x (supponiamo x=8) Lettura di un numero e memorizzazione nella variabile y (supponiamo y=3) Assegna 0 alla variabile z (che conterrà il risultato) Controllo se y > 0 Î è vero z=0+8=8 y=3–1=2 Controllo se y > 0 Î è vero z = 8 + 8 = 16 y=2–1=1 Controllo se y > 0 Î è vero z = 16 + 8 = 24 y=1–1=0 Controllo se y > 0 Î non è vero Stampa/visualizza “Prodotto = 24” Fine. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 4.

(2) inizio. Calcolo di xy. x← y←. Calcolo di xy (con x e y numeri naturali) utilizzando il sottoprogramma ‘moltiplica(a,b)’. Diagramma di flusso dell’algoritmo per il calcolo di xy. Scomposizione in sottoproblemi: 1. 2. 3. 4. 5. 6. 7. 8. 9.. Leggi un valore dall’esterno e inseriscilo nella variabile x Leggi un valore dall’esterno e inseriscilo nella variabile y z←1 Se y > 0 allora vai al passo 5 altrimenti vai al passo 8 z ← moltiplica(z, x) y←y–1 Vai al passo 4 Stampa/visualizza la frase “xy = ” seguita dal valore in z Fine. Fondamenti di Informatica A – Università di Brescia. 2 3 4 5 6 7 8 9. 5. Fondamenti di Informatica A – Università di Brescia. y←y–1. Docente: A. Gerevini. chiamata di un sottoprogramma. Fondamenti di Informatica A – Università di Brescia. 6. Esecuzione passo passo dell’ algoritmo (cont.). Lettura di un numero e memorizzazione nella variabile x (supponiamo x=2) Lettura di un numero e memorizzazione nella variabile y (supponiamo y=4) Assegna 1 alla variabile z (che conterrà il risultato) Controllo se y > 0 Î è vero z = moltiplica(1, 2) = 2 y=4–1=3 Controllo se y > 0 Î è vero z = moltiplica(2, 2) = 4 y=3–1=2 Controllo se y > 0 Î è vero. Docente: A. Gerevini. sì z ← moltiplica(z,x). fine. Esecuzione passo passo dell’algoritmo 1. y>0. no. ‘xy =’, ← z. * il sottoprogramma ‘moltiplica(a,b)’ riceve in ingresso due numeri naturali e ne restituisce il prodotto (può essere ad esempio definito attraverso l’algoritmo precedente) Docente: A. Gerevini. z←1. 10 11 12 13 14 15 16 17. 7. Docente: A. Gerevini. z = moltiplica(4, 2) = 8 y=2–1=1 Controllo se y > 0 Î è vero z = moltiplica(8, 2) = 16 y=1–1=0 Controllo se y > 0 Î non è vero Stampa/visualizza “xy = 16” Fine. Fondamenti di Informatica A – Università di Brescia. 8.

(3) Calcolo del fattoriale. Esercizio. Calcolo del fattoriale del numero N. • Scrivere l’algoritmo e il diagramma di flusso per il seguente problema: dato in ingresso un numero intero N restituire in uscita il fattoriale di questo numero, cioè il valore ottenuto da N x (N-1) x (N2) x … x 1 • Scrivere l’algoritmo controllando che il valore N in ingresso sia corretto (cioè maggiore di zero). N! = N x (N-1) x (N-2) x … x 1 Esempio: 5! = 5 x 4 x 3 x 2 x 1 = 120 Scomposizione in sottoproblemi: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.. Docente: A. Gerevini. 9. Fondamenti di Informatica A – Università di Brescia. Leggi un valore dall’esterno e inseriscilo nella variabile N Se N <= 0 allora vai al passo 8 fattoriale ← 1 Se N > 1 allora vai al passo 5 altrimenti vai al passo 9 fattoriale ← fattoriale x N N←N–1 Vai al passo 4 Stampa/visualizza la frase “Errore nell’inserimento del valore di N” e vai al passo 10 Stampa/visualizza la frase “Fattoriale = ” seguita dal valore in fattoriale Fine. Docente: A. Gerevini. inizio. no 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. N<=0. Diagramma di flusso dell’algoritmo del fattoriale. ‘Errore nell’inserimento…’. fattoriale ← 1. no. N>1. sì fattoriale ← fattoriale * N N←N–1. ‘Fattoriale =’, ← fattoriale. fine Docente: A. Gerevini. 10. Esecuzione passo passo dell’algoritmo. N←. sì. Fondamenti di Informatica A – Università di Brescia. Fondamenti di Informatica A – Università di Brescia. 11. Lettura di un numero e memorizzazione nella variabile N (supponiamo N=4) Controllo se N <= 0 Î non è vero Assegna 1 alla variabile fattoriale (che conterrà il risultato) Controllo se N > 1 Î è vero fattoriale = 1 * 4 = 4 N=4–1=3 Controllo se N > 1 Î è vero fattoriale = 4 * 3 = 12 N=3–1=2 Controllo se N > 1 Î è vero fattoriale = 12 * 2 = 24 N=2–1=1 Controllo se N > 1 Î non è vero Stampa/visualizza “Fattoriale = 24” Fine. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 12.

(4) Perché gli algoritmi non bastano…. Esercizio • Scrivere l’algoritmo e il diagramma di flusso per il seguente problema: l’esecutore deve leggere in ingresso una sequenza di numeri naturali (i.e. interi positivi strettamente maggiori di zero) e calcolarne (per poi stamparli) il massimo, il minimo e la media • La sequenza si interrompe non appena viene introdotto un numero negativo o uguale a zero • Per esempio, data la sequenza 5, 1, 2, 3, 4, -5, il risultato dovrebbe essere: “Il massimo è 5, il minimo è 1, la media è 3” Docente: A. Gerevini. • Un algoritmo descritto con i linguaggi visti è spesso interpretabile in modo ambiguo • Non è utilizzabile da un esecutore automatico • Ad esempio, in quegli algoritmi non si parlava di: – come sono codificati i dati – come avviene l’interazione con operatori umani – problemi legati alle caratteristiche fisiche: ad es. limiti nella dimensione dei numeri rappresentabili 13. Fondamenti di Informatica A – Università di Brescia. Docente: A. Gerevini. Dall’analisi del problema all’esecuzione. Fondamenti di Informatica A – Università di Brescia. 14. Programma. problema. analisi. • Un programma è la descrizione formale di un algoritmo attraverso un linguaggio di programmazione. soluzione (informale). specifica. programazione. • Esempio: il sistema operativo Windows NT è composto da 4,3 milioni di righe di istruzioni che, trascritte su fogli A4, riempirebbero più di 75 mila pagine. programma (alto livello). traduzione. Hw Docente: A. Gerevini. • Scrivere programmi è un compito complesso. algoritmo (sol. formale). Fondamenti di Informatica A – Università di Brescia. programma (ling. macchina) esecuzione 15. • Il calcolatore esegue i programmi passo per passo: se i passi non sono completi o non sono nell’ordine corretto, oppure se ci sono dei conflitti tra i passi, il calcolatore non sarà in grado di portare a termine il suo compito Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 16.

(5) Il lavoro dei programmatori. Linguaggi di programmazione. • I programmatori – – – – –. Scrivono i programmi Verificano l’esecuzione dei programmi (debugging) Correggono eventuali errori Preparano le istruzioni/documentazione per gli utenti finali (manuali) Modificano programmi esistenti per aumentarne l’efficienza o per adattarli a nuove esigenze. • Ora anche utenti “poco esperti di programmazione” vengono messi in grado di scrivere programmi (linguaggi “macro” e di interrogazione sono presenti in molti ambienti applicativi). • I linguaggi di programmazione (di alto livello) sono nati per consentire uno sviluppo “rapido” e “facile” di applicazioni informatiche • Permettono di descrivere l’algoritmo e le componenti più operative (es. visualizzazione dei risultati) in un formalismo che fa uso di un insieme ridotto di termini linguistici (della lingua inglese) • Con tali termini linguistici vengono formate le istruzioni che operano sui dati • Le istruzioni hanno un significato preciso e univoco. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 17. Cos’è in pratica un programma? • Un programma è dunque una sequenza di istruzioni di un linguaggio di programmazione di alto livello (ad es.: Fortran, Cobol, Basic, C, Pascal, Ada, C++, Java, Prolog, Lisp) • Un programma viene poi tradotto in linguaggio macchina per essere eseguito dal calcolatore • Ogni linguaggio di programmazione ha Sintassi + semantica • Confronteremo frammenti di programmi in C e in Basic (si vedranno analogie sintattiche e semantiche fra i due linguaggi) Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 19. Docente: A. Gerevini. 18. Fondamenti di Informatica A – Università di Brescia. Esempio: moltiplicazione tra numeri interi positivi. Inizio Dichiarazione: a,b,w,z sono numeri a← b← w←a z←0 Sì. w>0. z ← z+b w ← w-1. No. ←z fine. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 20.

(6) Dallo pseudo-codice al programma in C Dati a, b interi positivi w, z interi Risoluzione leggi a e b z←0 w←a finchè w > 0 ripeti z←z+b w ← w –1 fine ciclo scrivi z fine Docente: A. Gerevini. identificazione programma. main() /* prodotto in C */ { unsigned int a, b dichiarazione int w, z; variabili scanf(“%d %d”, &a,&b); z = 0; w = a; while (w > 0) controllo { z = z + b; w = w – 1; } printf(“%d”, z); }. corpo del programma. Fondamenti di Informatica A – Università di Brescia. 21. • Ogni variabile ha un tipo • Il tipo identifica le proprietà della variabile e le operazioni che su di essa possono essere compiute • Ogni variabile viene dichiarata prima del suo utilizzo • Dichiarazione del tipo delle variabili • Assegnamento dei valori alle variabili Fondamenti di Informatica A – Università di Brescia. identificazione programma. Dati a, b interi positivi w, z interi Risoluzione leggi a e b z←0 w←a finchè w > 0 ripeti z←z+b w ← w –1 fine ciclo scrivi z fine Docente: A. Gerevini. ‘ prodotto in Basic dim a as integer, b as integer dim w as integer, z as integer input a, b z=0 w=a while w > 0 z=z+b w=w-1 wend print z. dichiarazione variabili. controllo. corpo del programma 22. Fondamenti di Informatica A – Università di Brescia. Dichiarazioni di variabili e assegnamento di valori. Variabili e tipi. Docente: A. Gerevini. Dallo pseudo-codice al programma in Basic. La dichiarazione della variabile ‘z’ di tipo ‘intero’ crea un contenitore per memorizzare un valore intero positivo La dichiarazione associa il nome ‘z’ a tale contenitore L’assegnamento usa il contenitore per memorizzarvi il valore 23. Docente: A. Gerevini. z. z. Fondamenti di Informatica A – Università di Brescia. 0 24.

(7) Istruzioni di ingresso/uscita e istruzioni aritmetico-logiche. Le istruzioni. • Le istruzioni di I/O consentono:. • Il corpo del programma è composto da una sequenza di istruzioni • Nei linguaggi di programmazione si distinguono solitamente 3 tipi di istruzioni:. – – – –. – Istruzioni di ingresso/uscita – Istruzioni aritmetico-logiche – Istruzioni di controllo. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. l’acquisizione (ingresso) di dati dall’esterno la presentazione dei risultati in uscita in linguaggio C: scanf e printf in Basic: input e output. • Le istruzioni aritmetico-logiche consentono – la manipolazione dei dati – la generazione di nuovi risultati – in quasi tutti i linguaggi sono assegnamenti 25. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 26. Esempi di utilizzo delle operazioni logiche. Operazioni logiche. main() { int h, i, j, k; bool b1, b2, b3; … b1 = h > j; /* b1 ← true se h è maggiore di j */ b2 = (h > j) || (j ==k); /* b2 ← true se h è maggiore di j o se j e k hanno lo stesso valore */ b3 = b1 && b2; /* b3 ← true se sia b1 che b2 sono true */ … Notare differenza fra = (per assegnamento) e == per }. • Le operazioni di tipo logico fanno riferimento a variabili o costanti di tipo booleano • Somma e prodotto logici sono indicati rispettivamente con i termini OR e AND • In C: – OR corrisponde a ‘| |’ – AND corrisponde a ‘&&’. confronto (valutazione di uguaglianza fra due valori). Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 27. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 28.

(8) Istruzioni di controllo. Proprietà Booleane • • • • • • • • •. NOT (a OR b) =(NOT a) AND (NOT b) De Morgan NOT (a AND b) = (NOT a) OR (NOT b) De Morgan a AND (b OR c) = (a AND b) OR (a AND c) Distributiva a OR (b AND c) = (a OR b) AND (a OR c) Distributiva NOT (NOT a) = a Doppia negazione a AND b = b AND a Commutativa a OR b = b OR a Commutativa a AND (b AND c) = (a AND b) AND c Associativa a OR (b OR c) = (a OR b) OR c Associativa. Docente: A. Gerevini. 29. Fondamenti di Informatica A – Università di Brescia. • Le istruzioni di controllo consentono di modificare il flusso di esecuzione delle istruzioni all’interno di un programma • L’esecuzione sequenziale viene alterata attraverso le istruzioni di controllo che introducono dei salti • Salto incondizionato: salto ad un certo punto del programma (identificatore) senza alcun controllo • Salto condizionato: il salto è condizionato al verificarsi di una condizione valutata durante l’esecuzione del programma Docente: A. Gerevini. Selezione semplice …. main() /* C */ {…. Fondamenti di Informatica A – Università di Brescia. Esempio di selezione semplice ‘ Basic …. /* selezione semplice */ Sì. if (cond) {…. cond. if cond then …. /*blocco istruzioni */ /* eseguito solo se */ /* cond è true */. No. blocco istruzioni. V B←C*D C←C+1. … } …. …. 30. … end if. A=5. F. main() /* C */ { int A, B, C, D; … if (A = = 5) { B = C * D; C = C + 1; } … }. ‘Basic dim A as integer, B as integer dim C as integer, D as integer … if A = 5 then B=C*D C=C+1 end if. } Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 31. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 32.

(9) Esempio di selezione a 2 vie. Selezione a due vie main() /* C */ {…. .... Sì. blocco 1. if (cond) { … /* blocco 1 */ } else { … /* blocco 2 */ }. blocco 2. … }. ... Docente: A. Gerevini. V if cond then … else … end if …. Fondamenti di Informatica A – Università di Brescia. 33. Si. test 1. blocco 1. Si. No. test 2. No. blocco 2 Si. blocco n. test n. No blocco n+1. B←B-A A←A-1. … Docente: A. Gerevini. … if A > B then A=A-B B=B-1 else B=B-A A=A-1 end if …. Fondamenti di Informatica A – Università di Brescia. .... main() /* C */ {… /* selezione a più vie */ if (test1) { … /* blocco 1 */ } else if (test2) { … /* blocco 2 */ } … else if (testn) { … /* blocco n */ } else { … /* blocco n + 1*/ } ... }. Fondamenti di Informatica A – Università di Brescia. ‘Basic dim A as integer dim B as integer. 34. Selezione a più vie (in Basic) Si. test 1. blocco 1. Si. No. test 2. No. blocco 2 Si. blocco n. .... ... Docente: A. Gerevini. F. A>B. A←A-B B←B-1. Selezione a più vie (in C) .... main() /* C */ { int A, B; … if (A > B) { A = A - B; B = B - 1; } else { B = B - A; A = A - 1; } … }. …. /* selezione a 2 vie */. No. cond. ‘ Basic …. 35. Docente: A. Gerevini. test n. No blocco n+1. ‘ Basic … ‘ selezione a più vie if test1 then … ‘ blocco 1 elseif test2 then … ‘ blocco 2 … elseif testn then … ‘ blocco n else … ‘ blocco n + 1 end if .... Fondamenti di Informatica A – Università di Brescia. 36.

(10) Esempio di ciclo a condizione iniziale. Ciclo a condizione iniziale. F. cond V Blocco istruzioni. Docente: A. Gerevini. main() /* C */ {… /* ciclo a condizione iniziale */. ‘ Basic …. while (cond) { /* blocco istruzioni eseguito quando cond è vero */ } … /* eseguito quando cond è falso */ }. while cond ‘ blocco istruzioni ‘ eseguito quando cond ‘ è vero. Inizio J←0 I←0. I <= 10. I←I+1 J←J+I. 37. blocco istruzioni. Sì. cond No .... ‘Basic main() /* C */ … {… /* ciclo a condizione */ /* finale */ do do ‘ blocco istruzioni { ‘ eseguito almeno /* blocco istruzioni ‘ una volta e finchè eseguito almeno ‘ cond rimane vera una volta e finchè cond rimane vera */ } while (cond) loop while cond … /* eseguito quando cond … ‘eseguito quando cond ‘ è falsa è falsa */ }. ‘ Basic dim I as integer, J as integer J=0 I=0 while I <= 10 I=I+1 J=J+I wend. Esercizio: cosa fa il programma? Quali sono i valori finali di I e J?. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 38. Esempio di ciclo a condizione finale Inizio. Ciclo a condizione finale .... fine. V. wend … ‘ eseguito quando ‘ cond è falso. Fondamenti di Informatica A – Università di Brescia. F. main() /* C */ { int I, J; J = 0; I = 0; while (I <= 10) { I = I + 1; J = J + I; } }. j←1 i ← 10 j←j*i i←i-1. i>0. V. F ←j. main() /* C */ { int i, j; j = 1; i = 10; do { j = j * i; i = i – 1; } while (i > 0) printf(“%d”, j); }. ‘Basic dim I as integer, J as integer j=1 i = 10 do j=j*i i=i-1 loop while i > 0 print j. Esercizio: cosa calcola questo programma? fine. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 39. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 40.

(11) Ciclo For. Esempio di uso del ciclo For. • Si utilizza quando è noto a priori il numero di iterazioni da compiere • Ad esempio:. i, n, s interi Risoluzione. Algoritmo che, preso in ingresso un numero n, calcola la somma dei quadrati dei numeri compresi fra 1 e n. s←0. s←0 i←1. È un ciclo a condizione iniziale. for i=1 to i = n. • In tutti i linguaggi è previsto un costrutto del tipo “for i=1 to n do sequenza istruzioni”… la sintassi precisa ovviamente cambia da linguaggio a linguaggio Fondamenti di Informatica A – Università di Brescia. n← E se n è minore di 1?. leggi n. • Nell’algoritmo avrò un ciclo di n iterazioni (con n noto a priori, cioè prima di entrare nel ciclo). Docente: A. Gerevini. Inizio. Dati. s = s + i*i. V. fine for. s←s+i*i i←i+1. scrivi s 41. i <= n. Docente: A. Gerevini. F ←s fine. Fondamenti di Informatica A – Università di Brescia. 42. Algoritmo di Euclide per il MCD (in C). Ciclo For in C e in Basic Dati i, n, s interi Risoluzione leggi n s←0 for i=1 to i = n s = s + i*i fine for. main() /* C */ { int i, n, s; scanf(“%d”, &n); s = 0; for ( i=1; i<=n; i++ ) { s = s + i*i; } printf(“%d”, s); }. inizio x← y←. ‘Basic no. dim i as integer, n as integer dim s as integer input n s=0 for i=1 to n s = s + i*i next i print s. x≠y. sì sì x←x–y. x>y. no y←y –x. main() /* MCD in C */ { int x, y; scanf(“%d”, &x); scanf(“%d”, &y); while (x != y) { if (x > y) x = x – y; else y = y - x } printf(“%d”, y) }. ‘MCD =’, ← y. scrivi s. fine Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 43. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 44.

(12) Algoritmo di Euclide per il MCD (in Basic). I dati: tipi. inizio x← y←. no. x≠y. sì sì x←x–y. x>y. no y←y –x. ‘MCD in Basic dim x as integer, y as integer input x input y while x <> y if x > y then x = x – y else y = y – x end if wend print y. ‘MCD =’, ← y. • Ogni variabile è caratterizzata da un tipo (oltre che dal nome e dal valore) • Il tipo specifica le operazioni di cui le variabili possono essere oggetto • Tipi predefiniti: numeri (interi, reali, …), caratteri, booleani Î normalmente previsti in tutti i linguaggi di programmazione • Esempi: – tipo int (intero) in C permette di dichiarare variabili di tipo intero – Su variabili di tipo intero saranno applicabili operatori aritmetici (+, *, -, /, …) – Il tipo booleano permette di dichiarare variabili che possono assumere solo i valori ‘vero’ e ‘falso’ (true e false) – Su variabili di tipo booleano possono essere applicate operazioni logiche, ad esempio AND (&& in C) e OR (| | in C). fine Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 45. Altri tipi. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 46. L’ "overloading" degli operatori • Uno stesso operatore (ad esempio ‘+’) può assumere significati diversi a seconda del tipo delle variabili a cui viene applicato. • Previsti solo in alcuni linguaggi • Tipo ‘stringa’ per la memorizzazione di successioni di caratteri alfanumerici: esempio ‘ciao a tutti’. • Si dice che l’operatore viene ‘sovraccaricato’ di significato (operator overloading) • L’operatore ‘+’ applicato. • Tipo ‘data’ per la memorizzazione di date: esempio ‘15/10/1002’. – a variabili numeriche Î ne somma i valori – a variabili di tipo stringa Î ne giustappone i valori: se x contiene ‘ciao ’ e y contiene ‘a tutti’ allora x + y conterrà la stringa ‘ciao a tutti’ – Applicato a una variabile di tipo data e a una numerica Î aggiorna la data. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 47. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 48.

(13) Esempio: somma dei guadagni di 1 anno. Variabili strutturate: i vettori •. Le variabili dichiarate di un tipo predefinito diventano contenitori di singoli valori. •. int x Î significa che la variabile x è un contenitore di un valore intero. •. E se volessimo memorizzare i guadagni di 12 mesi in 12 variabili? Possiamo… a). Dati n=12 intero g[ ] vettore di interi w, z interi positivi Risoluzione w←1 z←0 finchè (w <= n ) ripeti z ← z + g[w] w←w+1 fine ciclo scrivi z. … dichiarare dodici variabili di tipo intero: g1, g2, …, g12. b) … oppure dichiarare un VETTORE (ARRAY) g di 12 posizioni. •. Ogni vettore ha un nome e un tipo e può contenere un numero stabilito n di elementi, ogni elemento è identificato da un indice che varia fra 1 e n. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 49. w = 0; z = 0; while (w < 12) { z = z + g[w]; w = w + 1; } printf (“%d, z);. w=1 z=0 while w <= 12 z = z + g(w) w=w+1 wend print z. Docente: A. Gerevini. 50. Fondamenti di Informatica A – Università di Brescia. Matrice bidimensionale. • Le matrici sono array multidimensionali, cioè i cui elementi sono identificati di più indici contemporaneamente • Ogni indice identifica una dimensione della matrice • Esempio: nella gestione del magazzino di un’azienda si vuole tenere traccia, per ognuno dei suoi 50 prodotti, della disponibilità mensile. Dati relativi al mese j-esimo Dati relativi al prodotto i-esimo. ⇒ Usiamo una matrice d[i,j] dove i è l’indice che identifica l’iesimo prodotto (1..50) e j è l’indice che identifica il mese a cui si riferisce la disponibilità (1..12). Fondamenti di Informatica A – Università di Brescia. ‘ Basic dim g(12) as integer dim w as integer dim z as integer. }. Variabili strutturate: matrici. Docente: A. Gerevini. main() /* C */ { int g[12]; int w, z;. (n=50). 51. Docente: A. Gerevini. d[1,1] d[1,2] d[2,1] d[2,2]. …. d[1,j] d[2,j]. …. d[1,12] d[2,12]. d[i,1] d[i,2]. …. d[i,j]. …. d[i,12]. d[n,1] d[n,2]. …. d[n,j]. …. d[n,12]. Fondamenti di Informatica A – Università di Brescia. 52.

(14) Esempio: inizializzazione della matrice d Inizio i←1 j←1. i <= 50. V j <= 12. V d[i,j] ← 0 j←j+1. Docente: A. Gerevini. F fine. F i←i+1 j←1. main() /* C */ { int i, j; int d[50][12]; i = 0; j = 0; while (i < 50) { while (j < 12) { d[i,j] = 0; j = j + 1; } i = i + 1; j = 0; } }. For anziché While (in C). Ordine di inizializzazione d[0,0] = 0 d[0,1] = 0 d[0,2] = 0 … d[0,11] = 0 d[1,0] = 0 d[1,1] = 0 … d[1,11] = 0 … d[48,11] = 0 d[49,0] = 0 d[49,1] = 0 … d[49,11] = 0. Fondamenti di Informatica A – Università di Brescia. 53. Variabili strutturate: record. main() /* C */ { int i, j; int d[50][12]; i = 0; j = 0; while (i < 50) { while (j < 12) { d[i,j] = 0; j = j + 1; } i = i + 1; j = 0; } } Docente: A. Gerevini. main() /* C */ { int i, j; int d[50][12]; for (i=0; i < 50; i++) for (j=0; j < 12; j++) d[i,j] = 0; }. Esempio: il record “studente”. • Nei vettori e nelle matrici gli elementi devono essere tutti dello stesso tipo. studente. • Si supponga che per ogni elemento si vogliano però memorizzare diversi dati • Ad esempio: per ogni studente si vuole memorizzare numero di matricola, nome, cognome, numero degli esami sostenuti •. Tipi definiti dall’utente: a partire dai tipi di dati disponibili nel linguaggio l’utente può definire altri tipi. • Una variabile avente una certa struttura definita comprende più componenti di diverso tipo • Le strutture sono dette record e i componenti campi Fondamenti di Informatica A – Università di Brescia. matricola = 25891 nome = Mario cognome = Rossi num_esami = 0. definizione del tipo ‘studente’. struct studente /* in C */ { matricola; int char nome[30]; char cognome[30]; num_esami; int }. • Il programmatore può definire delle strutture. Docente: A. Gerevini. 54. Fondamenti di Informatica A – Università di Brescia. 55. Docente: A. Gerevini. definizione del tipo ‘studente’. type studente ‘in Basic matricola as integer nome as string * 30 cognome as string * 30 num_esami as integer end type. Fondamenti di Informatica A – Università di Brescia. 56.

(15) Vettori di record e accesso diretto. Dichiarazione e uso di record C. Dichiarazione. struct studente stud;. Basic. dim stud as studente. Assegnamento stud.matricola = 25891;. stud.matricola = 25891. Modifica stud.num_esami = stud.num_esami + 1;. Docente: A. Gerevini. stud.num_esami = stud.num_esami + 1. Fondamenti di Informatica A – Università di Brescia. 57. I sottoprogrammi. Fondamenti di Informatica A – Università di Brescia. Docente: A. Gerevini. type studente ‘in Basic matricola as integer nome as string * 30 cognome as string * 30 num_esami as integer end type dim s(100) as studente … s(3).num_esami = 0 …. Assegna il valore 0 al numero di esami dello studente di indice 3. Fondamenti di Informatica A – Università di Brescia. 58. Strutturazione in sottoprogrammi. • Soluzione di problemi complessi • Lavoro di più persone in modo coordinato • La struttura dei programmi deve essere il più possibile comprensibile e modulare • Ricordate il concetto di strutturazione in sottoproblemi e di problemi elementari • I sottoprogrammi corrispondono alla soluzione di sottoproblemi • Facilitati comprensione, controllo correttezza, manutenzione Docente: A. Gerevini. struct studente /* in C */ { matricola; int char nome[30]; char cognome[30]; num_esami; int }; Main() { struct studente s[100]; … s[3].num_esami = 0; … }. • Ogni sottoproblema sufficientemente limitato può essere assunto come problema terminale • Per ogni problema terminale esiste un’istruzione del linguaggio che lo risolve • Per ogni sottoproblema si scrive un sottoprogramma • A questo punto è come se il linguaggio si arricchisse di nuove istruzioni… ogni nuova istruzione è la chiamata di un sottoprogramma e quindi corrisponde all’esecuzione di un sottoprogramma (una certa sequenza di istruzioni del linguaggio di programmazione) 59. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 60.

(16) Programmi in C e Basic. Esempio di uso di sottoprogrammi. Dati n intero z razionale fine booleano Risoluzione fine ← false finchè (non fine) ripeti leggi w se (w > 0) z ← media(w) scrivi z altrimenti fine ← true fine condizione fine ciclo fine. • Supponiamo di disporre di una matrice p contenente i valori dei fatturati relativi ai 100 prodotti di un’azienda per ogni mese dell’anno (p ha cioè 100 righe e 12 colonne) • p[i,j] contiene il fatturato del prodotto i nel mese j • Si vuole visualizzare il fatturato mensile medio di ogni prodotto specificato dall’utente attraverso l’inserimento dell’indice relativo al prodotto • Scriviamo il programma supponendo di disporre di un sottoprogramma che calcola la media Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. 61. Docente: A. Gerevini. • Nello pseudo-codice e nel codice Basic, se l’utente inserisce un indice di prodotto <=0 allora l’esecuzione termina, altrimenti viene calcolata la media dei valori della riga individuata dall’indice inserito • Nel caso del C la locazione p[0,0] contiene il fatturato del primo prodotto nel mese di gennaio Îla numerazione degli indici di vettori e matrici inizia dallo zero ÎSe l’utente inserisce un indice (del prodotto) >-1 (cioè 0 o un numero positivo) allora viene fatto il calcolo della media e viene visualizzato il fatturato medio relativo al prodotto altrimenti l’esecuzione termina • In Basic, se il valore di una variabile o di una espressione è diverso da zero, allora il suo valore booleano corrispondente è “vero” (uso diffuso del valore “-1” per indicare il valore “vero”) Fondamenti di Informatica A – Università di Brescia. fine = 0; while (!fine) { scanf(“%d”,&w); if (w > -1) { z = media(w); printf(“%d”,z); } else { fine = 1; } } } ?. ‘ Basic dim w as integer dim z as single dim fine as integer fine = 0 while not fine input w if w > 0 then z = media(w) print z else fine = -1 end if ? wend. Fondamenti di Informatica A – Università di Brescia. 62. La funzione ‘media’. Note sui programmi precedenti. Docente: A. Gerevini. main() /* C */ { int w; float z; bool fine;. 63. Funzione media(w) Dati. float media(int w). i,j interi z razionale p[] matrice di interi Risoluzione. { int i, j; float z; int p[100][12];. i←1e j ←0 finchè (i < 13) ripeti j ← j + (p[w, i]) i ←i + 1 fine ciclo z = j / 12 restituisci z fine funzione Docente: A. Gerevini. i = 0; j = 0; while (i < 12) { j = j + p[w][i]; i = i + 1; } z = j / 12; return (z); }. function media (w as integer) dim i as integer dim j as integer dim z as single dim p(100, 12) as integer i = 1: j = 0 while i <= 12 j = j + p(w, i) i=i+1 wend z = j /12 media = z end function. Fondamenti di Informatica A – Università di Brescia. 64.

(17) Domanda. Un altro esempio di uso di sottoprogrammi. • Che controllo manca nei programmi? …cosa succede se l’utente, come indice di prodotto, inserisse 120? • Nella funzione ‘media’ si va ad accedere alle locazioni p[120,i] con i che varia fra 1 e 12 (o fra 0 e 11 nel caso del C) • In ogni caso tutte queste locazioni sono al di fuori della nostra matrice!. • Uno stesso sottoproblema si può presentare più volte in momenti diversi • Con i sottoprogrammi si riduce il numero delle istruzioni del programma • Invece di ripetere la stessa sequenza di istruzioni più volte si scrive un sottoprogramma e lo si richiama tutte le volte che serve • Esempio: calcolo di z = x2 + y2 • Le stesse funzioni scanf e printf del C che abbiamo visto sono sottoprogrammi disponibili in (una libreria del) C. Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. Calcolo di x2 + y2. Inizio leggi xey w ←x z ←0 V. w> 0. +x z ←z+ w ←w -1. F. V. x2 ←z w ←y z ←0 w> 0. +y z ←z+ w ←w -1. y2 ←z q ←x2+y2. I prodotti x*x e y*y sono ottenuti con somme successive Docente: A. Gerevini. F. scrivi “x2+ y2=q” fine. 65. main() /* q = x2 + y2 */ { int x,y,x2,y2,q,w,z; scanf(“%d %d”,&x,&y); w = x; z = 0; while (w > 0) { z = z + x; w = w – 1; } x2 = z; w = y; z = 0; while (w > 0) { z = z + y; w = w - 1; } y2 = z; q = x2+y2; printf(“%d”,q); }. Fondamenti di Informatica A – Università di Brescia. 67. Docente: A. Gerevini. 66. Fondamenti di Informatica A – Università di Brescia. Funzione quad(a). Calcolo di x2 + y2. Funzione quad (a). Inizio leggi xey. w←a z←0. V z ←z + a w ←w -1. Esercizio Scrivere la funzione quad in C e in Basic. w> 0 F. x2 ←quad(x) y2 ←quad(y) q ← x2 + y2 scrivi “x2+ y2=q”. ritorna z Docente: A. Gerevini. Fondamenti di Informatica A – Università di Brescia. fine 68.

(18)