Traccia della lezione Lez06: Lucido 2: Le quattro osservazioni finali sembrano delle banalità, ma le ultime tre sono la chiave per la scrittura di cicli corretti. La prima non varrà per i cicli a condizione finale (che vedremo poi). La seconda richiama la necessità di un passo iniziale, che assegni un valore alle variabili che compaiono nella condizione del ciclo. Ci sono sempre variabili nella condizione di un ciclo? Ovviamente sì, perché una condizione costante sarebbe - o sempre falsa (e allora il ciclo sarebbe inutile) - o sempre vera (e allora il ciclo non terminerebbe mai). La terza richiama la necessità che un ciclo termini, e quindi che le variabili che compaiono nella condizione vengano modificate dal corpo del ciclo. La quarta garantisce che dopo il ciclo la condizione diventa falsa. Questo è importante per sapere se il ciclo ha svolto correttamente il suo compito. Lucido 3: Il codice POWER1.C calcola la minima potenza di 2 che sia >= n, definendo un'opportuna funzione. L'idea e': - scorrere una serie di potenze di 2 crescenti - fermarsi appena si trova una potenza di 2 che sia >= n Chiamiamo p la potenza corrente, che fa da risultato parziale, e quindi e' una variabile locale. Si osservi che: - la condizione contiene due variabili, che vengono entrambe inizializzate (n dalla chiamata della funzione, p da un'istruzione apposita) - il corpo modifica il valore di una delle due variabili, e quindi può modificare il valore della condizione Non lo fa a caso, ma conserva la proprietà che p è una potenza di 2! - quando il ciclo termina, la condizione è falsa, cioè p >= n, che è quanto richiesto dal problema. Ma allora al termine del ciclo p è una potenza di 2 ed è >= n. Non abbiamo ancora dimostrato che è la minima potenza di 2 non inferiore a n, ma poco ci manca. Questa è in effetti una traccia di dimostrazione che il codice è corretto, cioè fa quel che deve. Imparare a scrivere codice che risulti automaticamente corretto, sfruttando la struttura del codice stesso, è una dote fondamentale per un buon programmatore. Si noti che è possibile non eseguire il corpo. Questo succede per n <= 1. Si discuta se il codice è corretto per n <= 1 (dipende dalla definizione). Il codice POWER1B.C è identico a POWER1.C, ma in più genera una serie di stampe che illustrano passo per passo l'esecuzione. Siccome il corpo non è più ridotto a una sola istruzione, occorrono le parentesi graffe. Si noti l'uso dell'operatore condizionale. Esercizio: Si scriva un codice POWER2.C, che calcola la massima potenza di 2 che sia < n. Non esistendo una massima potenza, non si può semplicemente ribaltare il metodo, cioè partire dall'alto e dividere per 2 fino alla prima potenza inferiore a n. Soluzioni possibili: - POWER2A.C: ad ogni esecuzione del corpo, si salva la potenza corrente in un'altra variabile, ma solo se < n; il corpo del ciclo conserva la proprietà che q è potenza di 2 e che q < n. - POWER2B.C: si sostituisce la condizione di permanenza con 2*p < n. Il corpo del ciclo conserva la proprietà che p è potenza di 2. Al termine 2*p >= n, ma p < n. - POWER2C.C: la massima potenza < n coincide con la minima potenza >= n, divisa per 2. Si può quindi calcolare quest'ultima con la funzione già realizzata nel codice POWER1.C e ottenere la prima. Questa soluzione è interessante, perché applica un tipico procedimento algoritmico: ricavare la soluzione di un problema da quella di un altro. Che succede per n <= 1? Esercizio: Partendo dal codice SQUARE.C, scrivere un programma SQUARE-WHILE.C che legge un numero intero n da tastiera e stampa nell'ordine i quadrati dei numeri interi da 1 a n. Si notino i vari elementi del blocco iterativo (inizializzazione, condizione, corpo vero e proprio, istruzioni di aggiornamento). Lucido 4: I cicli a condizione finale godono delle stesse proprietà dei cicli a condizione iniziale, salvo la prima: in essi il corpo viene sempre eseguito almeno una volta. Il costrutto termina con ; nonostante non sia un blocco perché in caso contrario il compilatore avrebbe difficoltà a riconoscere questo costrutto da un while, e potrebbe accorpare all'while la prima istruzione seguente. Si noti che la condizione in C è sempre una condizione di permanenza, cioè il corpo viene eseguito finché è vera. In altri linguaggi (Pascal, ad esempio), il ciclo a condizione finale è detto "repeat until" e la condizione che segue l'"until" è una condizione di uscita o terminazione: "ripeti il corpo finché la condizione non diventa vera". In tal caso, il corpo viene eseguito finché la condizione è falsa. Per non confondersi è sufficiente leggere il codice come se fosse scritto in linguaggio naturale. **** QUESTO ESERCIZIO ANDREBBE SVOLTO NEL SECONDO LABORATORIO, MA QUEST'ANNO DEVO FARLO IO IN AULA PERCHE' IL LABORATORIO E' STATO RITARDATO E QUESTO CODICE MI OCCORRE NELLA LEZIONE Lez07 (T05) **** Esercizio: Il codice DIGITS.C stampa il numero di cifre di un numero intero dato: il corpo del ciclo riduce via via le cifre del numero corrente dividendolo per 10 con divisione intera, cioè troncata. Come sappiamo che il codice è corretto? Perché al termine di ogni iterazione il valore corrente di c più il numero corrente di cifre di n è lo stesso. All'inizio c = 0, mentre alla fine n = 0, cioè ha 0 cifre. Quindi: c_iniz + Cifre(n_iniz) = c + Cifre(n) = c_fin + Cifre(n_fin) 0 + Cifre(n_iniz) = c + Cifre(n) = c_fin + 0 cioe' c_fin = Cifre(n_iniz). Usando do...while, il ciclo verrà eseguito sempre almeno una volta, e quindi restituirà sempre un numero di cifre >= 1 (anche se n = 0). Bisogna valutare se questo è ragionevole per l'utente. **** Lucido 5: Essendo i cicli a condizione iniziale meccanicamente trasformabili in cicli a condizione finale, la scelta tra i due dipende solo da quale abbia la forma più chiara ed elegante nel caso specifico. Esercizio: Si trasformi il codice SQUARE.C da "while" a "do...while" (SQUARE-DO.C) Lucido 6: Nel codice di destra, il blocco che precede il costrutto while ha le graffe solo per sottolineare che è identico al corpo del ciclo. Di per sé, le graffe sono inutili. Come esistono i cicli a condizione iniziale e finale, potrebbero esistere cicli a condizione intermedia, con un primo sottoblocco da eseguire almeno una volta, poi una condizione da valutare e, nel caso sia vera, un secondo sottoblocco e di nuovo il primo da eseguire ancora, e così via. Il C non li ammette perché sarebbe difficile fornire un costrutto chiaro per usarli. Inoltre, anche questi cicli si possono facilmente scrivere sotto forma di cicli a condizione iniziale o finale (vedi lucido 5). Esercizio: Si disegni il diagramma di flusso di un ciclo a condizione intermedia, e si traduca in codice C nella forma "while" e nella forma "do ... while". Lucido 9: Osservare che l'equivalenza è nei due sensi, perché, come già detto, i cicli while: - hanno una condizione logica espressione2 - l'espressione2 dipende da variabili che vanno inizializzate prima, e questo può essere fatto in espressione1 - l'espressione2 dipende da variabili che sono modificate dal corpo, e questo può essere fatto in espressione3 Quindi, ogni ciclo "while" può essere scritto in forma di ciclo "for". Linguaggi diversi dal C hanno quasi sempre costrutti for per realizzare i cicli a conteggio, ma di solito non permettono di usarli per realizzare altri tipi di ciclo. Esercizio: Si trasformi meccanicamente il ciclo del codice SQUARE.C da "while" a "for" (SQUARE-FOR.C). Esercizio: Si trasformi meccanicamente il ciclo del codice POWER2B.C da "while" a "for" (POWER2B-FOR.C). Lucido 10: Nei due esercizi precedenti succede una cosa strana: l'intero corpo del ciclo scompare, assorbito nella espressione3 di aggiornamento. Siccome un ciclo deve avere un corpo, si lascia un'istruzione vuota, costituita dal solo ; che in genere viene messo sulla stessa riga del costrutto for. Costrutti del genere possono essere pericolosi se si aggiunge altro codice subito sotto e ci si dimentica del ; finale. In tal caso, infatti, la prima istruzione successiva viene incorporata nel ciclo al posto del corpo. Questo succede anche se si lasciano righe vuote per chiarire che i costrutti sono separati: lo spazio rende solo più facile trovare l'errore. Il codice PRIME.C determina se un numero n è primo o composto. Lo fa provando per ogni divisore potenziale d compreso fra 2 e n-1 se d è un divisore effettivo, cioè se n diviso d ha resto nullo oppure no. Se lo è, esce dal ciclo; altrimenti, continua sino a che d = n. Una volta eseguito il ciclo, come si fa a sapere se n è primo oppure no? Si testa se d < n; infatti, se siamo usciti con d < n, significa che siamo usciti violando l'altra condizione dell'AND logico, e quindi significa che n % d == 0 per un valore di d < n, cioè che n ha un divisore. Lucido 11: In linea di principio, quando si vuole modificare più variabili conviene farlo in istruzioni separate. Questo però è impossibile se la modifica deve avvenire dentro le espressioni 1 e 3 di ciclo for. Lucidi 12-13: Che succede se, in SQUARE3.C, si accoda il calcolo del quadrato all'inizializzazione i = 1? for (i = 1, q = i * i; i <= n; i++) StampaIntero(q); [Risposta: il quadrato è calcolato solo una volta, prima del ciclo, sul valore i = 1] Che succede se, in SQUARE3.C, si premette il calcolo del quadrato all'inizializzazione i = 1? for (q = i * i, i = 1; i <= n; i++) StampaIntero(q) [Risposta: il quadrato è calcolato solo una volta ed è il quadrato di un numero i casuale] Che succede se, in SQUARE3.C, si premette il calcolo del quadrato all'aggiornamento? for (i = 1; i <= n; q = i * i, i++) StampaIntero(q); [Risposta: il quadrato è calcolato dopo la stampa; il primo valore è sbagliato e gli altri sono in ritardo di un passo] Che succede se, in SQUARE3.C, si accoda il calcolo del quadrato all'aggiornamento? for (i = 1; i <= n; i++, q = i * i) StampaIntero(q); [Risposta: il primo valore è sbagliato, ma gli altri sono giusti e sincronizzati (calcolati sul valore corrente di i)] Sarebbe corretto: for (i = 1, q = 1; i <= n; i++, q = i * i) StampaIntero(q); Il codice SQUARE2.C calcola i quadrati senza fare moltiplicazioni. Ricava ciascun quadrato dal precedente, applicando la proprietà algebrica: (i+1)^2 = i^2 + 2*i + 1 Indichiamo con "q" il quadrato di "i" (come prima) e con "di" il doppio di "i": i = 1; q = 1; di = 2; while (i <= n) { StampaIntero(q); i++; q += di + 1; di += 2; } Se volessimo usare un ciclo "for", dovremmo scegliere una variabile (probabilmente "i") di cui conservare inizializzazione e aggiornamento nel costrutto "for" e relegare le altre prima del ciclo o al termine del corpo. q = 1; di = 2; for (i = 1; i <= n; i++) { StampaIntero(q); q += di + 1; di += 2; } Questo fa perdere un po' di vista il fatto che anche "di" e "q" giocano un ruolo nel ciclo. Inoltre, l'istruzione "i++" ora viene eseguita per ultima, mentre prima era terzultima; in questo caso non cambia nulla, ma in altri casi potrebbe (per esempio, si badi bene all'ordine dell'aggiornamento di "q" e "di"). Un'altra via è usare l'operatore virgola: for (i = 1, q = 1, di = 2; i <= n; q += di + 1, di += 2, i++) StampaIntero(q); Un risultato molto compatto, anche se forse un po' troppo oscuro. Lucido 14: Il codice COMMA.C riporta alcuni esempi complessi (da evitare!) sulle operazioni multiple separate dall'operatore virgola. Indicare con le parentesi l'ordine di valutazione per l'espressione: i = 1, j = 2, k = i + j Si noti che l'operatore virgola ha precedenza minima, ma gli operandi vengono comunque valutati separatamente nell'ordine da sinistra a destra. Quindi il + non viene eseguito per primo, ma dopo la valutazione di i = 1 e di j = 2. (i = 1), j = 2, k = i + j (i = 1), (j = 2), k = i + j ((i = 1), (j = 2)), k = i + j ((i = 1), (j = 2)), k = (i + j) ((i = 1), (j = 2)), (k = (i + j)) (((i = 1), (j = 2)), (k = (i + j))) Quindi il valore è: 1 , j = 2, k = i + j e ora i vale 1 (side effect) 1 , 2 , k = i + j e ora j vale 2 (side effect) (1,2) , k = i + j 2 , k = (1 + 2) 2 , (k = 3) e ora k vale 3 (side effect) (2,3) 3 Si noti che nel codice COMMA.C l'espressione è racchiusa fra parentesi prima di assegnarla alla variabile l. Secondo esempio: i = 1; j = 5; L'espressione ++i, i+j vale (++i), (i+j) cioè 2,(i+j) e ora i vale 2 (side effect) 2,(2+5) 2,7 7 Si noti che nel codice COMMA.C l'espressione è racchiusa fra parentesi prima di assegnarla alla variabile k. Esercizio per l'associatività: Indicare il valore dell'espressione e il valore di p al termine: i = 1,2,3; [i vale 1 perchè = prevale su , e quindi assegno 1 a i e poi calcolo il resto] i = (1,2,3); [i vale 3 perchè le parentesi mi fanno calcolare 1 2 e 3 e restituire 3] L'espressione vale 3 in entrambi i casi. Lucido 15: Per eliminare un'istruzione if (condizione) break; occorre interrompere il ciclo quando la condizione è vera, cioè rendere la permanenza nel ciclo più difficile. Quindi si introduce nella condizione di permanenza un AND logico (congiunzione) con la condizione opposta a quella che provoca il break. In questo modo, si continua a eseguire il ciclo solo finché la condizione che provoca il break rimane falsa. Lucido 16: Il costrutto "if" che sostituisce l'istruzione "continue" deve coinvolgere tutta la parte del corpo del ciclo che segue l'istruzione stessa, e deve avere la condizione opposta, dato che quelle istruzioni verranno eseguite, anziché essere ignorate. Un classico rischio dell'istruzione continue è di creare un ciclo infinito, dato che di solito l'aggiornamento delle variabili che compaiono nella condizione del ciclo avviene in fondo al corpo e l'istruzione continue fa tornare l'esecuzione in cima al corpo, probabilmente impedendo l'aggiornamento stesso. Nei cicli for, però, l'espressione3 viene valutata comunque e quindi l'aggiornamento che essa provoca avviene regolarmente. Le istruzioni break e continue sono comode, ma violano la programmazione strutturata, perche' fanno sì che i blocchi iterativi abbiano più punti di uscita: - nel caso di break si tratta di un'uscita verso l'esterno, - nel caso di continue di un'uscita che torna alla valutazione della condizione di permanenza.