DIAGRAMMI A BLOCCHI TEORIA ED ESERCIZI - UniTrento

1 DIAGRAMMI A DIAGRAMMI A BLOCCHIBLOCCHI1 BLOCCHIBLOCCHITEORIA ED ESERCIZITEORIA ED ESERCIZI1Il linguaggio deidiagrammidiagrammi aa blocchiblocchi un possibileformalismo per la descrizione di algoritmiIl diagramma a BLOCCHI , oflowchartflowchart, una rappresentazionegrafica dell algoritmo2Un diagramma a BLOCCHI descrive il flussoflusso delle operazioni daeseguire per realizzare la trasformazione, definitanell algoritmo, dai dati iniziali ai risultatiOgni istruzione dell algoritmo viene rappresentata all internodi unbloccoblocco elementareelementare, la cui forma grafica determinatadal tipo di istruzioneI BLOCCHI sono collegati tra loro dalineelinee didi flussoflusso, munite difrecce, che indicano il susseguirsi di azioni elementariXXleggi/scrivileggi/scrivibegi nbeginAABlocco iniziale Blocco azione 3 BLOCCHI elementariendendBlocco finale Blocco di scrittura CCscriviscriviXXBlocco di controlloBlocco di lettura/scrittura Blocco azione falsofalsoveroveroUndiagrammadiagramma aa blocchiblocchi un insieme di blocchielementari composto da.

2 A)un blocco inizialeb)unbloccofinale4b)unbloccofinal ec)un numero finito n (n 1) di BLOCCHI di azione e/o diblocchi di lettura/scritturad)un numero finito m (m 0) di BLOCCHI di controlloL insieme dei BLOCCHI elementari che descrivono un algoritmo devesoddisfare le seguenti condizioni:ciascun blocco di azione o di lettura/scrittura ha una sola frecciaentrante ed una sola freccia uscenteciascunbloccodicontrollohaunasola frecciaentranteeduefrecceuscenti5ciascun bloccodicontrollohaunasolafrecciaentrant eeduefrecceuscenticiascuna freccia entra in un blocco oppure si innesta in un altrafrecciaciascun blocco raggiungibileraggiungibile dal blocco inizialeil blocco finale raggiungibileraggiungibile da qualsiasi altro bloccoUn blocco B raggiungibileraggiungibilea partire da un blocco A se esiste unasequenza di BLOCCHI X1,X2.

3 ,Xn, tali che A=X1, B=Xn, e Xi,i=1,..,n 1, Xi connesso con una freccia a Xi+1I programmatori inesperti tendono ad aggrovigliare ilprogramma introducendo numerosi salti privi di regole(spaghettispaghetti programmingprogramming)L analisianalisi strutturatastrutturatafavorisce, viceversa, la descrizione dialgoritmifacilmentedocumentabiliecompr ensibili6algoritmifacilmentedocumentabil iecomprensibiliI BLOCCHI di un diagramma a BLOCCHI strutturato sono collegatisecondo i seguenti schemi di flusso:SchemaSchema didi sequenzasequenza pi schemi di flusso sono eseguitiin sequenzaSchemaSchema didi selezioneselezione un blocco di controllo subordinal esecuzione di due possibili schemi di flusso al verificarsidi una condizioneSchemaSchema didi iterazioneiterazione si itera l esecuzione di un datoschema di flussoOvvero: undiagrammadiagramma aa blocchiblocchi strutturatostrutturato undiagramma a BLOCCHI nel quale gli schemi di flusso sonostrutturatistrutturatiUno schema di flusso strutturato quando soddisfa unadelle seguenti propriet.

4 1).. unoschemaelementareounoschemadisequenza7 1).. unoschemaelementareounoschemadisequenzae ndAbeginS1, S2,.., Snschemidi flusso strutturati2).. uno schema di selezione8 Nel primo caso, lo schema S viene eseguito solo se lacondizione C vera; se C falsa, non viene eseguitaalcuna azioneNel secondo caso, viene eseguito solo uno dei due schemiSvo Sf, in dipendenza del valore di verit della condizione3).. uno schema di iterazione9 Nel primo caso, S pu non venire mai eseguito, se la condizione C subito falsa; nel secondo caso, S viene eseguito almeno unavoltaQuando lo schema S viene eseguito finch la condizione C simantiene vera si parla diiterazioneiterazione perper vero vero.

5 Si ha un iterazioneiterazioneperper falso falsoquando S viene eseguito finch C falsaGli schemi di flusso sonoapertiapertiquando consentono una solaesecuzione di una sequenza di BLOCCHI elementari, sonochiusichiusiquando permettono pi di un esecuzione della sequenza diblocchiGliGli schemi schemi didi sequenzasequenza ee didi selezioneselezione sonosono aperti,aperti, lolo schemaschemadidiiterazioneiterazione chiusochiuso10didiiterazioneiterazione chiusochiusoOgniOgni diagrammadiagramma aa blocchiblocchi nonnon strutturato strutturato trasformabiletrasformabile ininunun diagramma diagramma aa blocchiblocchi strutturatostrutturato equivalenteequivalenteDue DIAGRAMMI a BLOCCHI sonoequivalentiequivalentise, operando suglistessi dati, producono gli stessi risultatiL uso dell analisi strutturata garantisce.

6 Facilit di comprensione e modifica dei DIAGRAMMI a blocchimaggiore uniformit nella descrizione degli stato dimostrato (teorema fondamentale dellaprogrammazione di Bohm Jacopini, 1966) che ogni programmapu essere codificato riferendosi esclusivamente ad unalgoritmostrutturatoequindiattenendosi alletrestrutture11algoritmostrutturatoeq uindiattenendosialletrestrutturefondamen tali:SequenzialeIterativaCondizionaleIl teorema di Bohm Jacopini ha un interesse soprattuttoteorico, in quanto i linguaggi di programmazione tendono adotarsi di pi tipi di istruzioni, non sempre rispettose delteorema, ma utili per la realizzazione di programmi di facilescritturaecomprensione12scritturae comprensioneIl suo valore consiste nella capacit di fornire indicazionigenerali per le attivit di progettazione di nuovi linguaggi e distrategie di programmazioneIn effetti, esso ha contribuito alla critica dell uso sconsideratodelle istruzionigogo totoe alla definizione delle linee guida dellaprogrammazione strutturata.

7 Sviluppate negli anni `70In un diagramma strutturato non apparir mai una istruzionedisalto incondizionatoI tre schemi fondamentali possono essereconcatenaticoncatenati,uno diseguito all altro, onidificatinidificati,uno dentro l altro; non possono innessun caso essere intrecciati o accavallati 13 CorrettoSbagliatoDiagramma a BLOCCHI per laselezione, in un mazzo dichiavi, di quella che apreun un numero dire se positivo o e se il numero fosse nullo? il prodotto tra due numeri positivi usando solo l operazione di E se i numero non fossero solo positivi? E se i numero non fossero solo positivi? il maggiore tra tre di 3 interi dei primi N di N di prodotti con tetto massimo di tra due numeriPROBLEMADati due numeri effettuare il loro prodotto usando solo l operazione prodotto usando solo l operazione a trovare una soluzione al problema descrivendola con DIAGRAMMI di flussoUsando solo l operazione sommaSOLUZIONE:PROBLEMADati 3 numeri stabilire quale sia il valore maggioremaggioreSOLUZIONEP rovate a trovare una soluzione al problema descrivendola con DIAGRAMMI di flusso ProblemaProblema: Calcolare la somma ditre interi consecutivi23 NoteNote.

8 La variabile sommasomma uncontenitore di somme parziali,finch non si ottiene la sommatotale richiestaLa soluzione del problema vieneraggiunta eseguendo azionisimili per un numero opportunodi volteIlciclocicloolooploop uno schema di flusso per descrivere, in modo conciso,situazioni in cui un gruppo di operazioni deve essere ripetuto pi volteLacondizionecondizione didi finefine ciclo ciclovieneverificata ogni volta che siesegue il ciclo; se la condizioneassumevalorevero(falso),le24as sumevalorevero(falso),leistruzioni vengono reiterate,altrimenti si esceesce daldal ciclo cicloLa condizione di fine ciclo pu essere verificata prima o dopol esecuzione dell iterazioneLeistruzioniistruzioni didi inizializzazioneinizializzazioneassegnan o valori iniziali adalcune variabili (almeno a quellache controlla la condizione di fineciclo)Ciclo con controllo in codaCiclo con controllo in codaCiclo con controllo in testaCiclo con controllo in testa ProblemaProblema: Calcolare la somma ditre interi consecutivi25 NoteNote.

9 La fase di inizializzazione riguardala somma e l indice del cicloIl controllo di fine ciclo vieneeffettuato in codaUn ciclo definitodefinitoquando noto a priori quante volte deveessere eseguito; un ciclo definito detto ancheenumerativoenumerativoUncontatoreco ntatore deldel ciclo ciclotiene memoria di quante iterazionisonostateeffettuate;pu essereutilizzatoinduemodi:27sonostateeff ettuate;pu essereutilizzatoinduemodi:incrementoincr emento deldel contatore contatore: il contatore viene inizializzato ad unvalore minimo (ad es. 0 o 1) e incrementato ad ogniesecuzione del ciclo; si esce dal ciclo quando il valore delcontatore eguaglia il numero di iterazioni richiestedecrementodecremento deldel contatore contatore: il contatore viene inizializzato alnumero di iterazioni richiesto e decrementato di uno ad ogniiterazione.

10 Si esce dal ciclo quando il valore del contatoreraggiunge 0 (o 1)Un ciclo indefinitoindefinitoquando non possibile conoscere apriori quante volte verr eseguitoLa condizione di fine ciclo controlla il valore di una o pi variabilimodificatedaistruzionichefannop arte28variabilimodificatedaistruzioniche fannopartedell iterazioneComunque, un ciclo deve essere eseguito un numero finitodi volte, cio si deve sempre verificare la terminazioneterminazionedell esecuzione del ciclo ProblemaProblema: Calcolare la somma dei primi N :Leggo un numero N e sommo tutti i numeridell intervallo [0,N] oppure [N,0] se N negativoAttenzione al segno del risultato ProblemaProblema: Calcolo della mediadi un insieme di numeri; non noto a priori quanti sono inumeridicuideveessere30numeridicuidevee sserecalcolata la media I numeri vengono letti