Informatica 1
-
Upload
emilia-calzetta -
Category
Education
-
view
1.981 -
download
2
description
Transcript of Informatica 1
INFORMATICA Algoritmi, funzioni e procedure
(teoria di base)
DAL PROBLEMA AL PROGRAMMA
PROBLEMA ALGORITMO PROBLEMA ALGORITMO PROGRAMMAPROGRAMMA
1. 1. Analisi del problema e identificazione di una soluzione;
2. 2. Stesura dell’algoritmo risolutivo;
3. 3. Programmazione, cioè scrittura dell’algoritmo in un linguaggio di programmazione;
4. 4. Esecuzione traduzione del programma in un linguaggio direttamente eseguibile dalla macchina e verifica del suo funzionamento
2
ALGORITMO DEFINIZIONE (1)
Un algoritmo e' una successione finita ed ordinata di azioni da eseguire per risolvere il problema.
Un algoritmo deve essere: Finito costituito cioè da un numero limitato di passi (le istruzioni sono in numero finito e vengono eseguite un numero finito di volte);
Deterministico deve considerare tutti i casi possibili che si possono verificare durante l'esecuzione e per ogni caso deve indicare la soluzione da eseguire;
Eseguibile cioè la sua esecuzione deve essere possibile con gli strumenti di cui si dispone;
Non ambiguo ogni istruzione deve consentire un’interpretazione chiara ed univoca;
3
ALGORITMO DEFINIZIONE (2)
L'algoritmo e' indipendente dal linguaggio di programmazione e può essere rappresentato in:
PSEUDOCODIFICA: PSEUDOCODIFICA: descrizione di un algoritmo utilizzando termini del linguaggio comune. Non si tratta di un vero e proprio linguaggio di programmazione, ma di un linguaggio sintetico composto da un vocabolario e una sintassi molto ristretti.
DIAGRAMMI A BLOCCHI: DIAGRAMMI A BLOCCHI: linguaggio formale di tipo grafico per rappresentare l’ordine di esecuzione delle istruzioni negli algoritmi.
4
PSEUDOCODIFICA(1)
Utilizzando la pseudocodifica, il programmatore esprime le proprie idee attraverso espressioni elementari della lingua italiana.
Le regole seguenti vanno eseguite con rigore:
Le parole chiave che aprono e chiudono il testo di un algoritmo sono: INIZIO e FINE
Ogni istruzione è indicata con una frase del linguaggio corrente e può contenere un'espressione di tipo aritmetico o logico.
5
PSEUDOCODIFICA(2)
Le istruzioni LEGGI e SCRIVI vengono utilizzate per descrivere le operazioni input ed output dei dati.
leggileggi(lista di variabili) e scrivi scrivi (variabili e costanti)
La richiesta all'utente, per acquisire i dati necessari all'elaborazione, può essere fatta nel seguente modo:
chiedichiedi(lista dei dati che servono)
Oltre a INIZIO e FINE sono utilizzate in pseudocodifica altre parole chiave che corrispondono ai passaggi fondamentali dell'algoritmo.
6
ESEMPIO PSEUDOCODIFICA
Problema:Problema: Trovare l'area di un rettangolo conoscendo la base e l'altezza.
Analisi del problema:Analisi del problema:Dati di INPUT: base ed altezza del rettangolo.Dati di OUTPUT: area del rettangolo.
Pseudocodifica:Pseudocodifica:
7
DIAGRAMMI A BLOCCHI (1)
Attraverso il diagramma a blocchi (o flow chart) si può indicare l’ordine di esecuzione delle istruzioni: Un particolare simbolo grafico detto blocco elementare è associato a ciascun tipo di istruzione elementare.
I blocchi sono collegati fra loro tramite frecce che indicano il susseguirsi delle istruzioni.
8
DIAGRAMMI A BLOCCHI (2)
I blocchi elementari sono i seguenti:
9
DIAGRAMMI A BLOCCHI (3)
Un diagramma a blocchi descrive un algoritmo se:
ha un blocco iniziale e uno finale;
è costituito da un numero finito di blocchi azione e/o blocchi lettura/scrittura e/o blocchi di controllo;
ciascun blocco elementare soddisfa le condizioni di validità.
10
CONDIZIONI DI VALIDITÀ
ciascun blocco azione, lettura/scrittura ha una sola freccia entrante e una sola freccia uscente;
ciascun blocco di controllo ha una sola freccia entrante e due frecce uscenti;
ciascuna freccia entra in un blocco o si innesta su un’altra freccia;
ciascun blocco è raggiungibile dal blocco iniziale;
il blocco finale è raggiungibile da qualsiasi altro blocco. 11
ESEMPIO DIAGRAMMA A BLOCCHIPseudocodifica: Diagramma a
blocchi:
12
INIZIOINIZIO
FINEFINE
Chiedi(base, Chiedi(base, altezza)altezza)
Leggi(base, Leggi(base, altezza)altezza)
Scrivi(area)Scrivi(area)
area=base*altezzarea=base*altezzaa
SCOMPOSIZIONE DI UN PROBLEMA
Sappiamo che un programma è un algoritmo scritto in un linguaggio comprensibile al calcolatore
Un problema può essere talvolta scomposto in parti, che possono essere risolte in maniera indipendente per ottenere una soluzione al problema di partenza
Un programma quindi può essere suddiviso in diverse parti (sottoprogrammi) ognuna delle quali risolve un sottoproblema.
13
FUNZIONI E PROCEDURE
Un sottoprogramma è un algoritmo per la soluzione di un sottoproblema scritto in un linguaggio di programmazione
Sottoprogrammi che restituiscono un risultato parziale tramite l’istruzione return prendono il nome di funzioni
Sottoprogrammi che prevedono solo l’esecuzione di un blocco di istruzioni senza l’esplicita restituzione di un risultato si chiamano procedure
14
PROCEDURA DEFINIZIONE
Sottoprogramma che, attivato dall’apposita istruzione di chiamata nel programma principale, svolge le azioni in esso specificate allo scopo di risolvere il problema per il quale e’ stato realizzato.Una procedura è individuata da un nome ed è composta da un Una procedura è individuata da un nome ed è composta da un insieme di istruzioni. Essa può essere chiamata da un punto insieme di istruzioni. Essa può essere chiamata da un punto qualsiasi del programma principale tutte le volte che si desideraqualsiasi del programma principale tutte le volte che si desidera
Utilità:Migliorano la leggibilità, la revisione e la correzione dei programmiRaggruppano le istruzioni che devono essere eseguite più volteRiutilizzo in altri programmi 15
ESEMPIO: CALCOLO DELLA MEDIA
Problema:Problema: chiedere all’utente 3 interi, calcolarne la media aritmetica, e stamparla su schermo
Il problema può essere scomposto nei seguenti sottoproblemi: richiesta numeri calcolo media stampa del risultato
16
FUNZIONI E PROCEDURE PER IL CALCOLO DELLA MEDIA
Modelliamo come funzione il sottoprogramma per: calcolo media
Risolviamo il seguente sottoproblema per mezzo di una procedura: stampa del risultato
La scrittura di questi sottoprogrammi in riferimento allo stesso programma principale (main) riflette il fatto che essi sono parte della soluzione a un unico problema
17
FUNZIONE: ESEMPIO
float media (int a, int b, int c){int somma = a + b + c;float risultato = somma/3;return risultato;
}
tipo del risultato restituito
tipo del risultato restituito
nome della
funzione
nome della
funzione
lista dei tipi e dei nomi dei parametri
formali
lista dei tipi e dei nomi dei parametri
formali
inizio del blocco di
istruzioni della funzione
inizio del blocco di
istruzioni della funzione
fine del blocco di istruzioni
della funzione
fine del blocco di istruzioni
della funzione
istruzione return con cui si conclude
l’esecuzione della funzione e si restituisce il
risultato
istruzione return con cui si conclude
l’esecuzione della funzione e si restituisce il
risultato 18
PROCEDURA: ESEMPIO
void stampa(float m){cout << “La media è: ” << m << “\n”;
}
non c’è alcun risultato restituito dal
sottoprogramma, quindi il tipo del risultato è void
(vuoto)
non c’è alcun risultato restituito dal
sottoprogramma, quindi il tipo del risultato è void
(vuoto)
non c’è alcun risultato da restituire, e infatti il blocco
di istruzioni non include una istruzione return
non c’è alcun risultato da restituire, e infatti il blocco
di istruzioni non include una istruzione return
19
USO DELLA FUNZIONE E DELLA PROCEDURA NEL PROGRAMMA FINALE…float media (int a, int b, int c){
int somma = a + b + c;float risultato = somma/3;return risultato;
}void stampa(float m){
cout << “La media è: ” << m << “\n”;}int main(){
int x,y,z;float r;cout << “inserisci 3 numeri:\n”;cin >> x >> y >> z;r = media(x,y,z);stampa(r);…
}
il risultato restituito dalla funzione va
salvato in una variabile
il risultato restituito dalla funzione va
salvato in una variabile
l’esecuzione di una procedura, invece, non prevede alcun risultato
se non l’effetto delle istruzioni che la
compongono
l’esecuzione di una procedura, invece, non prevede alcun risultato
se non l’effetto delle istruzioni che la
compongono 20
PASSAGGIO DEI PARAMETRI
Nell’esempio precedente, a, b, e c sono i parametri formali della funzione media, a cui, al momento della chiamata della funzione nel main, vengono associati i valori dei parametri attuali x, y, e z
Tale corrispondenza è posizionale: ad a viene associato il valore di x perché sono entrambi i primi della lista, e così via
Dei parametri attuali occorre indicare solo il nome, dei formali, invece, è necessario indicare il nome ed il tipo.
21
PASSAGGIO DI PARAMETRI PER VALORE Il passaggio del valore di x ad a consiste, di
fatto, nella creazione di una variabile temporanea con lo stesso valore di x che viene usata nelle istruzioni della funzione al posto di a
Per tutta l’esecuzione della funzione, la variabile x, quindi, non viene minimamente modificata: al termine della funzione sarà rimasta come prima
22
POSSIBILE PROBLEMAA volte, il fatto che un parametro attuale non subisca modifiche da parte della funzione può non essere ciò che desideriamo. Ad esempio:
#include <iostream>
using namespace std;
void azzera(int n) {
n=0;
cout << "stampa il valore della procedura= " <<n <<"\n";
}
int main(){
int x;
cout <<"inserisci il valore di X: \n";
cin>>x;
azzera(x);
cout<< "stampa il valore del main= " <<x<<"\n";
system(" pause");
return(0);
} 23
in questo caso la X non viene azzeratain questo caso la X non viene azzerata
PASSAGGIO DI PARAMETRI PER INDIRIZZO
Si ha questo tipo di passaggio quando alla funzione non è fornita una copia del valore del parametro attuale (come nel passaggio per valore) bensì l’indirizzo della cella di memoria contenente il parametro attuale.
In questo modo, la funzione non esegue le sue istruzioni su una copia, ma direttamente sul parametro attuale.
24
ESEMPIO
#include <iostream>
using namespace std;
void azzera(int &n) {
n=0;
cout << "stampa il valore della procedura= " <<n <<"\n";
}
int main(){
int x;
cout <<"inserisci il valore di X: \n";
cin>>x;
azzera(x);
cout<< "stampa il valore del main= " <<x<<"\n";
system("pause");
return(0);
}
il simbolo & indica che il passaggio del parametro
è per indirizzo
il simbolo & indica che il passaggio del parametro
è per indirizzo
questa volta la variabile x è veramente azzerata e su schermo compare ‘0’
questa volta la variabile x è veramente azzerata e su schermo compare ‘0’
25
PASSAGGIO DI PARAMETRI STRUTTURATI
Attenzione: nel linguaggio C++, se un parametro è un dato strutturato (ad esempio: un array), viene sempre passato per indirizzo, per risparmiare la memoria che verrebbe occupata da una copia del parametro attuale
Data questa regola, nella scrittura della lista dei parametri formali di un sottoprogramma si omette il simbolo ‘&’ quando trattiamo gli array
26
DEFINIZIONE ARRAY(1)
Un array può essere definito come una "collezione organizzata di oggetti". Il concetto di "collezione" implica che tali oggetti siano dello stesso tipo, un array in C++ è una collezione di variabili dello stesso tipo.
"Organizzata" significa che è possibile identificare univocamente tutti gli oggetti dell'array in modo preciso; questo in C++ viene fatto tramite l'uso di indici numerici che, in un array di dimensione N, vanno da 0 ad N-1.
27
DEFINIZIONE DI ARRAY(2)
Collezione finita di N variabili dello stesso tipo, ognuna identificata da un indice compreso tra 0 e N-1, dove N è la dimensione dell’array
Gli array sono sequenze di variabili dello stesso tipo, posizionate consecutivamente nella memoria. Questo significa, ad esempio, che possiamo memorizzare 5 valori di tipo int senza bisogno di dichiarare cinque diverse variabili. Per fare questo è sufficiente dichiarare un array di cinque elementi di tipo int.
28
DICHIARAZIONE ARRAY
Vediamo come è possibile dichiarare un array:int myarray[10] ; int myarray[10] ;
Come si può notare un array viene dichiarato mettendo il nome della variabile (myarray) e, tra parentesi quadre, la cifra che identifica il numero di elementi dello stesso tipo (int) e quindi la dimensione dell'array.
29
ARRAY COME PARAMETRI
In particolare, quando un array viene passato come parametro, l’informazione che il sottoprogramma riceve è solo l’indirizzo della prima cella dell’array
Sarà cura del programmatore aggiungere un altro parametro che indichi la dimensione dell’array in modo che il sottoprogramma possa eseguire le istruzioni sull’array in maniera corretta
30
ESEMPIO
int somma_valori (int v[], int dim){int i;int somma = 0;for (i = 0; i < dim; i++)
somma = somma + v[i];return somma;
}int main(){
int vettore[10];int s;…s = somma_valori(vettore, 10);cout << “la somma dei valori dell’array e’: ” << s << “\n”;…
}
il parametro è un array di int e la sua dimensione è un parametro separato
il parametro è un array di int e la sua dimensione è un parametro separato
nel parametro attuale viene specificato solo il
nome dell’array
nel parametro attuale viene specificato solo il
nome dell’array
31
ESEMPIO COMPLETO (SOMMA VALORI DI UN VETTORE )#include <iostream>
using namespace std;
int somma_valori (int v[], int dim){
int i; int somma = 0;
for (i = 0; i < dim; i++)
somma = somma + v[i];
return somma;
}
int main(){
int vettore[5], s, i;
cout <<" Inserisci il vettore \n";
for (i=0; i<5; i++) {
cout<< "inserisci l'elemento di indice "<< i<< " del vettore:";
cin >> vettore[i];
cout<<"\n"; }
s= somma_valori(vettore, 5);
cout << "la somma dei valori dell' array e': " << s << "\n";
system(" pause " );
return 0;
}
32