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.
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 :
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.
Quindi necessita un TEST in cui chiediamo quante volte bisogna ripetere lo schema di fig. 8.1
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.
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.
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.
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.
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 ‘ :
Il corrispondente programma in linguaggio C puo’ essere visualizzato al seguente Link :
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)
{
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;
}