Capitolo 2.   La programmazione strutturata

2.1   Le strutture di controllo (fondamentali)

Le istruzioni che compongono un algoritmo sono organizzate in strutture che permettono di avere un controllo sul "percorso" della elaborazione.

Tra di esse ce ne sono tre fondamentali con le quali si può descrivere qualsiasi algoritmo: sequenza, selezione e iterazione.

2.2   Sequenza

È la struttura per la quale le istruzioni vengono eseguite solo nell'ordine in cui sono specificate.

Scambio del contenuto di due variabili A e B (occorre una terza variabile di "appoggio" C):

VAR A,B,C;
INIZIO
ACCETTA (A,B);
C:=A;
A:=B;
B:=C;
COMUNICA (A,B);
FINE.

2.3   Selezione

È una struttura che permette di:

• eseguire certe istruzioni al verificarsi di una certa condizione (selezione ad una via);

• eseguire certe istruzioni al verificarsi di una certa condizione ed altre istruzioni se non si verifica (selezione a due vie).

Nel linguaggio di progetto la struttura di selezione ad una via si indica con:

SE condizione ALLORA  
                INIZIO
                        ...
                        ...
                        ...
                FINE;

e quella a due vie con:

SE condizione ALLORA
                INIZIO
                        ...
                        ...
                        ...     
                FINE 
             ALTRIMENTI
                INIZIO
                        ...
                        ...
                        ...
                FINE;

Soluzione di una equazione di primo grado AX + B = 0; i dati di partenza sono A e B, il risultato da ottenere è X.

VAR A,B,X;
INIZIO
ACCETTA (A,B);
SE A=0 e B=0 ALLORA 
                INIZIO
                COMUNICA ('EQUAZIONE INDETERMINATA')
                FINE;
SE A=0 e B <> ALLORA
                INIZIO
                COMUNICA ('EQUAZIONE IMPOSSIBILE')
                FINE;
SE A <> e B <> ALLORA
                INIZIO
                X:=-B/A;
                COMUNICA (X);
                FINE;   

FINE.

2.4   Iterazione

È una struttura che permette di ripetere una o più operazioni in sequenza per un numero finito di volte.

La ripetizione del gruppo di istruzioni soggette alla iterazione (o ciclo) è soggetta al verificarsi di una certa condizione ed il controllo su di essa può essere in testa alla struttura oppure in coda alla stessa.

Ci sono due tipi di iterazione:

• iterazione per vero (con controllo in testa);

• iterazione per falso (con controllo in coda).

L'iterazione per vero si esprime nel seguente modo nel nostro linguaggio di progetto:

MENTRE condizione ESEGUI
                      INIZIO
                      .....
                      .....         
                      .....
                      FINE;

il gruppo di istruzioni comprese tra INIZIO e FINE viene eseguito fin tanto che la condizione rimane vera; il controllo sulla condizione è in testa. Questo significa che prima viene controllata la condizione e poi, eventualmente, si eseguono le istruzioni del ciclo. Se la condizione è falsa sin dall'inizio, le istruzioni del ciclo non vengono eseguite neanche una volta.

L'iterazione per falso si esprime nel seguente modo nel nostro linguaggio di progetto:

RIPETI
        ......
        ......
        ......
FINCHE' condizione;             

il gruppo di istruzioni comprese tra RIPETI e FINCHE' viene eseguito fin tanto che la condizione rimane falsa; il controllo sulla condizione è in coda. Questo significa che prima vengono eseguite le istruzioni del ciclo e poi viene controllata la condizione. Se la condizione è vera sin dall'inizio, le istruzioni del ciclo vengono comunque eseguite una volta (proprio perché il controllo avviene dopo).

Prima di passare agli esempi introduciamo altri due tipi di variabili particolari (dopo quelle di "appoggio" viste in precedenza):

contatore

si dice contatore una variabile che si usa per contare il numero di volte che si è eseguita una certa iterazione (si inizializza di solito a 0 oppure a 1, secondo come si imposta il ciclo);

accumulatore

si dice accumulatore una variabile che si usa per contenere il risultato di operazioni (somme o prodotti) successive (si imposta a zero se si usa per accumulare somme, a 1 se si accumulano prodotti).

Calcolo del prodotto fra due numeri A e B effettuato sommando A con se stesso "B volte".

VAR A,B,P,C;        {C contatore, P accumulatore}
INIZIO
ACCETTA (A,B);
C:=1;
P:=0;
MENTRE C NON > B ESEGUI
                    INIZIO
                    P:=P+A;
                    C:=C+1;
                    FINE;
COMUNICA (P);
FINE.

Oppure si può fare la stessa elaborazione usando l'iterazione per falso:

VAR A,B,P,C;
INIZIO
ACCETTA (A,B);
C:=1;
P:=0;
RIPETI 
        P:=P+A;
        C:=C+1;
FINCHE' C > B;
COMUNICA (P);
FINE.

Si noti che questa seconda versione dell'algoritmo fornisce un risultato corretto solo se B > 0.

2.5   Diagrammi a blocchi

Come secondo metodo di descrizione degli algoritmi usiamo i diagrammi a blocchi (o grafi a blocchi o flow chart) che sono basati su simboli grafici corrispondenti alle istruzioni da eseguire.

I simboli si chiamano appunto blocchi e si differenziano per la loro forma in base alla funzione che svolgono nella descrizione dell'algoritmo. Sono uniti da archi orientati (cioè linee munite di frecce) che danno la successione delle operazioni da svolgere nell'algoritmo.

Con i diagrammi a blocchi non si ha più la fase di dichiarazione dell'area di lavoro (manca l'equivalente della istruzione VAR del linguaggio di progetto).

Non esiste nessun blocco particolare per indicare le strutture di iterazione; si usano semplicemente dei blocchi di selezione in testa o in coda al gruppo di istruzioni facenti parte del ciclo.

Descriviamo di nuovo l'algoritmo per la soluzione di una equazione di primo grado facendo uso della simbologia dei diagrammi a blocchi:

2.6   Le strutture derivate

Le tre strutture di sequenza, selezione e iterazione sono chiamate fondamentali perché con esse si possono descrivere tutti gli algoritmi; esistono però anche le strutture derivate che sono delle loro estensioni e servono a descrivere in modo più agevole gli algoritmi stessi. Tali strutture derivate sono:

ITERAZIONE CALCOLATA

PER i := num1 FINO num2 ESEGUI
                           INIZIO
                           .....
                           .....
                           FINE

i è una variabile intera, num1 e num2 sono due numeri interi con num2 > num1.

Questa struttura fa si che i venga automaticamente posto uguale a num1 all'inizio del ciclo; le istruzioni all'interno di esso vengono eseguite finché i non supera num2.

Nel diagramma a blocco non c'è un blocco particolare per indicarla e si ricorre quindi ancora al blocco di selezione usato in modo opportuno:

SELEZIONE MULTIPLA

NEL CASO CHE  var SIA

                valore1: ESEGUI .......
                valore2: ESEGUI .......
                .
                .
                ALTRIMENTI ESEGUI .......
FINE

Per questa struttura esiste un apposito blocco nei diagrammi a blocchi:

Le strutture derivate sono appunto "derivate" da quelle fondamentali; l'iterazione calcolata può essere realizzata attraverso una iterazione per vero con l'utilizzo di un contatore, la selezione multipla attraverso una serie di selezioni nidificate.

2.7   La programmazione strutturata

La programmazione strutturata è una tecnica di programmazione cioè di scrittura di programmi (che sono la "traduzione" dei nostri algoritmi in un linguaggio comprensibile ad un elaboratore elettronico) che ha lo scopo di semplificare la scrittura dell'algoritmo. Essa consiste nell'utilizzo, per la realizzazione dell'algoritmo e del programma, delle tre strutture di controllo fondamentali.

In realtà si parlerà di algoritmi o programmi strutturati anche in presenza delle strutture di controllo derivate in quanto esse sono, come si è accennato, ottenibili da quelle fondamentali.

Ogni struttura di controllo può essere immaginata come un blocco con una sola freccia in entrata ed una sola in uscita.

Ogni blocco interno ad una struttura di controllo non è detto che sia semplice (singola istruzione) ma può essere a sua volta una struttura. Approfondiremo meglio questo concetto più avanti parlando di tecniche di risoluzione top-down.

Come esempio consideriamo il problema del calcolo del fattoriale di un numero N > 1 e risolviamolo con tre diversi algoritmi descritti con diagrammi a blocchi:

Questi tre algoritmi sono funzionalmente equivalenti cioè danno gli stessi risultati partendo dagli stessi dati di ingresso (ammesso che N sia maggiore di 1 altrimenti il terzo non funziona). Il primo algoritmo è però da "scartare" perché non è strutturato.

2.7.1   Il teorema di Jacopini-Bohm

Ci si potrebbe chiedere se le tre strutture fondamentali formano un insieme di strutture completo (cioè tramite le quali si possono descrivere tutti gli algoritmi).

A questo proposito c'è il teorema di Jacopini - Bohm del 1966 (che non dimostriamo) che ci assicura questa proprietà in quanto afferma che:

Ogni algoritmo può essere espresso con le sole tre strutture di controllo fondamentali.

È quindi lecito pretendere l'uso della programmazione strutturata per la soluzione dei problemi, tanto più che con essa si hanno i seguenti vantaggi (tra gli altri):

• maggiore facilità di uso di tecniche top-down;

• algoritmi più leggibili;

• maggiore facilità di individuazione degli errori.

A sinistra abbiamo un algoritmo non strutturato (c'è una iterazione che non è né per vero né per falso); a destra lo stesso algoritmo opportunamente trasformato in modo da renderlo strutturato:

Si noti che nell'algoritmo strutturato siamo ricorsi ad una iterazione per vero al cui interno c'è una selezione e ad una variabile (SW) che ha il ruolo di switch (interruttore).

Una variabile di questo tipo viene solitamente "spenta" (valore 0) all'inizio dell'algoritmo, "accesa" (valore 1) al verificarsi di una certa condizione e "testata" in modo da decidere le azioni da intraprendere in base al suo valore.

2.8   Le tecniche Top-Down

Un algoritmo si ottiene come risultato di un procedimento di analisi che è suddiviso in tre fasi:

• definizione del problema con i suoi dati in ingresso ed in uscita;

• individuazione del metodo di soluzione;

• descrizione dell'algoritmo (con il linguaggio di progetto o con il diagramma a blocchi).

• Un possibile metodo di analisi è dato dalle tecniche top-down o delle scomposizioni successive.

Esse si basano appunto su una scomposizione del problema in sottoproblemi che a loro volta possono essere ulteriormente scomposti fino ad arrivare a sottoproblemi molto semplici costituiti solo da operazioni direttamente "eseguibili".

Naturalmente tale tecnica è utile in caso di problemi abbastanza complicati; in caso di problemi semplici già la prima scomposizione può essere direttamente composta da operazioni elementari (come in tutti gli esempi che abbiamo visto fini a questo momento).

Un sottoproblema sarà associato ad un "sottoalgoritmo" o sottoprogramma. Esso sarà individuato da un blocco di questo tipo:

la sua descrizione inizierà con il consueto blocco di inizio al cui interno sarà indicato il nome del sottoprogramma e non la parola INIZIO e finirà con il blocco di fine contenente RITORNO anziché FINE.

Vogliamo calcolare il Massimo comun divisore fra due numeri interi A e B (faremo uso dell'operatore MOD che dà il resto della divisione tra due numeri interi).