Lezione VIII                         FRAMES    NOFRAMES

 

Concetti di programmazione  parte II

 

Nella lezione VII abbiamo visto i due esempi della fig. 7.2 in cui avevamo una ripetizione infinita delle istruzioni; ma se si usa un  test, ( il rombo nei diagrammi di flusso ) puo’ essere specificato quando e quante volte ripetere un insieme di istruzioni.

In sostanza a volte il flusso puo’ essere deviato per ripetere piu’ volte parti del programma.

 

Esempio   8.1

 

Se dobbiamo leggere da Input 10 numeri interi e stampare per ognuno il successivo, come si puo’ impostare l’algoritmo che risolve tale problema ?

 

Vi sono diversi metodi :

 

Metodo risolutivo ingenuo

 

1)     Leggere un numero da Input e memorizzarlo nella variabile NUM1;

2)     Leggere un numero da Input e memorizzarlo nella variabile NUM2;

3)     Leggere un numero da Input e memorizzarlo nella variabile NUM3;

4)     Leggere un numero da Input e memorizzarlo nella variabile NUM4;

5)     Leggere un numero da Input e memorizzarlo nella variabile NUM5;

6)     Leggere un numero da Input e memorizzarlo nella variabile NUM6;

7)     Leggere un numero da Input e memorizzarlo nella variabile NUM7;

8)     Leggere un numero da Input e memorizzarlo nella variabile NUM8;

9)     Leggere un numero da Input e memorizzarlo nella variabile NUM9;

10)  Leggere un numero da Input e memorizzarlo nella variabile NUM10;

 

11)   S1 < ----  NUM1 +1

 /* assegna alla variabile S1 il risultato della somma fra NUM1 e 1*/

12)   S2 < ----  NUM2 +1

13)   S3 < ----  NUM3 +1

14)   S4 < ----  NUM4 +1

15)   S5 < ----  NUM5 +1

16)   S6 < ----  NUM6 +1

17)   S7 < ----  NUM7 +1

18)   S8 < ----  NUM8 +1

19)   S9 < ----  NUM9 +1

20)   S10 < ----  NUM10 +1

21)   STAMPA  S1

22)   STAMPA  S2

23)   STAMPA  S3

24)   STAMPA  S4

25)   STAMPA  S5

26)   STAMPA  S6

27)   STAMPA  S7

28)   STAMPA  S8

29)   STAMPA  S9

30)   STAMPA  S10

 

L’algoritmo e’ corretto ma richiede un numero di istruzioni eccessivo rispetto alla complessità del problema;

pero’ diciamo subito : nessuno ha chiesto che  i 10 numeri venissero memorizzati in 10 locazioni di memoria diverse, per cui non e’ obbligatorio farlo!

Notiamo inoltre che nell’algoritmo vi e’ uno  schema ripetitivo ,  nel senso che i passi

a)    leggere un numero da Input e memorizzarlo nella variabile NUMi

b)    incrementare NUMi di 1 ed assegnarlo alla variabile Si:

      Si < ----- NUMi +1

c)     stampare      Si

sono ripetuti tutti per 10 volte.

 

Ossia lo schema di figura 8.1, in cui NUMi e’ chiamato D ed Si e’ chiamato S, va ripetuto per 10 volte.

 

   Fig.  8.1

  

Quindi necessita un TEST in cui chiediamo quante volte bisogna ripetere lo schema di fig. 8.1

 

Fig.  8.2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ci accorgiamo che per non ripetere lo schema di fig. 8.1, necessita un CONTATORE ossia una variabile che conti il numero di volte che dobbiamo ripetere lo schema di fig. 8.1, cioe’ che conteggi per quante volte le istruzioni contenute in tale schema devono essere ripetute nel programma che stiamo progettando.

Chiamando la variabile CONTATORE  cont ; sicuramente   cont  deve essere <= (minore uguale) a 10;

quindi il test diventa   cont<=10 ? ;

 

questo evita di ripetere per infinite volte le istruzioni della fig. 8.1,  infatti non appena la variabile cont assume il valore 11 il test diventa falso (no) e quindi si percorre il ramo in cui c’e’ STOP.

 

Nella  fig. 8.2 dopo le istruzioni di fig. 8.1 deve esserci una istruzione di incremento di 1
del contatore:   cont < --- cont +1.

 

Fig.  8.3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ma questo non basta, in quanto prima che venga eseguito il test nella variabile cont deve esserci un valore !

Cioe’ manca l’INIZIALIZZAZIONE DEL CONTATORE;  nel nostro caso assegniamo a cont il valore 1,
cont < --- 1 , poiche’ vogliamo ripetere da 1 fino a 10 le istruzioni suddette.

 

Algoritmo

 

1)    cont < --- 1

2)    leggere D

3)    S < --- D+1

4)    stampa S

5)    cont  <---- cont +1

 

le istruzioni da 2) a 5) bisogna ripeterle, fintanto che  cont <=10;

 

programma 8.1 

 

/* quello che e’ contenuto fra queste parentesi non fa parte del programma */

 

#include < stdio.h >  /* direttiva per il preprocessore */

 

int main ( )

{

  int  D, S, cont;

 

  cont  = 1;  /* alla variabile cont viene assegnato il valore 1 */

  while ( cont<=10 )  /* ciclo while */

   {   /* inizio corpo while */

     scanf (“\n %d”,&D);   /* lettura di un intero nella variabile D */

     S = D+1;                    /* assegnazione alla variabile S di (D+1) */

     printf (“\n %d”,S);   /* stampa intero successivo a quello letto */

     cont = cont +1;         /* incremento di 1 del contatore */

   }   /* fine corpo while */

return  0;

}

 

 

Per quanto riguarda il ciclo while,  per ora diciamo che nel programma il suo significato e’ il seguente:
fintanto che  cont e’ minore od uguale a 10  vengono eseguite le istruzioni dentro le parentesi graffe ( corpo del  ciclo ), quando cont  non verifica la condizione di essere <= 10 si esce dal ciclo e si prosegue in sequenza con le altre istruzioni del programma , che in questo caso non ve ne sono.

 

Tecnica del contatore

 

   INIZIALIZZAZIONE  (es. fuori del ciclo while )

   USO NEL TEST        

   MODIFICA NEL BLOCCO ITERATO ( es. corpo della while )

 

 

Blocco di istruzioni

 

E’ un gruppo di istruzioni da eseguire sequenzialmente ( senza deviazioni ).

In C per specificarlo su usano le parentesi graffe : aperta e chiusa.

{

<istruzione1>

<istruzione2>       ( blocco istruzioni )

<istruzione3>

……………

}

 

Se il blocco di istruzioni e’ costituito da una sola istruzione non serve usare le parentesi graffe;

la parentesi graffa aperta del linguaggio C e’ l’analoga del begin del linguaggio Pascal , mentre quella chiusa e’ l’analoga dell’ end;  del Pascal.

 

Esempio 8.2  : test di natura diversa

 

Leggere dei numeri interi da input e stampare i successivi; smettere quando l’ input e’ 50.

 

In questo esempio dobbiamo iterare il blocco di istruzioni della fig. 8.1 fintanto che il numero D, letto da input e’ diverso dal valore 50.

 

 

 

 

 

Fig. 8.4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Il blocco di Fig. 8.1 e’ da iterare fintanto che:  D != 50   “ D diverso da 50 ” ; quando D assume il valore 50 il test diventa falso e si va’ verso STOP (cioe’ si esce dal ciclo ).

Cioe’ nel nostro caso l’ ultimo valore assunto da D che sia diverso da 50, coincide con la condizione di ripetizione del ciclo.

 

Programma 8.2 

 

#include<stdio.h>

 

main ( )

 

{

 int  D , S;

 D = 40;

 while ( D != 50 )

    {

     scanf (“\n %d”,&D);

     S = D + 1; 

     printf (“\n %d”, S ); 

    }

}

 

Osservazione

 

In quest’ultimo programma non sappiamo a priori quante iterazioni vengono eseguite, ossia quante volte il ciclo while viene ripetuto, in quanto cio’ dipende dal numero memorizzato in D che viene letto da input ( in via teorica se in ingresso non inserissimo mai il valore di D uguale  50 non si uscirebbe mai dal ciclo while ed il programma chiederebbe di leggere sempre nuovi dati da Input (tastiera) ).

Nel programma precedente sapevamo a priori dalla condizione  su cont, che il ciclo while veniva ripetuto per sole 10 volte.

 

Nella struttura di iterazione  for  si sa’ a priori quante iterazioni vengono eseguite, mentre nella struttura while il numero di iterazioni dipende dalla condizione logica, nel nostro esempio dalla condizione sul contatore; contatore che nel primo problema era noto, mentre nel secondo problema doveva essere letto da input (quindi non noto a priori ).

 

Ciclo for e ciclo while possono essere utilizzati indifferentemente, potendosi simulare un ciclo while attraverso l'utilizzo del for e viceversa.  Vedi FAQ per maggiori dettagli.

Struttura di iterazione for

 

for ( cont =1; cont < =10; cont++)

 

cont e’ il nome della variabile di controllo; 1 e’ il valore iniziale della variabile di controllo, 10 e’ il valore finale della variabile di controllo e l’espressione cont++  (che coincide con la espressione cont= cont +1)  e’ l’incremento della variabile di controllo.

 

Vediamo come si traduce, l’ esempio 8.2: test di natura diversa in C, usando il costrutto for:

 

programma 8.3   :

 

#include<stdio.h>

 

main ( )

{

 int  D , S ;

   for (cont =1; cont<=10; cont++)

    {

     scanf (“\n %d”, &D);

     S= D+1;

     printf (“\n %d”, S );

    }

 }

 

Esempio 8.3 

 

Calcolare e stampare la somma di una sequenza di 10 numeri dati in Input.

 

Usiamo una locazione N per leggere ciascun numero; dopo ogni lettura “ACCUMULIAMO” in una locazione somma.

 

Algoritmo

 

1)  inizializzazione

2)  leggere N

3)  somma ß somma + N

4)    STAMPARE somma

 

I passi da 2 a 4 dell’ algoritmo vanno ripetuti per 10 volte; usiamo una locazione cont come contatore per cui avremo il seguente diagramma di flusso:

 

Fig.  8.5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

La prima volta che viene eseguita l’istruzione: 

somma ß somma +N , il valore della variabile somma e’ indefinito per cui e’ necessario darle un valore; cioe’ e’ necessario INIZIALIZZARE la variabile ACCUMULATORE somma ;  in questo caso le assegneremo il valore 0 ; per cui nel primo blocco del grafo di flusso contrassegnato con  *  metteremo:  somma ß 0  .

 

Programma 8. 4  :

 

#include < stdio.h >

 

 main ( )

 

 {

   int  cont, somma, N;

   somma = 0 ;

   for (cont=1 ; cont <= 10 ; cont ++)

   {

     scanf (“\n%d”,&N)

     somma = somma + N ;

    }

 printf (“\n %d”, somma);

 }

 

Tecnica dell’ accumulatore

INIT

AGGIUNTA ITERATA

 

 

 

Esempio 8.4 : Calcolo del MCD ( m , n )

 

Torniamo sulle tecniche di scrittura di algoritmi “ notazione discorsiva ” , sul massimo comun divisore fra due numeri m ed n letti da Input .

 

   Primo algoritmo

 

1)    Ricevere in input i valori di m ed n

2)    I ß  insieme dei divisori di m

3)    J ß  insieme dei divisori di n

4)    K ß I Ç J

5)    MCD ß massimo elemento di K

6)    Stampa il MCD

 

   Queste operazioni non sono banali e men che meno direttamente eseguibili.

 

   Secondo algoritmo

 

1)    Ricevere in Input i valori di m ed n

2)    Se m > n esegui m ß m - n altrimenti esegui n ß  n -m

L ‘ operazione 2) va ripetuta  fintanto che m e’ diverso da n

3)    MCD  ß valore in m oppure valore in n

4)    Stampa  MCD

 

Vediamo se funziona !

 

es.  m = 16 , n = 10 con  MCD = 2

 

m	16	6	6	2
n	10	10	4	2

 

Es.   m = 36, n = 14 con  MCD = 2

 

m	36	22	8	8	2	2	2
n	14	14	14	6	6	4	2

 

 

Il diagramma di flusso di questo secondo algoritmo e ‘ :

 

Fig.  8.6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Il corrispondente programma in linguaggio C puo’ essere visualizzato al seguente Link :

 

MCD.c  

 

Ciclo di vita di un programma in C

 

Si parte dalle specifiche del problema, si fa l’ analisi e la sintesi dell’algoritmo risolutivo ed i vari raffinamenti “metodologia top down”.

 

Per ottenere un programma eseguibile prog.exe si passa attraverso determinate fasi:

 

FASE DI EDITING )

si codifica l’ algoritmo risolutivo in linguaggio C, attraverso un programma  per il trattamento di testi “sequenze di caratteri” ( editor : che consente di scrivere il programma sorgente) lo salviamo con il nome  “ prog.c ” ;

FASE DI COMPILAZIONE)

si attiva subito il preprocessing in modo automatico, poi una volta che si e’ creato e modificato il programma sorgente nell’ editor di testi, avviene la compilazione : rivelazione degli errori  e traduzione in programma oggetto (codice in linguaggio macchina) “ prog.obj ”;

prog.c  à  prog.obj

FASE DI LINK ) nel caso in cui la costruzione del programma oggetto richieda l’ unione di piu’ moduli (“file” compilati separatamente ) si  collegano tutti i file oggetto con produzione del programma eseguibile “ prog.exe ” ;

FASE DI LOADING ) prog.exe viene caricato in memoria centrale

FASE DI ESECUZIONE ) lancio del file eseguibile : la CPU esegue una istruzione per volta immagazzinando i nuovi dati ottenuti dall’esecuzione del programma.

 

La compilazione avviene in tre fasi :

a)    analisi lessicale

si verifica se vi sono errori sulle parole chiave del linguaggio e le si corregge eventualmente (es iff si corregge in if )

b)    analisi sintattica

esempio nella istruzione while cont <= 10 printf(“\n%d”, cont); si viene avvisati che mancano le parentesi tonde (cont <=10 )

c)     analisi semantica

si rivelano errori di semantica statica

es. x= 3; ma x non e’ definito ! ( qualsiasi variabile va definita prima dell’ uso )

i= 3.5;     i e’ di tipo intero !

 

Il file prog.obj che viene fuori dalla fase di compilazione e’ praticamente in linguaggio macchina ma non ancora eseguibile, poiche’ gli mancano dei pezzi di codice tipo le operazioni di Input, operazioni di Output, funzioni di libreria che sono da collegare. Di questo si occupa il programma LINKER nella fase di linking.

Es. se abbiamo p1.obj file delle operazioni di Input, p2.obj file delle operazioni di Output, p3.obj file di libreria che contiene la funzione matematica seno, avremo :

(prog.obj + p1.obj + p2.obj + p3.obj ) à prog.exe , dove con + abbiamo indicato l’operazione di collegamento svolta dal LINKER.

 

Il file prog.exe e’ un codice rilocabile; gli indirizzi non sono assoluti ma relativi;

relativi a che cosa ? all’ inizio del codice di indirizzo Inizio.

 

prog.exe
indirizzi	istruzioni
Inizio	Prime istruzioni in LM
	………
	………
	Chiamata p1
	………
	Chiamata p2
	……….
	Chiamata p3
	……….
IND+121	p1
	…….
IND+163	p2
	…..
IND+172	p3
	…..

 

ESECUZIONE  “ RUN ”

 

Caricamento in memoria centrale (MC) da IND=7421=Inizio

prog.exe à MC  il LOADER provvede al caricamento in MC di prog.exe

( PC ) ß 7421

 e via di seguito.

 /* l’indirizzo della prima istruzione da eseguire viene caricato nel program counter */

 

ERRORI LOGICI

 

Se vogliamo calcolare la somma dei primi 100 numeri interi tramite il costrutto while che fa uso della variabile contatore cont : bisogna innanzitutto inizializzare tale variabile ; se la inizializzamo al valore 40 : 

….

cont=40;

while( cont <=100)

{

somma=somma+cont;

 cont = cont+1;

}

….

alla fine nella variabile somma ritroviamo  soltanto la somma di 61 numeri, quelli da 40 fino a 100;

se assegnamo a cont il valore iniziale corretto 1 ed incrementiamo dentro il ciclo cont di 2:

….

cont= 1;

while (cont <= 100 )

{

somma=somma+cont;    

 cont = cont +2;

}

…

commetteremo un’altro errore logico in quanto il ciclo viene ripetuto 50 volte e non 100.

 

Il programma corretto e’:

 

#include<stdio.h>

int main ( )

{

 int cont , somma=0 ;

 cont = 1;

  while ( cont <= 100 )

  {

   somma=somma+cont;

   cont = cont +1;

  }

  printf(“\n %d”,somma) ;

return 0;

}

 

Programmabilita’ di un algoritmo

 

Lo stesso problema puo’ essere sicuramente risolto con diversi algoritmi piu’ o meno adatti ad essere programmabili in C, ma non sempre i problemi sono programmabili.

 

Vediamo un esempio di “ algoritmi diversi ma programmabili ” tradotti in linguaggio C .

 

Stampa la somma dei primi n numeri interi positivi

 

#include<stdio.h>

int main ( )   /* programma SOMMAN1 */

{

 int  i , somma , n ;

 scanf (“\n %d”,&n );

 somma=0;

   for (i=0;  i < n ; i ++)

   {

    somma = somma + i+1 ;

   /* le parentesi graffe si potevano omettere in quanto vi e’ una sola istruzione */

   }

printf (“\n %d”, somma);

return 0;

}

 

Lo stesso problema puo’ essere risolto utilizzando un diverso algoritmo; infatti ricordandoci la formula di Gauss che calcola la somma G dei primi n numeri interi positivi come :

       n

G = å  i    = n * ( n+1 ) / 2

       i = 1

 

avremo il seguente programma risolutivo in C:

 

#include<stdio.h>

int main ( )  /* programma SOMMAN2 */

{

 int  n , Gsomma ;

 scanf (“\n %d”, &n);

 Gsomma = ( n * ( n + 1 ) ) / 2 ;

 printf (“\n %d”, Gsomma ) ; 

return 0;

}