fondamenti di informatica
parte 5
appunti per la laurea in Ingegneria
Civile, Edile, Ambientale
a.a. 2005-2008
di
anna maria carminelli gregori
[email protected]
Approfondimenti
fond. di informatica1 parte 5
1
Tema del 17.10.2000
Scrivere in C++ un programma,
strutturato in sottoprogrammi, che letti da
tastiera 3 dati numerici, positivi e ciascuno <1
_ ne valuti il minimo e il massimo;
_ se il minimo e’ inferiore a 0.25 proceda a
moltiplicare per 1.1 i dati e a rivalutarne il
minimo e il massimo, ripetendo tali operazioni
fintantoche’ il minimo risulti maggiore o
uguale a 0.25;
(segue)
fond. di informatica1 parte 5
2
Tema ...
_ visualizzi sul video o i dati modificati,
 o la stringa ”Non occorre modificare i valori letti”; e
(memorizzi in una tabella in Memoria
Centrale e) visualizzi sul video i dati originali.
N.B. E' SCONSIGLIATO L' USO DI VARIABILI
GLOBALI.
L’ uso delle tabelle ormai è noto e quindi nell’
ultima domanda va considerata la richiesta di
visualizzazionee di memorizzazione in array.
fond. di informatica1 parte 5
3
Considerazioni e ...
I 3 dati numerici, sono positivi e ciascuno <1:
per memorizzarli occorreranno 3 variabili di tipo
…. Di questi 3 dati si deve valutare il minimo e
il massimo, NON l’ ordinamento !
Per valutare il minimo occorre considerare una
variabile dello stesso tipo dei dati e chiamarla
per esempio min. Per il massimo la variabile
dello stesso tipo sara’ max.
La rivalutazione del minimo implica un
procedimento iterativo che si puo’ realizzare
con una funzione contenente la frase while.
fond. di informatica1 parte 5
4
… svolgimento:
 Il main deve leggere i 3 valori, attivare una funzione che calcoli il
minimo, un’ altra che calcoli il massimo, se il minimo e’ inferiore
a 0.25 deve attivare una funzione che rivaluti minimo e massimo,
e poi c’e la memorizzazione e la visualizzione:
 main()
{/* Inizio Modulo principale*/float a, b, c, min, max, v[3]
/*Parte esecutiva*/ clrscr(); cout <“\n dammi i 3 float: “;
 cin >> a >> b >> c;
 min = minimo(a, b, c);
// passaggio per valore
 max = massimo(a, b, c); // “
“ “
 if(min<0.25){max=rivaluta(&min, &a, &b, &c); // indirizzi !
 visual(a,b,c);} else memovis (a,b,c,v); cin >> " ";
fond. di informatica1 parte 5
 return 0;}
5
… e la funzione minimo ?
Eccola … (e analoga sara’ la funzione massimo:)
float minimo(float x, float y, float z)
{float mi; // si puo’ usare min ?!?
cout<<“\nCon i dati: ”<<x<<“ “<<y<<“ “<<z;
if (x<y && x< z) mi=x;
else if (y<x && y<z) mi=y;
else mi = z;
cout <<“\n il minimo e’:”<< mi; <<endl;
return mi; //la funz. ha in piu’ le visualizzazioni...
fond. di informatica1 parte 5
6
}
Alla funzione rivaluta i parametri
sono passati per indirizzo quindi:
float rivaluta (float *m, float *x1, float *y1,
float *z1) // m, x1, y1, z1 sono puntatori a float: per
lavorare sui valori puntati occorre usare l’ operatore *
{float ma=0;//var. locale usata per restituire il massimo
while (*m < 0.25)
{*x1= unoeun*(*x1); *y1= unoeun*(*y1);
*z1=unoeun*(*z1); *m=minimo(*x1,*y1,*z1);}
 ma=massimo(*x1, *y1, *z1); // *x1,… valori !!!
 return ma;}
fond. di informatica1 parte 5
7
CAPIRE BENE E completare
il programma con le direttive al precompilatore (per
es.
#define unoeun 1.1), ed
i prototipi dei sottoprogrammi, la funzione massimo, la
procedura visual che mancano, le costanti …
farlo girare;
con l’ introduzione delle tabelle realizzare anche la
procedura memovis che memorizza in una tabella (=
vettore v) i dati originali.
Farlo per martedì prossimo! per domani costruire una
matrice mat[5][4] di valori float ottenuti con:
mat[i][j]= (float) i*(j+1)
8
 void scambia(float *a, float *b)
 /* Esegue lo scambio del valore float puntato da a
con il valore puntato da b moltiplicato per w che
tramite un #define vale 2.0 */
 { /* Inizio scambia */
 float com; /* variabile LOCALE di comodo per fare lo
scambio */
com = *a; /* pone il valore numerico puntato da a in
com */
 *a = w*(*b); /* sovrappone il valore numerico
puntato da b moltiplicato per w nel posto di memoria
puntato da a .....! NON DA’ ERRORI!!!*/
 *b = com; /* sovrappone il valore numerico assunto
da com nel posto di memoria puntato da b: scambio
effettuato! */
 } /*Fine scambiafond.
*/di informatica1 parte 5
9
E per emulare la memoria?
prima di fare nuovi discorsi, occorrono precisazioni
sull’ uso di array, sulla sinteticita’ del C e C++, su
errori comuni …. e altro! E’ bene ricordare le 2 versioni
della procedura:
void strcp(char *s, char *t) /* strcp copia la stringa
puntata da t in quella puntata da s */
{ while ((*s=*t)!=‘\0’) /*fintantoche’ il contenuto di t
assegnato alla cella puntata da s e’ diverso da ‘\0’
(=fine stringa) fai*/ { s++; t++}; // + sintetica ?!
while (*s++=*t++); // dove manca != ‘\0’ !!
}
fond. di informatica1 parte 5
10
Frasi sintetiche
Questo tipo di sintesi e’ normale nei programmi
in C o in C++ ed e’ utile conoscerla ed
abituarcisi per poter leggere programmi C e C++
in circolazione;
si tratta di “compattare” alcuni tipi di frasi in una
sola.
Es. lettura e calcolo indicate nel progetto logico
posto in parte 4 diapo 69: fintantoche’ il
carattere letto non è il punto, aggiungi 1 all’
elemento che indica la frequenza del carattere
letto… ma come si scrive in C o C++ sintetic … ?
fond. di informatica1 parte 5
11
Sinteticamente … ?
Non e’ in linea con la sintesi leggere la sequenza di
caratteri in un array di char e poi analizzare il vettore
... Sarebbe comunque corretto farlo se fosse
necessario tenere memoria della sequenza di
caratteri per altri scopi per es. per successive analisi.
In tal caso occorre dimensionare l’ array con il numero
di caratteri +1 per salvare un posto dove posizionare
‘.’. Se invece l’ analisi e’ solo quella indicata allora:
while( (cin >> ch) /* fintantoche’ c’e’ un ch
(carattere) da leggere*/ && ( ch != ‘.’) ) /* e inoltre
questo ch e’ diverso da punto FAI */...
fond. di informatica1 parte 5
12
In definitiva
il significato di queste considerazioni riguarda l’
utilizzo di matrici e/o vettori.
E’ bene usarli quando richiesto e/o esiste la
necessita’ di tenere memoria dei valori
calcolati o letti: se tali condizioni sono false,
allora usare il valore corrente (per es. appena
letto) per i calcoli ad esso relativi e passare ad
altro valore (per es. il successivo).
E poi bisogna essere attenti ad errori ed a
esigenze comuni come indicato nel seguito.
fond. di informatica1 parte 5
13
Funzioni e procedure
“predefinite”
del C, C++, MATLAB, di tutti i liguaggi di
programmazione, sono comode,ma non voglio
presentarvele …troppe.
Perchè?
Può capitare che cambiando compilatore cambino in
qualcosina, non tanto, ma qualcosina può essere
diversa. Così preferisco darvi i concetti logici che
devono essere realizzati ed indicarvi come farlo in
C++.
Comunque qualche funzione é standard, comoda e ve
la indico qui di seguito
fond. di informatica1 parte 5
14
Attenzione al fallimento dell’
input !
In iostream.h del C++ esiste una funzione collegata
al flusso cin ossia cin.fail() che restituisce il valore
true se l’ input fallisce, per es. se si ha:
int x,y;
while(true)
{cin>>x; if ( cin.fail() ) break;
else { y= x;
…. }
Il fallimento dell’ input può avvenire per esempio per
un errore di battitura attribuendo ad x un carattere
fond. di informatica1 parte 5
15
Attenzione alla fine file !
In iostream.h del C++ esiste una funzione
collegata al flusso cin ossia cin.eof() che
restituisce il valore true se si incontra EOF. Nell’
es. precedente si analizzerà la fine file solo
dopo il fallimento dell’ input:
int x,y;
while(true)
{cin>>x; if ( cin.fail() ) {if ( cin.eof()) break ;}
else {x--; …. }
fond. di informatica1 parte 5
16
Attenzione alle condizioni di
confronto!
 Ricordarsi le codifiche Fixed e Floating point(!!!) quando
si devono confrontare i numeri in virgola mobile che
hanno precisione limitata.
 Per es. avendo:
 double r= sqrt(2.0);
 if (r*r == 2.0) cout << “il quadrato di sqrt(2) è 2\n”;
 else {cout<< “il quadrato di sqrt(2) NON è 2, ma “<<
r*r<<endl; }
 La visualizzazione sarà: il quadrato di sqrt(2) NON è 2,
ma 2 !!!?
 Ponendo {cout<< “il quadrato di sqrt(2) NON è 2, ma
“<< setprecision(16)<< r*r<<endl; }
 la visualizzazione sarà: il quadrato di sqrt(2) NON è 2,
ma 2.000000000000004
fond. di informatica1 parte 5
17
Attenzione alle richieste di dati
 Quale può essere la risposta implementativa ad una
richiesta di un valore float <1.0 ? Le seguenti 3 frasi:
{ float val;
cin >> val;
if (val > 1.0) cin >>val; }
sono una soluzione valida? …
NO! PERCHé ripete la lettura solo una volta e invece
deve essere ripetuta fintantochè é errata, quindi:
while (val > 1.0) cin >> val;
fond. di informatica1 parte 5
18
Attenzione ai dimensionamenti
errati come nel project27 che vuole
 ampliare array e produce errore in esecuzione …!
 void riscrivamplia (int t[]) //attivata con: riscrivamplia(tab); (e
tab[MAX])
 { int i; /* Inizio riscrivamplia */

cout<<"\nin riscriviamplia t = vettore tab ampliata";

for( i= 0; i<MAX; i++)

cout<< "\n "<< t[i];

cout<<"\nin riscriviamplia oltre MAX";

for( i= MAX; i<3*MAX; i++)

{cout<< "\nprima "<< t[i];

t[i]=99;

cout<< " dopo "<< t[i];

} /* il compilatore non segnala errori, ma in fase di
esecuzione c'e l' indicazione + Access violation .... e problemi in
chiusura*/
19
 } /* Fine riscrivamplia*/
Break e altro
La frase break si può usare anche in cicli while,
do… while, for: vedere project 20 - 22 di programm4
dove si esce con un break da un ciclo infinito come
qui riportato CON : bool attiva = false;
forever
{
switch (menu(!attiva))
{ case 1: cout <<"\nnumero 1 e ris: ";
 ris = elabora(menu(attiva)); cout <<ris; break;
 case 2: cout <<"\nnumero 2 e ris: ";
 ris = elabor1(menu(attiva)); cout <<ris; break;
 case 99: cout<< " Un numero 99 =>fine forever”; break;
 default: cout <<"\n intero non previsto\n";}//fine switch

if (menu(attiva) == 99) break; // fine forever
}
fond. di informatica1 parte 5
20
… e dove la funzione
int menu(bool); è:
int menu(bool attua)
 { /* Inizio menu che mostra anche come da
una funzione se ne puo' attivare un' altra */

static int c;
// c e' var. locale di menu'

if (attua) leggi(&c); // passaggio per
indirizzo: c da inizializzare

return( c);
// ritorma sempre il
valore letto con attua=TRUE
 } /* Fine menu */
fond. di informatica1 parte 5
21
A proposito della variabile logica da usare
in project22…
riprendiamo qui il
discorso
Ossevare i project 21 e 22. Quando la funzione
menu() viene attivata nella frase switch e’
giusto che richiami la funzione leggi(n) in
quanto n deve dirottare il controllo al caso
ennesimo; invece quando la funzione menu()
viene attivata nelle 2 funzioni di elaborazione
non occorrera’ una nuova lettura purche’ n sia
ancora disponibile. Questo e’ il punto: n e’
ancora disponibile? NO se menu() è richiamata
come in project21 ed al suo interno non si
dichiara: static int n;
22
Significato delle variabili
automatiche e statiche
Meo 1 lez.33
In C e C++ ogni variabile e’ caratterizzata oltre
che dal tipo dalla sua classificazione rispetto
alla sua allocazione in memoria ed alla sua
durata. Le variabili finora trattate sono dette
automatiche perche’ iniziano ad esistere
(sono allocate in memoria) quando la funzione
in cui sono definite e’ attivata e “spariscono” all’
uscita dalla funzione. Non conservano il loro
valore tra una attivazione e l’ altra della
funzione. Per conservarlo devono essere
dichiarate static: senza questo attributo sono
fond. di informatica1 parte 5
23
automatiche.
Static => protezione
Tutte la variabili (locali o globali) definite static
sono create ed inizializzate prima che il main
inizi l’ esecuzione e sono distrutte solo al
termine dell’ esecuzione del main program: la
loro inizializzazione e’ eseguita una sola volta,
se manca sono inizializzate a 0.
Anche una var. globale (o esterna) puo’ essere
dichiarata static: in tal caso diventa visibile e
usabile solo all’ interno delle funzioni definite
nello stesso file sorgente in cui essa e’
definita, ma diventa invisibile ad altri file: è
un tipo di protezione.
fond. di informatica1 parte 5
24
Conclusione per menu()
Per salvare il valore di n letto solo la prima volta
bisogna dichiarare n static (non solo int) e
quindi scrivere menu cosi’ (come in project22):
int menu (bool attiva) /* attiva param. formale
di tipo logico che deve essere True solo al primo
richiamo e False ai richiami successivi in cui si
potrà usare il suo duale senza cambiarlo */
{static int n; // n inizializzata a 0
if (attiva) leggi(&n) /*se attiva = True in n va il
valore digitato che resta immutato fino a nuova
lettura che non si verifica se attiva = False */
return n; }
fond. di informatica1 parte 5
25
Attenzione a leggere e scrivere
matrici
 void leggi(int m[][MAX-5]) /* m è una matrice di MAX
righe e MAX-5 colonne */
 { /* Inizio leggi */

int ic,n;
 cout<<"\n dammi i valori della tabella per righe";
for (n=0; n<MAX; n++)

{

cout<<"\n dammi i MAX-5 valori di riga n="<<
n<<" ";

for (ic=0; ic<MAX-5; ic++)

cin>> m[n][ic];

}// fine lettura riga ennesima

}// fine righe
26
Ancora un esempio sui giochi
sempre più importanti …
Nell’ ultimo convegno su Vita Artificiale e
Computazione Evolutiva é stata presentata da
ricercatori dell’ Un. Urbino, un’ Applicazione di
algoritmi genetici a contesti videoludici dove per
l’implementazione dei giochi evolutivi è stato
sviluppato un package Java.
Come esempio del funzionamento del package è stato
utilizzato lo sviluppo di un semplice gioco evolutivo il
cui protagonista è un topolino che si muove in uno
spazio bidimensionale quadrato (MATRICE!!!) popolato
da un cane (che si muove in modo casuale) e da un
gatto (che si muove nel tentativo di mangiare il topo e
di tenersi alla larga dal cane). Il topolino si muove in
base ad un istinto dettato dal suo “genotipo”
(descrittore del suo “DNA”….) …
27
Senza parlare di genotype
vediamo il gioco delle 3 carte …
 o, per semplicità dei 3 interi positivi.
 Il main attiva una procedura Giocatore che legge 3
lettere, le modifica in interi, li memorizza come static, e
visualizza solo l’ intervallo in cui si trovano (0-500 per
es.);
 il main cerca di indovinare i numeri che non vede: per
farlo apre un ciclo, legge o calcola un intero nell’
intervallo (tra 0 e 500) con un certo criterio, lo
memorizza in un vettore ed attiva di nuovo la procedura
Giocatore passandole l’ intero letto;
 la procedura esegue i confronti e se il numero è uguale
ad uno dei 3, visualizza OKEY ed il numero, altrimenti
visualizza NOT OKEY ed il main deve riprovare con un
altro numero diverso dal precedente fino a scoprire i 3
numeri.
 Sono concessi 3 tentativi: al terzo tentativo sbagliato
28 il
main perde.
Volendo complicare il gioco dalla scoperta
dei 3 numeri a quella delle 3 carte,
 sarebbero stati necessari 2 vettori cards e namecards con:
 _ inizializzazione del vettore cards con 54 interi, da 1 a 54,
corrispondenti alle carte da gioco secondo la seguente
corrispondenza: 1 corrisponde all' Asso di Picche, 2 al Due di
Picche,.... 10 al 10 di Picche, 11 al Fante di Picche, 12 alla Donna di
Picche, 13 al Re di Picche, 14 all' Asso di Cuori, etc. etc. fino al 52
che corrisponde al Re di Fiori, mentre 53 e 54 corrispondono ai 2
jolly. La corrispondenza e' effettuata ponendo nel vettore namecards
54 stringhe di caratteri con i nomi suddetti;
 _ attivazione della procedura estrai che estrae una carta a caso: per
far ciò, occorre utilizzare la funzione int random(num) -Random
number generator- e usare il valore da essa restituito, che é un
numero casuale compreso tra 0 e num-1.
 In particolare per utilizzare la funzione random(num) in un
programma in C occorre premettere le seguenti frasi:
 #include <time.h> e #include <stdlib.h> .............
 e poi in estrai:
 randomize(); /* inizializza il generatore di numeri casuali
29
ed usare int indice_casuale= random (55); */ )
E…per tornare al problema del
SORT
Si riprende il project26 che ordina un vettore
di interi con l’algoritmo di selezione o scelta
diretta con il quale l‘ ordinamento di una tabella
di n elementi si ottiene in n-1 passi come
indicato nella diapo seguente.

fond. di informatica1 parte 5
30
SORT & Algoritmo di Scelta diretta.
Con questo metodo l'ordinamento di una tabella di N elementi
si ottiene in N-1 passi.
• Al passo 1 si ricerca il minimo tra gli N elementi con N
confronti (il CONFRONTO è l’ operazione dominante!) e
trovatolo si scambia (di posto) col primo elemento;
• al passo 2 si ricerca il minimo tra gli N-1 elementi (dal
secondo all'ennesimo con N-1 confronti ) e trovatolo si
scambia (di posto) col secondo elemento ;
• cosi' di seguito fino al passo N-1 quando si potranno
scambiare di posto l' elemento N-1 con l'elemento N.
•Ad ogni passo #confronti  N
•#passi  N
#operazioni effettuate dall'algoritmo è dell'
ordine di N*N ... fond.
QUINDI
di informatica1 da
parte 5usare se N <10.
31
void ordina(int x[], int n) /* x è “orlata” cioè l’
elemento x[0] è trascurato. Effettua l' ordinamento di
x (tabella di n elementi) con Alg. Scelta Diretta.
Variabili locali usate: i,j,k,min
Parametri in ingresso: n,x; per es. n=3, x[1] =3,
x[2] = 4 x[3] =1
Parametri che escono definiti: x; x[1] =1, x[2] = 3,
x[3] = 4 */
{ int i,j; /* var. di controllo cicli */ int k; /* indice
del minimo */
int min; /* var. contenente il minimo */
/* Inizio parte esecutiva di ordina */
32
for (i = 1; i <= n-1; i++)
 { min = x[i]; k = i; // se i=1 allora min = 3 e k =1

for (j = i+1; j <= n; j++) //ciclo ricerca minimo

{ if (x[j] < min) /* solo per j=3 questa
condizione è vera (1<3) */

{ k= j; min = x[j]; /*per i=1 si ha: k=3 e

min= 1 se i=2  k=3 e min= 3*/ }

}// fine del for su j

x[k] = x[i]; /* per i=1 scambio tra x[3] e
x[1] ottenendo 1, 4, 3 e tra x[3] e x[2] ottenendo 1,
3, 4 per i=2 */

x[i] = min; /* per ricerche del min. senza
successo queste due frasi non hanno effetto */

} //fine del for su i
}/* fine di ordina */
fond. di informatica1 parte 5
33
E… vedere +oltre
 …cercare altri algoritmi di SORT per esempio da pag. 503 del
testo di Franco Crivellari: “Elementi di programmazione con il
C++”, Franco Angeli; (primo riferimento in Bibliografia) dove
sono descritti
 METODI (Algoritmi) DI ORDINAMENTO come:
 1) selezione (per minimi successivi)
 complessita’ = O(n2)
 2) scambi (bubble sort)
 complessita’ = O(n2)
 3) inserzione
 complessita’ = O(n2)
 4) ad albero: doppio indice (quicksort) complessita’ =

heap-sort
O(n log(n))
 5) distribuzione e fusione o MergeSort
 Per la Complessità diapo seguente
fond. di informatica1 parte 5
34
La complessità computazionale
di un ALGORITMO A ne indica il COSTO come numero
di operazioni eseguite per arrivare al risultato
desiderato: fornisce una misura del “running time” t
del Programma realizzato con A;
il COSTO é funzione del tipo di elaborazione (
scansione lineare ? doppio ciclo o ciclo al quadrato ? è
una funzione logaritmica ?…), e del tipo e dimensione
n dei dati di ingresso: COSTO= f(n).
Interessa soprattutto il Costo per n ELEVATO 
COSTO ASINTOTICO  lim f(n)
n 
e NEL CASO PEGGIORE (meno spesso nei casi migliore e
medio!)
 Quindi il Costo si indica con la notazione O(f(n))

fond. di informatica1 parte 5
35
NO Saltare 3 diapo Altro metodo di ORDINAMEN.
CON DOPPIO INDICE (quicksort) se N 10
1) algoritmo di separazione: scelto nell’ array un
elemento X come perno (o elemento di separazione), si
effettuano spostamenti nell’ array in modo da ripartirlo in due
parti: sinistra (ps) e destra (ds) che, rispetto a X (elemento di
separazione), siano:
elementi ps  X  elementi ds
2) Si ripete “ricorsivamente” l’algoritmo di separazione
per ps e ds fino all'ordinamento completo
fond. di informatica1 parte 5
36
ALGORITMO DI SEPARAZIONE
_ si sceglie un valore dell’ array (p.e. il mediano) come
elemento di separazione X
_ si cerca da sinistra il primo elemen. > X e lo si sposta
a destra di X se c' e’ un elem.
_ si cerca da destra il primo elemen. < X e lo si sposta
a sinistra di X se c' e’ un elem.
_ si prosegue da sinistra e da destra per gli elementi
successivi finche’‚ la ricerca di sinistra non si
"incrocia" con quella di destra
 Si ottiene:
elementi ps  X  elementi ds
fond. di informatica1 parte 5

37
ESEMPIO ALGORITMO
SEPARAZIONE con N=10
LISTA SIN.
9
s
0
0
1
1
s
1
X
5
LIS. DESTRA
6
4
8
2
7
3
0
d
6
1ø riordinamento
4
5
8
2
7
3
d
9
6
2ø riordinamento
4
5
3
2
7
8
9
d
s
s e d si "incrociano": separaz. Finita
#operaz. fatte <= n; #passi da fare  log2 n se le liste sono sempre
divise a metà altrimenti n fond. di informatica1 parte 5
38
COMPLESSITA' QUICKSORT
Caso peggiore:
n2
(liste “sbilanciate”, per es. ps di 2 termini ds di n-2 termini)
Caso
medio:
(liste sempre divise a metà)
n log2 n
•non richiede extra memoria
•si realizza facilmente con una procedura
ricorsiva
fond. di informatica1 parte 5
39
La ricorsione
Che cosa è ? la sua definizione appare
immediata dalla figura successiva tratta dal
testo “Algorithm + Data Structure = Programs”
di N. Wirth creatore del linguaggio Pascal;
la definizione di un oggetto in modo ricorsivo si
avvale dell’ uso di versioni “più semplici” dell’
oggetto stesso.
Si pensi alla definizione ricorsiva di numero
naturale:
1 è un numero naturale;
il successore di un numero naturale è un
numero naturale con successore(n)=n+1.
fond. di informatica1 parte 5
40
fond. di informatica1 parte 5
41
Algoritmi ricorsivi
Usano una funzione che si definisce attraverso se
stessa.
Vantaggi della forma ricorsiva:
formulazione naturale di problemi matematici definiti
in termini di se stessi;
programmi +facili da leggere.
Svantaggi della forma ricorsiva:
attenzione a non entrare in cicli senza fine: occorre
porre un limite alla definizione ricorsiva di un oggetto!
Talvolta può essere utile una soluzione di tipo
iterativo!
fond. di informatica1 parte 5
42
Ricorsione in C e C++
 Un sottoprogramma ricorsivo e’ attivato
ricorsivamente con un SOLO richiamo per ogni
attivazione.
 Come esempio illustrativo si considera il fattoriale di
n che si può definire in 2 modi:
1. n! = n.(n-1).(n-2)….3.2.1 (“produttoria”)
2. n! = n.(n-1)! (forma ricorsiva)
Occorre porre un limite alla definizione ricorsiva della
funzione fattoriale(n) limite dato dalla matematica
che stabilisce: n>0 e 0!=1.
Quindi la funzione ricorsiva fattoriale di n è la seguente:
fond. di informatica1 parte 5
43
int fattoriale (int n)
/* funzione che calcola il fattoriale di n in modo ricorsivo: se
n>0 si autoattiva con n-1 ponendo in risultato il valore di
n * fattoriale (n-1)… continua così finchè n diventa 0. A quel
punto ritorna 1, ma a chi ? A chi l’ ha attivata l’ ultima volta
ossia a se stessa ... */
{
int risultato;
if (n <= 0) return 1; //CONDIZIONE INDISPENSABILE!!!
else
{
risultato = n * fattoriale (n-1); //Autoattivazione con n-1
return risultato;
}
fond. di informatica1 parte 5
44
}
In programm7
si trovano sia il programma per il calcolo del fattoriale
con una funzione ricorsiva, sia la procedura di
ordinamento che usa l’ algoritmo Quick descritto
precedentemente e che segue…
A voi il compito di fare una funzione ricorsiva per
calcolare i numeri di Fibonacci! Ricordare:
Fib0 = 0; Fib1 = 1; Fibn+1 = Fibn + Fibn-1 con n>0
(In Programm7 project33 risolve il problemino….,
mentre il project32 ordina una tabella col metodo
ricorsivo del Quik-Sort … qui di seguito NO saltare)
fond. di informatica1 parte 5
45
Quick-Sort
 void ordina(int x[],int sin, int des)
 /* Effettua l' ordinamento di x (tabella di n elementi)

col metodo Quick da sin a des
 Parametri in ingresso: sin, des, x;
 Parametri che escono definiti: x;
 Variabili locali usate: i,j,k,w,perno; */
{ int i,j,k; /* var. di controllo */ int w; /* var. di comodo */ int
perno; /* var. col perno */
 /* Inizio parte esecutive di ordina */ i = sin; j = des;
 k= (sin +des)/2;
perno= x[k];

while (x[i]<perno) i++;

while (perno< x[j]) j--;

if (i<=j)

{w= x[i]; x[i]=x[j]; x[j]=w; }//scambio

if (sin < j) ordina (x, sin,j);

//cout<<"\n finii sin ora des i="<<i<<" des="<<des;

if ((i+1) < des) ordina (x,i+1,des);
46

}/* fine di ordina */
2
L’ emulazione della menoria Mezzalama
lez. 18 & seg.
introduce il ritorno all’ hardware
Vai a pag. 31
con lo scopo di parlare del linguaggio di E.E.
Si ricordi:
C.M. & CPU: indirizzo di ogni locazione di C.M.
=> in registri della CPU ( es. registro P =Puntatore, registro I.C.= Instruction Counter ...);
Contenuto di ogni locazione di C.M. => in altri
registri della CPU (per es. A = Accumulatore...);
C.M. (RAM): scandibile e rintracciabile per es.
col Registro P : IndirizziMemoria <=> Registro P;
CPU = Unita’ Centrale = Unita’ Elaborativa =
MicroProcessore per Personal Computer
fond. di informatica1 parte 5
47
Si ricordi anche la struttura
funzionale di EE gia’ vista:
Temporizzator
e
Unita’ Centrale di Controllo
Unita’ Aritmetico - Logica
CPU

Registri
Flag
Unita’ di controllo di
I/O
Periferiche
Memoria Centrale
Memorie di massa
fond. di informatica1 parte 5
48
La CPU controlla tutte le
operazioni di E.E.
Le operazioni possono essere:
interne alla CPU (per es. Somma i contenuti
di 2 Registri);
esterne come trasferimenti di dati verso la
(o dalla) C.M. o verso le (o dalle) interfacce
(Controller Unit) dei dispositivi periferici.
Notare: la CPU non invia i dati al dispositivo,
ma alla sua interfaccia!
fond. di informatica1 parte 5
49
La CPU lavora
in stretto contatto con la C.M. e per svolgere i
suoi compiti usa i registri, i Flag (indicatori di
stato) e inoltre le Unita’ di Controllo e
Aritmetico-Logica (A.L.U.). I registri piu’ usati
sono:
Registri P e I.C. (Istruction Counter) per tenere
gli Indirizzi,
Registri tipo Accumulatore (A, B, C … ed anche
Reg.1, Reg.2 ...) per tenere i Dati ,
Registro Istruzione (I.R.) per tenere le
Istruzioni del linguaggio della macchina.
fond. di informatica1 parte 5
50
CPU: funzionamento ciclico nell’
esecuzione di un programma
Ogni ciclo della CPU si compone di 3 fasi: fase
di fetch (=prelievo) dell’ istruzione,
fase di decodifica dell’ istruzione,
fase di esecuzione dell’ istruzione.
In ogni fase sono usati alcuni Registri.
Le operazioni relative ad ogni fase sono indicate
alla diapo seguente, ma
SALTARE 13 diapo, riprendere dai BUS,
diapo65.
fond. di informatica1 parte 5
51
Prelievo e decodifica saltare 13
diapo
fase di fetch (=prelievo: uso dei Reg. IC e IR):
1) Esame del Reg. I.C.;
2) Accesso alla locazione di C.M. indirizzata da
I.C.;
3) Trasferimento del contenuto della
locazione di C.M. in I.R.;
fase di decodifica: (uso del Reg. IR):
4) Interpretazione del contenuto di I.R.;
5) SE non e’ un' istruzione ALLORA
segnalazione ERRORE e STATO DI ATTESA
fond. di informatica1 parte 5
52
Esecuzione istruzione
… altrimenti fase di esecuzione:
SE si tratta di un’ istruzione di salto alla
locazione di memoria di indirizzo xyzv allora
I.C.= xyzv ed il controllo delle operazioni passa
a xyzv e da qui si prosegue in sequenza;
ALTRIMENTI: l' istruzione viene eseguita ed e’
incrementato I.C.= I.C.+(lunghezza istruz.)
per passare all’ istruzione successiva.
Si noti: in assenza di istruzioni di salto esiste un
ordinamento sequenziale tra le istruzioni.
fond. di informatica1 parte 5
53
Accesso alla Memoria:
per estrarre info. = leggere dalla Memoria;
per deporre info. = scrivere in Memoria;
Operazioni realizzabili:
 a Hardware con codici propri della CPU
 a Software con istruzioni di un Linguaggio
Artificiale, tradotte nei codici della CPU (ossia
nelle Istruzioni del linguaggio della macchina)
dal programma traduttore.
Esempio fase di esecuzione con uso del reg.P
(e non I.C. per brevità di scrittura)
Sia: Istruzione = Leggi un dato dal disco e
ponilo in C.M. all' indirizzo 00116
54
Registro P di 4 bit =>16 byte
indirizzabili (qui la freccia sintetizza il contenuto
di P)
 CPU = “Ragnetto”
Central Memory
0000
000
REG. P .
1
Accumulat.
Registro P.= Pointer
1111
fond. di informatica1 parte 5
55
Esempio: continua
C.P.U. pone 00116 nel Registro P cioe’ P= 00116
(cfr. grafico precedente) e passa il controllo all’
Unita’ di Controllo della Periferica disco.
Questa, attivato il lettore che legge il dato (per
es. 3.14), lo pone in un proprio registro: da qui
C.P.U. lo preleva e lo trasferisce nell’
Accumulatore ossia A = 3.14
Infine C.P.U. trasferisce il contenuto di A nella
Memoria indirizzata da P ossia Mem(P)=A (cfr.
grafico seguente)
fond. di informatica1 parte 5
56
Registro P di 4 bit => 16 byte
indirizzabili
 CPU = “Ragnetto”
Central Memory
3.14
REG. P.
0000
0001
3.14
Accumulat.
Registro P.= Pointer
1111
fond. di informatica1 parte 5
57
Ancora esempi
 Analogo comportamento se Istruzione = Visualizza un
dato su video … Se poi Istruzione = Somma i dati
delle locazioni di indirizzo 55516 e 12316 e
metti il risultato in C.M. all' indirizzo 66616
allora C.P.U. effettua le operazioni seguenti
(dove => significa sposta e il registro B  A)
55516 => P
Mem(P) => A
(per es. 891710 => A)
12316 => P Mem(P) => B (per es. 7910 => B)
A+B => A
(per es. 891710+7910 => A)
66616 => P
A => Mem(P)
fond. di informatica1 parte 5
58
Deduzioni logiche
Cosa vogliono evidenziare i precedenti esempi?
1) ogni accesso in C.M. avviene con il deposito
in un registro di CPU (I.C., P, …) dell’ indirizzo
della locazione (cella, byte, voce …) di C.M;
2) ogni insieme di istruzioni (ossia ogni
programma) per essere eseguito deve risiedere
in C.M.
3) se un salto rimanda ad un indirizzo dove non
c’e’ un’ istruzione, ma un dato: ERRORE!
fond. di informatica1 parte 5
59
Le istruzioni
del linguaggio macchina sono praticamente
comandi in codice. Il codice e’ quello capito
dalla CPU di E.E. con comandi indicati qui con
sigle simboliche, da immaginare in binario.
Per es. somma
avra’ il codice ADD

poni in memoria “
“ “
STORE
 carica in un registro “
“ “
LOAD
 salta (branch)
“
“ “
B
salta e torna indietro(back)“ “ “
BB
confronta (compare) avra’ il codice CMP
etc.
fond. di informatica1 parte 5
60
Il formato delle istruzioni
del linguaggio della macchina varia da C.P.U. a
C.P.U. col vincolo che ogni istruzione deve poter
stare nel registro I.R. della C.P.U. per essere
decodificata e poi eseguita. Il numero dei bit di
I.R. varia da C.P.U. a C.P.U….
Se per es. IR ha 32 bit allora si potrebbero
usare: 8 bit per il codice operativo (leggi, scrivi,
somma …), 4 bit indicare il supporto, 4 bit il
tipo di indirizzamento (immediato, diretto, indiretto) e
16 bit per indirizzare la memoria o altro.
Segue un esempio in un ipotetico linguaggio
macchina, non usando però codici binari, ma
61
mnemonici. SALTARE 3 diapo.
Come fare la somma S=S
in linguaggio macchina ?
i=0-7
5
In C++ o C  {int S = 0, i;
for ( i=0; i<8; i=++) S+ = 5;}
In ling.macchina le addizioni si fanno in A=Acc.
e per gli indici si usano i Reg.i e cosi’ a parole:

Azzera A e Carica in Reg.1 0
COME Confronta Reg.1 con 8

Se sono uguali salta a VIA

(se no) Aggiungi ad A 5

Incrementa Reg.1 di 1

Salta a COME
VIA
Memorizza
A in S (A => MemS) 62
fond. di informatica1 parte 5
E quindi:

CLEAR A

LOAD R1 #0 (#indica dato immediato)
COME CMP R1 #8 (se il compare da’ 0 FlagZero=1)

BZ
VIA (salta a VIA se FlagZero=1)

ADD A #5

INC
R1 (incrementa di 1 R1)

B
COME
VIA
STORE A ADDRS (--> ADDRS => P
e inoltre A => Mem(P))
fond. di informatica1 parte 5
63
o anche e meglio (con 1 giro
ed 1 istruzione in meno):


COME

CLEAR A
LOAD R1 #7
ADD A #5
DEC
R1 (decrementa di 1 R1 : quando R1= 0


VIA
BZ
VIA (salta a VIA se FlagZero=1)
B
COME
STORE A ADDRS
.
FlagZero=1)
fond. di informatica1 parte 5
64
BUS
Tra le unita’ di E.E. viaggiano dati e indirizzi …
 DOVE? Nei BUS !
BUS = l' insieme dei collegamenti (cavi e
connettori) tra C.P.U. e le altre componenti su
cui sono trasferiti le informazioni in parallelo a
pacchetti di n bit
BUS indirizzi => n da 16 a 20 bit e
BUS dati
=> n da 16 a 64 ”
Attualmente si usano 2-3 livelli di BUS per
accelerare i trasferimenti.
fond. di informatica1 parte 5
65
Memoria di massa :
Funzione: uguale a quella della C.M. (memorizzare
!!!), ma tecnologia di tipo magnetico ...
Caratteristica: permanenza delle informazioni (come
la ROM !!!), ma il Tempo di accesso che dipende
dal tipo,  10-100msec. Enorme divario con la C.M.
!!! Questo divario deve essere “compensato” con
operazioni di input/output che scambino un notevole
numero di informazioni in ogni accesso (vedere tra 5
diapo)
Supporto: disco fisso, floppy, nastro, C.D. , unità
esterna collegabile tramite USB...
Lettura/scrittura: Unita’ di Lettura/scrittura dotata di
66
una testina apposita o di raggio laser.
Tipo di accesso:
sequenziale e, per dischi (hard e floppy),
diretto o casuale (= random) tramite gli
indirizzi di settore e traccia creati (cfr.parte 2)
con la formattazione che divide il disco in tracce
ed ogni traccia in settori a partire da punti di
riferimento. RICORDARE che la Formattazione
annulla il contenuto preesistente! PERICOLO!
Capacita’
Capacita’
Capacita’
Capacita’
dei
dei
dei
dei
dischetti:  da 1200 Kbyte in su
dischi: da 10 Gigabyte
“ “
C.D.-D.V.D.:  oltre 1 Gigabyte;
nastri: variabile secondo il tipo di unita’
fond. di informatica1 parte 5
67
Unita’ periferiche: sistema video
E’ costituito da un display e da una scheda
grafica ed ha 2 modalita’ di funzionamento:
alfanumerica (p.e. 25righe x 80colonne di
testo) e grafica con necessita’ di un software
pilota (=driver) della scheda grafica che
permette diverse modalita’, risoluzioni … num.
di colori;
elemento base: PIXEL (PIcture ELement) in un
raster o matrice (griglia) di PIXEL (1280x1024;
…) usabili singolarmente in alta risoluzione, a
gruppi in bassa risoluzione.
fond. di informatica1 parte 5
68
Comunicazioni tra
elaboratori
Si basano su strumenti Hard./Soft. che
permettono di collegare elaboratori di vari tipi
in reti locali (LAN) e geografiche (WAN);
occorrono dispositivi di interfaccia tra
elaboratori (per es. “schede di rete”) e
protocolli (regole) di comunicazione;
si puo’ anche usare la rete telefonica con l’ uso
di dispositivi che permettono di convertire il
segnale analogico (voce) a segnale digitale (bit)
e viceversa.
fond. di informatica1 parte 5
69
E inoltre …
parlando di comunicazioni, il mezzo piu’
semplice per trasferire qualunque informazione
sia da C.M. a memoria di massa sia tra
Elaboratori di tipo diverso resta il file tipo testo
sequenziale memorizzato su memoria di massa.
Nel file tipo testo i byte sono interpretati come
caratteri ASCII (in altri file, quelli binari, ogni
byte e’ considerato come 8 bit di un dato
binario, per es. float);
I file tipo testo possono essere usati in lettura,
scrittura e aggiornamento.
fond. di informatica1 parte 5
70
Come si costruisce un file
tipo testo in C, C++ ?
Occorre usare le librerie e le funzioni giuste …
ma comunque sempre le informazioni al / dal
file sequenz. sono trasferite a blocchi, 1 blocco
per volta, da / a una zona di C.M. che funge da
tampone o buffer (= “interfaccia” tra i 2 tipi di
memoria) e da qui smistate (Cfr. parte2, file & C.M.)
Il C e C++ considerano un file sequenziale
come un flusso (stream) o successione
continua di byte proveniente da/inviata a
memoria di massa (analogia con cin e cout).
Per gestirlo pero’ usano procedure diverse.
fond. di informatica1 parte 5
71
Tipi di File
I file si distinguono in sequenziali e ad accesso
diretto o casuale (random qui non trattati).
La differenza sta nella struttura del file:
concettualmente il file sequenziale si puo’
assimilare ad una successione di informazioni
dove per raggiungere l’ informazione i-esima
occorre leggere le precedenti i-1; il file ad
accesso diretto si puo’ assimilare ad una
tabella dove per mezzo di un indice si puo’
raggiungere qualunque informazione
direttamente. Proprio a causa dell’ uso di un
indice si dicono indexed file.
72
Gestione di file sequenziali in C++
A differenza del C (che usa funzioni i cui
prototipi sono dichiarati in stdio.h), il C++ usa
le funzioni con prototipi dichiarati in fstream.h
dove sono anche definiti nuovi tipi di dati che
usano la classe fstream con sottoclassi, come
per es. il flusso di input e il flusso di output
(ifstream, ofstream) da/a un file.
Il discorso completo sarà ripreso subito dopo l’
introduzione delle classi.
SALTARE 2 diapo.
73
NO Gestione di file sequenziali in C
Il C usa le funzioni i cui prototipi sono dichiarati
in stdio.h e una struttura FILE anche definita
in stdio.h e accessibile con puntatori definiti
nel programma-utente. (La struttura FILE - visionarla!contiene al suo interno anche puntatori al buffer.) Il
collegamento con il file fisico si ottiene con la
funzione fopen che associa il nome del file al
puntatore a FILE dichiarato nel programma
utente: lo definisce. I nomi delle altre funzioni
utilizzate sono: fscanf, fprintf (analoghe a
scanf e printf) per leggere e registrare info.
fond. di informatica1 parte 5
74
Dove ?
NO …dove ?
Lettura e registrazione avvengono (tramite il
buffer) sul file aperto dalla fopen e identificato
da un puntatore a FILE dichiarato dall’ utente;
fopen definisce tale puntatore collegandolo al
file fisico; fscanf, fprintf usano tale puntatore
come primo argomento. Il collegamento e’
terminato dalla fclose che lo chiude quando il
file non serve piu’.
Vedere i programmi in C che usano le funzioni
prototipate in stdio.h per costruire un file (mat2
mat2pro e strutt) ed i programmi per leggerlo (fileper,
filequa) tutti in program8.
fond. di informatica1 parte 5
75
E … per emulare la memoria?
Le matrici non bastano: per i dati occorrerebbe
una zona a dimensione variabile (che si
puo’ ottenere con l’uso di funzioni come malloc
o new) di int ove porre valori interi e poi un’
altra zona di float, una di char …; una per gli
indirizzi e le istruzioni in linguaggio macchina e
poi ancora occorrerebbe un’ altra zona per gli
interi unsigned, etc. Insomma un contenitore di
elementi di tipo diverso, non omogenei ed
anche a dimensione variabile.
Un tipo di variabile strutturata che permette
di mantenere in memoria un insieme fisso di
elementi non omogenei e’ la struct del C e
76
C++ simile al record del Pascal.
Esempio di struct in C e C++
struct studente
{char nome[20];
char cognome[25];
int eta;
float peso;
float altezza;
};
Concettualmente con la keyword
struct si definisce un tipo di tabella non
omogenea con elementi di vari tipi che in C e
C++ possono essere anche funzioni: cosi’
fatta la struct puo’ servire a introdurre la class
del C++…ma questa e’ un’ altra storia che inizia
con…
fond. di informatica1 parte 5
77
Il paradigma O.O. (Object
Oriented)
Si tratta di un modello che mette in luce l’ aspetto dell’
astrazione dei tipi di dati.
I dati sono spesso di tipo complesso composti per
esempio da suoni, immagini oltre che da valori
numerici e alfanumerici. Occorre scrivere software
adeguato alla loro gestione. Si raggiunge questo
obiettivo con la definizione di nuovi tipi di dati che si
dicono “tipi di dati astratti” e si distinguono da
quelli predefiniti come int, float… Come i predefiniti
sono gestiti con proprie funzioni (per es. operazioni
aritmetiche intere per il tipo int) anche i tipi di dati
astratti sono gestibili solo con proprie funzioni dette
fond. di informatica1 parte 5
78
metodi.
Un esempio: il tipo pila
E’ un esempio semplice, ma che ha tanti
esemplari nel mondo reale: pila di pratiche, pila
di piatti, pila di parentesi, pila di registri di
memoria….
Si puo realizzare considerando una struttura
sequenziale di valori in cui le inserzioni ed i
prelievi avvengono allo stesso estremo: la cima
o TOP della pila 
C
B
A
 il primo entrato A è l’ ultimo ad uscire: questo è il
criterio di gestione della pila: LIFO Last In First Out79
Tipi di dati astratti
Come si definisce un Tipo di dato astratto ? per
esempio il tipo pila? La definizione del tipo pila si
chiarisce con la sua struttura e con l’indicazione dell’
algoritmo LIFO di gestione tipico della pila 
 per un Tipo di dato astratto e’ importante definire:
la struttura dati (proprietà statiche);
le proprietà dinamiche (gli algoritmi usati per la
relativa gestione) ossia le funzioni associate al tipo
detti metodi.
Quindi  il Tipo astratto e’ definito sia in senso
statico con la sua struttura che dinamico con i suoi
metodi che lo possono (loro soltanto!!!)
manipolare. Al Tipo astratto è associata una classe di
Oggetti ciascuno con il proprio Valore.
fond. di informatica1 parte 5
80
ed in C++ ?
La class del C++ permette la definizione e la
costruzione di tipi di dati astratti che si
definiscono per gestire oggetti complessi e da
proteggere come la memoria, la pila, lo
studente, il tempo, il punto…
Il tipo pila diventa la class pila che può avere
una tabella per memorizzare i suoi elementi
ed i metodi impila per inserirci nuovi elementi
ed espila per estrarre elementi: ad altre
procedure sarà vietato l’ accesso alla pila.
Si realizza così anche la protezione di oggetti!
fond. di informatica1 parte 5
81
Sintassi d’ uso!
In qualunque oggetto del C++ il punto “.“ collega l’
oggetto alle sue caratteristiche. Per il tipo pila un
oggetto p della class pila avrà p.tab[n] come
struttura statica e come metodi p.impila(),
p.espila().
Definita la class pila un oggetto p appare come una
variabile di tipo pila: pila p;
La progettazione-costruzione di nuovi tipi di oggetti (di
cui un esempio è in program7 project 92 e qui di
seguito) non è elementare, anche perché prevede una
sintassi particolare.
Non è difficile invece utilizzare oggetti già
progettati e che si ritrovano nelle librerie del
C++ … e questo proveremo a fare.
82
prima però: PROGRAM contator
/*Il programma contator.cpp deve:

mostrare come si usano le classi in C++ con una
classe di contatori.

Viene definito Contatore come class con i tipi dei
suoi dati e le relative funzioni. Queste funzioni (e solo
loro) permettono di lavorare con oggetti della classe:
con esse si azzera, si incrementa, si decrementa, si
interroga un contatore. Esaminare il main qui di
seguito ! Esaminare le definizioni di Contatore e delle
sue funzioni (metodi).

Far girare il prg. project92 e alla fine chiuderlo !
fond. di informatica1 parte 5
83
#include "iostream.h" //"Libreria richiesta I-O C++
#include "conio.h" // "
"
I/O speciale (clrscr)
#define MAX 9
/* seguono la dichiarazione della classe contatore (nuovo tipo) e del prototipo della funzione attendi */
.




 class contatore








{unsigned int valore;
public:
void azzera();
void incrementa();
void decrementa();
unsigned int contenuto();
};
void attendi();
 main()












/* Inizio Modulo principale */
{ int n;
contatore c1,c2;
/* INIZIO Parte esecutiva */ clrscr();
/* Azzeramento*/ c1.azzera(); c2.azzera();
/* Incremento */ for (n=0; n<MAX; n++) { c1.incrementa(); c2.incrementa(); }
/* Decremento */ c2.decrementa();
cout<<"\n alla fine c1 e':" << c1.contenuto() <<" mentre c2 e':"<< c2.contenuto() << endl;
attendi(); return (0);
}
/* seguono la definizione delle funzioni dichiarate nella classe contatore e della
funzione attendi() */
void contatore :: azzera()
84
{ this->valore = 0; return; } ….
Oggetti
 In C++ oggetti sono: le stringhe, i flussi di input/ouput, i
pixel o in generale i punti… definiti come oggetti delle
relative class
 Cominciamo con i flussi di informazioni e con la
gestione di file sequenziali in C++ (rimasta in
sospeso).
 C++ gestisce i file sequenziali con le funzioni i cui
prototipi sono dichiarati in fstream.h dove sono anche
definiti nuovi tipi di dati che usano la classe fstream
(flusso) con sottoclassi, come per es. il flusso di input e
il flusso di output (ifstream, ofstream) da/a un file.
 Incluso fstream.h nel programma si deve definire una
variabile di tipo flusso e poi collegarla
 o con un file fisico presente su disco (quindi da leggere)
 o col file da creare (registrare) su disco o da aggiornare.
85
Apertura del file
Questa operazione di collegamento si chiama apertura
del file e richiede:
o l’ indicazione sul tipo di gestione del file: lettura,
scrittura, aggiornamento ?
oppure l’ uso delle sottoclassi che il C++ fornisce ossia
ifstream come tipo di flusso di input e ofstream
come tipo di flusso di output (seguono esempi); per l’
aggiornamento si usa invece un’ altra specifica qui non
trattata.
Si noti che anche cin è un oggetto della classe
iostream con cin.fail, cin.eof(), cin.get(char*,... ) …
sue funzioni… o metodi !
86
Lettura file sequenziale in C++
Per leggere il file numeri.txt si puo’ scrivere:
… int n, elabora(int);
ifstream fi;//fi=var. tipo flusso input (analogia con cin)
fi.open(“numeri.txt”); /* si richiede di aprire il file
numeri.txt collegandolo al flusso fi */
if (!fi) // se fi = 0 l’ apertura e’ fallita
{cout<<“non trovo il file”<<endl; return(1); }
else while (!fi.eof()) { fi >> n; /*finche’ non
trovi EOF, leggi, poni in n e visualizza n e il risultato*/
cout <<“\nn=“;<<n<<“ Ris=“<< elabora(n);}
fi.close(); //si richiede di chiudere il file
numeri.txt
fond. di informatica1 parte 5
87
Un esempio della lettura
di un file di struct è project43 in program7
in cui viene letto un file tipo testo
(infdat.txt) e sono visualizzate le
informazioni in esso contenute insieme ad
altre calcolate.
In project43 viene richiesta la
registrazione di tutte le informazioni in un
nuovo file. A voi provare usando le
informazioni della diapo seguente.
fond. di informatica1 parte 5
88
Costruzione file sequenziale
Per registrare nel file risult.ati una sequenza di
interi in C++ si puo’ per esempio scrivere :
… int i, elabora(int), n [100]; /*si pensi ad
inizializzare il vettore n con un for... */
ofstream fa; // fa=var. tipo flusso output (…cout)
fa.open(“risultati.txt”); /* si richiede di aprire il
file risultati.txt e di collegarlo al flusso fa */
if (fa) // se fa = true il file gia’ esiste
cout<<“il file gia’ esiste: lo copro”<<endl;
for (i =0; i<99; i++) fa << n[i]<<endl; /* con
endl si registra un numero per linea (=record !) */
fa.close(); //si richiede di chiudere il file
fond. di informatica1 parte 5
...
89
Continuiamo con un cenno agli
oggetti grafici
La grafica è un capitolo importante della
programmazione, ma qui solo un accenno indicativo:
vedere e capire project39 (Grafica1) che è un’
applicazione VISUAL e disegna 2 linee, un rettangolo
ed un’ ellisse.
Sono tutti oggetti che si ricavano dall’ oggetto grafico
fondamentale che è il punto.
(…comunque per fare semplicemente un disegno in
C++ della Borland: aprire un’ applic. visual che apre
una finestra form1 con i Pixel in evidenza; trasportarci
col mouse il botton OK a cui dare il nome Run e
associarlo al funzionamento; andare nella guida,
90
cercare Tpoint, Canvas (tela) e vedere gli esempi …
Gli esempi
In programm7 il project43 usa una tabella di struct
definita come variabile locale del main.
Si noti come il passaggio alla procedura visualizza
avviene per indirizzo usando semplicemente il nome
della struct da passare.
Anche per le struct il nome è sinonimo dell’ indirizzo
che si può anche porre in un puntatore, ma questo è
un modo di utilizzo meno elementare.
Il project 92 fa un esempio di class.
Il project39 fa un’ ellisse e 2 linee: per usare punti
vedere gli esempi in tpoint (tipo punto)
Il project 30 in program6 risponde alla domanda di ieri
e cerca un elemento nella tavola pitagorica. I suoi
obbiettivi sono:
fond. di informatica1 parte 5
91
/*Il programma deve: costruire la tavola pitagorica
della moltiplicazione e visualizzarla per righe e
ricercarvi un elemento con la funz. int ricerca(...) che
restituisce o il valore trovato, o 99 e gli indici del
valore trovato: poi il main l’esamina e se il valore
restituito é 99 dice che la ricerca é fallita. seguono:
prototipo, attivazione nel main e funz. ricerca*/
 int ricerca (int [][MAX], int, int*, int*);
…
cout<<"dammi un intero ";

cin >>ricercato;

cout<<endl<<"VAL RICERCATO = "<<
ricercato<<endl;

restituito = ricerca (tavola,ricercato, &ir, &ic);
….
.
fond. di informatica1 parte 5
92
.
int ricerca (int t[][MAX], int v, int* p1, int* p2)
 { /* Inizio ricerca che cerca in t il valore v e
 se lo trova lo pone in reso e pone in *p1 e in *p2 i
suoi indici */
 int reso =99, ir, ic;
 for (ir=1; ir<MAX; ir++)
 for (ic=1; ic<MAX; ic++)
 if( t[ir][ic] ==v)
 {reso =v;
 *p1=ir;
 *p2=ic;
 break;
 }
 return reso;
 }
fond. di informatica1 parte 5
93
Argomenti del main
Per trasmettere ad un programma C o C++
informazioni (per es. il nome del file di lavoro
dati.per) si usano i parametri della main
function che finora era sempre scritta main().
La main function ha 2 forme di intestazione:
int main()
int main(int argc, char* argv[])
dalle quali si nota che il valore di ritorno e’ int
(come quello indicato nella frase return (0) !!),
ma spesso int è omesso.
fond. di informatica1 parte 5
94
main
Nella seconda forma si notano: int argc che e’
il numero di parametri trasmessi, char* argv[]
che e’ un vettore di puntatori a stringhe= nomi
dei parametri trasmessi.
In argv[0] c’ e’ il puntatore al nome del
programma, primo argomento presente sulla
linea di attivazione del programma stesso; nei
successivi ci sono puntatori alle stringhe che
sono gli altri argomenti presenti sulla linea di
attivazione del programma stesso.
fond. di informatica1 parte 5
95
… Ancora esempi
 Avendo scritto la frase main cosi’:
main(int argc, char *argv[])
 la linea di attivazione potra’ essere cosi’ fatta:
fileper.exe dati.per
dove il file di dati da leggere (dati.per) e’ fornito in
argv[1], in argv[0] va fileper (nome del programma) e
argc viene posto =2.
Tutto questo deve servire da guida, ma per imparare
occorre FARE e poi provare e riprovare con pazienza!
fine … anzi no, prima ecco un regalino!
fond. di informatica1 parte 5
96
SATOR
AREPO
TENET
OPERA
ROTAS
E’ una formula (magica ?) che é incisa nella
parete esterna sinistra (gurdando la facciata) del
Duomo di Siena.
Era usata nella realizzazione di opere importanti
come buon augurio.
Si legge in tutti i sensi … ma cosa significa?
fond. di informatica1 parte 5
97
Il Significato sembra il seguente: Il
Seminatore Tiene con l’ Opera le Ruote
dell’ Aratro (Arepo dal greco Arotron)
 che però potrebbe essere anche un nome magico come Aleppe (in Dante:
“Pape Satan, Pape Satan Aleppe”). Permutando tutte le lettere del quadro
magico si ottiene:
P

A

T

E

R

PATERNOSTER

O

S

T

E

R
un esempio di permutazione che vi
lascio da fare con un programma in C++!!! FINE !
fond. di informatica1 parte 5
98
Appendice a): perplessita’ 1
RICORDARSI: l’ operatore >> preleva un dato
dal un flusso di input: che tipo di dato? Il tipo
che e’ stato dichiarato: char, int, float, ...
2) RICORDARSI: non abusare di matrici e/o
vettori; usarli solo quando esiste la necessita’ di
tenere memoria dei valori calcolati o letti: se
tale necessita’ manca allora usare il valore letto
per i calcoli necessari e passare al successivo
valore da leggere.
fond. di informatica1 parte 5
99
Appendice a): perplessita’ 2-1
Ricordare che gli indici di un array sono
SEMPRE di tipo “discreto”, MAI floatingpont!!!
NON CONFONDERE INDICE CON
CONTENUTO DI UN ELEMENTO !!!
Ed ancora array e strutture sono passati a
procedure per indirizzo, ma il loro indirizzo è
rappresentato dal loro NOME e NON da
&nome o da *nome!!!
fond. di informatica1 parte 5
100
Ancora su array: perplessita’ 2-2
se si vuole fare una ricerca in un array ad una
dimensione (vettore) si può usare il metodo
lineare esaminando un elemento dopo l’ altro
con un for oppure il metodo della bisezione
(dividendo il vettore a metà e poi a metà delle
metà e così via) accelerando la ricerca.
In array a 2 dimensioni (matrici) il modo più
semplice da usare è il metodo lineare: si
esamina una riga alla volta e dentro ogni riga
un elemento dopo l’ altro con 2 for nidificati.
fond. di informatica1 parte 5
101
Appendice a): perplessita’ 2
3) La funzione elabora usata in tanti esempi di
programmi indica col suo nome una
elaborazione di tipo generale. Quando l’
elaborazione e’ di un tipo specificato e’ meglio
usare nomi di funzioni pertinenti, come fatto
nell’ esempio sulla valutazione del minimo e del
massimo (parte 4) dove si usavano nomi come
minimo, massimo, rivaluta e memovis. Cosi’ il
programma diventa +comprensibile e -generico
Come ulteriore esempio, se in un programma ...
fond. di informatica1 parte 5
102
Appendice a): perplessita’ 3
… se in un programma e’ richiesto di leggere
una matrice di valori interi e ricercarvi un certo
valore (letto anch’esso da tastiera) le funzioni
da usare e costruire saranno:
leggi(matrice); cin>> valore;
if (ricerca(valore, matrice, &riga, &colonna))
visualizza(“\ntrovo valore in ”, riga,colonna);
else cout<< “\nIl valore non c’e’ !”<<endl;
QUI la funzione elabora e’ la ricerca che ritorna
un valore bool! fond. di informatica1 parte 5
103
Appendice a): GIA’ FATTO
perplessita’ 4
4) RICORDARE: la codifica F.P. normalizzata fa
riferimento alla base 2 e quindi il valore dell’
esponente riguarda la base 2. Col metodo delle
moltiplicazioni successive ogni moltiplicazione
per la base isola una nuova cifra nella nuova
base. Per es.  =3.1410 avra’ 112 come parte
intera e 00100011112 come parte decimale.
Normalizzando  +.1100100011112 E+102
con S=0, M=1100100011112, E=0102 .
fond. di informatica1 parte 5
104
Appendice a): perplessita’ 5
5) RICORDARSI di fare attenzione alle
specifiche di progetto di un programma: IN
PARTICOLARE alle specifiche di progetto del
programma da costruire all’ esame che stanno
nelle relative richieste. Analizzarle e riflettere!
UN CONSIGLIO per l’ esame: scrivere il
programma in modo semplice e chiaro, con
qualche commento, ma senza fronzoli,
badando a rispondere a tutte e sole le
richieste. Privilegiare la sostanza ! Se resta
tempo aggiungere … i “fiorellini” !
fond. di informatica1 parte 5
105
Appendice a): perplessita’ 6
6)RICORDARE quanto detto in fondinf3 diapo 48
e seg. “Primo motivo per l' introduzione dei
sottoprogrammi: Si inserisce una sola volta
il codice del sottoprogramma (per es. la
printf ….”)
Se si devono leggere 10 matrici si scrive una
procedura di lettura di una matrice generica e si
richiama 10 volte per leggere le 10 matrici una
alla volta!!! NON scrivere una procedura con la
lettura di 10 matrici … (e capita anche che
qualcuno la richiami 10 volte!!!)
106
Appendice a): perplessita’ 7
Attenzione al significato del while che è:
fin tanto che, per tutto il tempo che è vera la
condizione tra parentesi
E NON: fino al momento in cui diventerà vera!!!
Se si deve leggere un valore <0 si scriverà:
cin>> comodo;

while (comodo >=0) cin>> comodo;
ed anche, se A e B sono array:

if (tot<soglia) cout<<"\n Soglia non

raggiunta da tot = "<<tot<<endl;

else { while ((tot=somma (A,B))>= soglia)

diminuisci(A,B); …. }
e ricordarsi l’ else, ma solo quando occorre !!!
fond. di informatica1 parte 5
107
Appendice a): continua
perplessita’ 7
ed inoltre: usare il while
appropriatamente!
NON si deve scrivere:
cin>> comodo;

while (comodo >=0)
{ }
va in loop !!!
fond. di informatica1 parte 5
108
Ancora ricordare:
nella provetta non sarà richiesto l’ uso di file che
invece potranno essere richiesti nei temi d’ esame
dove potranno essere anche domande su algoritmi
ricorsivi, sul funzionamento della CPU, sui tipi di dati
astratti, sugli argomenti del main … insomma su
quello che si trova in quest’ ultima dispensa.
Come appare dal file Notifica.doc sono ammessi alla
seconda provetta TUTTI E SOLI gli studenti che hanno
fatto la prima provetta, NON ALTRI.
Presentarsi alla provetta con il libretto da RITIRARE
alla fine della provetta.
fond. di informatica1 parte 5
109
Iscrizione agli esami
Per gli esami occorre ISCRIVERSI, nel foglio che
si troverà sulla porta del mio studio.
Sono valide le iscrizioni fatte fino a 2 giorni
prima dello scritto.
NON SI POSSONO FARE 2 APPELLI
CONSECUTIVI !!!
Presentarsi all’ esame scritto col libretto da
ritirare alla fine dello scritto.
fond. di informatica1 parte 5
110
Appendice b): esempi di temi d’esame
del 2000: simili saranno anche nel 2006
 Fondamenti di Informatica 1
 TEMPO = 1 ORA e 1/2,
 NON AMMESSI TESTI, APPUNTI, CALCOLATRICI.
 1) Conversioni di base (punteggio =2)

Esprimere in base 10 l' intero positivo piu' grande
rappresentabile con 6 bit in base 2.

Scrivere la rappresentazione binaria normalizzata di 3/4
 2) (punteggio =1)
 Come sono effettuate le divisioni per 2 dei numeri interi dall'
Unita' Aritmetico-Logica?
fond. di informatica1 parte 5
111
Appendice b; continua 2
 3) (punteggio =2) NO
 In un circuito logico a 3 ingressi (V,X,Y) la funzione Z vale 1
quando la combinazione di ingresso e’ dispari: scrivere la
funzione Z.
 4) (punteggio =5)
 Scrivere in C o C++ un programma strutturato in
sottoprogrammi che provveda a costruire in Memoria Centrale
una matrice F di N*M elementi float. Ogni elemento di F deve
contenere il valore della funzione
 f = 0.5*x2 +1.5*y +1
 per x variabile con passo dx=0.5 nell' intervallo 0.0  x  2.0
e y variabile con passo dy=0.1 nell' intervallo 0.0  y  0.3
(Estremi inclusi!)
fond. di informatica1 parte 5
112
Appendice b; continua 3
 (SI NOTI che N ed M vanno calcolati in funzione degli intervalli
di definizione di x e y e dei passi dx e dy sopra specificati).
 Dopo la costruzione della matrice F, il programma deve:
 visualizzare su video i valori N e M e la matrice F per righe.
 N.B. E' SCONSIGLIATO L' USO DI VARTIABILI GLOBALI
 Fondamenti di Informatica 1
 TEMPO = 1 ORA e 1/2,
 NON AMMESSI TESTI, APPUNTI, CALCOLATRICI.
 1) Conversioni di base (punteggio =2)
 Dare la forma normalizzata binaria Floating Point con 1 bit
per S, 3 bit per E , 4 bit per M del valore X=1/4 in base 10.
fond. di informatica1 parte 5
113
Appendice b; continua 4
 Dare la rappresentazione binaria in complemento a 2 con 8 bit
di X = 1510.
 2) (punteggio =1) Indicare quante sono e quali sono le fasi di
cui si compone il ciclo della CPU (Unita' Centrale di Elaboraz.)
 3) (punteggio =2) Indicare sinteticamente come lavora un
Sistema operativo multiprogrammato e dove si trovano i "molti"
programmi da essere eseguiti.
 4) (punteggio = 5) Scrivere in C++ un programma strutturato
in sottoprogrammi che faccia le seguenti azioni tramite apposite
procedure o funzioni:
 _ costruire in Memoria Centrale un vettore (tabella) di 10
elementi interi ordinati dove ogni elemento e' divisibile per 3 e
per 5 ossia 15, 30, 45, 60, ... e visualizzarlo
fond. di informatica1 parte 5
114
Appendice b; continua 5
 _ chiedere all' utente 2 valori interi (non compresi tra quelli
posti nel vettore);
 _ aggiungere nel vettore i 2 valori letti posizionandoli nei
posti voluti dall' ordinamento e visualizzare il vettore cosi'
modificato. (Se per esempio i valori letti sono 7 e 31 il vettore
modificato risultera': 7, 15, 30, 31, 45, 60, ... )

N.B. E' SCONSIGLIATO L' USO DI VARTIABILI GLOBALI
 Fondamenti di Informatica 1
 TEMPO = 1 ORA e 1/2,
 NON AMMESSI TESTI, APPUNTI, CALCOLATRICI.
 1) Conversioni di base (punteggio =2)
 Usando l' aritmetica binaria e la notazione in complemento a 2
fond. di informatica1 parte 5
115
Appendice b; continua 6

calcolare: la differenza tra
01012 e 10112 ;

il valore di un registro a 4 bit contenente 11112.

 2) (punteggio =1) Indicare la funzione del linker e quando e'
usato.
 3) (punteggio =2) NO !Indicare come viene realizzata la
dipendenza dal tempo nei circuiti elementari di memoria
FF_SR utilizzati per memorizzare i bit. Indicare anche la loro
struttura.
 4) (punteggio =5) Scrivere in C++ un programma strutturato
in sottoprogrammi che in Memoria Centrale utilizzi 3 matrici
bidimensionali di interi e di dimensione 3x3, A, B, C, e dotato di
un programma principale consistente dei passi seguenti:
fond. di informatica1 parte 5
116

Appendice b; continua 7
 P1.
init (A); init (B);
 P2.
C = A*B;
 P3.
stampa(A), stampa(B), stampa(C).
 NOTE: Le matrici A e B devono essere opportunamente
inizializzate tramite una procedura di lettura da tastiera, con
prototipo del tipo: void init(X) dove X e' una matrice 3x3 che
in uscita da init contiene i valori letti;
 Le 2 matrici A e B cosi' inizializzate, devono essere moltiplicate
tramite la procedura: void product(....) con tre parametri
(matrice C in uscita, matrici A e B in ingresso), ossia il risultato
di product( ...) e': C = A*B (ricordando che un elemento C[i][j]
e' dato dalla sommatoria in k di A[i][k] * B[k][j] );
fond. di informatica1 parte 5
117
Appendice b; continua 8
 Le matrici A, B, C devono essere visualizzate tramite la
procedura void stampa(X) che visualizza per righe sul display la
matrice X di dimensioni 3x3.
 N.B. E' SCONSIGLIATO L' USO DI VARTIABILI GLOBALI.
 Fondamenti di Informatica 1
 TEMPO = 1 ORA e 1/2,
 NON AMMESSI TESTI, APPUNTI, CALCOLATRICI
 1) Conversioni di base (punteggio =2)
 da base 2 in forma Floating Point normalizzata con Segno = 0,
 Esponente= 0012 Mantissa Normalizzata=10102 a base 10 =?
 da base 10 a base 16: 12310 = ?
fond. di informatica1 parte 5
118
Appendice b; continua 9
 2) (punt. =1) Indicare la differenza tra file e directory del DOS.
 3) (punteggio =2) In cosa consistono le fasi di Fetch (prelievo)
e decodifica di un' istruzione in linguaggio macchina ? chi le
attua ?
 4) (punteggio = 5) Scrivere in C++ un programma
strutturato in sottoprogrammi che:
 legga da tastiera un insieme di valori interi da memorizzare in T
array monodimemnsionale (vettore) di al massimo 99 elementi;
 attivi una procedura Conta che esamini T e restituisca 2 valori
e cioe': il numero degli elementi effettivamente presenti in T,
e il numero degli elementi che hanno un valore non divisibile
per 2 ne' per 3 e visualizzi sul video tali numeri.
 N.B. E' SCONSIGLIATO L' USO DI VARTIABILI GLOBALI
fond. di informatica1 parte 5
119
Esempio di provetta: esame del 28.6.2005
Scrivere un programma strutturato in sottoprogrammi che in
Memoria Centrale utilizzi 3 matrici bidimensionali di interi e di
dimensione 3x3, A, B, C, e dotato di un programma principale
consistente dei passi seguenti:
 P1. (punteggio =3)
init (A); init (B);
 P2. (punteggio =3)
C = A*B;
 P3. (punteggio =2)
stampa(A), stampa(B), stampa(C).
 NOTE:
 Le 2 matrici A e B devono essere (inizializzate tramite una procedura che
genera numeri casuali compresi tra 0 e 8, escludendo però 3 ed i suoi multipli)
lette da tastiera per righe;
 le 2 matrici A e B cosi' inizializzate, devono essere moltiplicate
tramite una procedura che ne effettua il prodotto e lo pone in
C. (Ricordare che un elemento C[i][j] e' dato dalla sommatoria
per k che varia da 0 a 2 di A[i][k] * B[k][j] );
 Le matrici A, B, C devono essere visualizzate tramite apposita
procedura che visualizza per righe sul display una matrice di
dimensioni 3x3.
120
 La soluzione è in program6, project35 e di seguito
/* Dichiarazione dei Prototipi dei MODULI usati */
void scrivi(int [][MAX], char); /*si dichiara di usare una mat. di
MAX colon. e con un carattere che sarà il nome della mat. */
void attendi(); void leggi(int [][MAX]);
void prodotto(int [][MAX],int [][MAX],int [][MAX]); //3 mat.
main()
{/* Inizio Modulo principale */
int A[MAX][MAX],B[MAX][MAX],C[MAX][MAX];
/* INIZIO Parte esecutiva */
leggi (A);
leggi(B);
prodotto(A,B,C);
clrscr(); scrivi(A, 'A'); scrivi(B, 'B'); scrivi(C, 'C');
attendi();
return(0);
}
/* Fine Modulo principale */
fond. di informatica1 parte 5
121
void scrivi (int t[][MAX], char nome)
/* t =nome della matrice */
{
/* Inizio scrivi */
int ic,n;
cout<<"\nMatrice "<<nome;
cout <<" valori per righe (scrivi) \n";
for (n=0; n<MAX; n++)
{
for (ic=0; ic<MAX; ic++)
cout<< setw(4)<< t[n][ic]<<" ";
cout<< "\n";
}
} /* Fine scrivi*/
fond. di informatica1 parte 5
122
void prodotto(int a[][MAX],int b[][MAX],int
c[][MAX]) //i nomi sono minuscoli !!!
{ /* Inizio prodotto */
int i,j,k; //var. di controllo
for (i=0; i<MAX; i++)
for (j=0; j<MAX; j++)
{ c[i][j] =0;
for (k=0; k<MAX; k++)
c[i][j]= c[i][j] +a[i][k]*b[k][j];
} // calcolato C [i][j]
}
fond. di informatica1 parte 5
123