Unità G2
Scomposizione funzionale
Obiettivi
•
•
•
•
•
•
•
•
•
•
•
Comprendere il concetto di programmazione modulare
Conoscere procedure e funzioni
Comprendere il concetto di visibilità delle variabili
Conoscere il concetto di funzione parametrica
Conoscere le tecniche di passaggio di parametri
Conoscere il significato di ricorsività
Conoscere il significato di conversione di tipo
Essere in grado di progettare procedure e funzioni
Essere in grado di effettuare il passaggio di parametri per valore
e per riferimento
Essere in grado di realizzare funzioni ricorsive
Essere in grado di effettuare la conversione di tipo
Progettazione modulare
• La difficoltà nell’affrontare un problema e nel descrivere i metodi
di risoluzione è proporzionale alla sua dimensione.
• La tecnica dei raffinamenti successivi suggerisce di
scomporre il problema in problemi più semplici (sottoproblemi)
• … e di applicare anche a questi sottoproblemi la stessa tecnica
fino ad ottenere problemi facilmente risolvibili
• Questa tecnica è definita top-down:
– Si parte da una visione globale del problema
(alto livello di astrazione) [top]
– Poi si scende nel dettaglio dei sottoproblemi
diminuendo il livello di astrazione [down]
• Viene fornita inizialmente una soluzione del problema che non si
basa però su operazioni elementari, ma sulla soluzione di
sottoproblemi
Un semplice esempio
• Problema: si vuole
conoscere il costo per
la verniciatura di tre
pannelli
– Dati di input:
dimensione dei pannelli
costo della vernice al
mq
– Dato di output: costo
della vernice necessaria
per completare l’opera
Pannello 2
Pannello 1
Pannello 3
Top-down
Moltiplicare l’area
Per il costo al mq
della vernice
Calcolare l’area dei
pannelli
Calcolare l’area del
quadrato
(primo pannello)
Calcolare l’area del
triangolo
(secondo pannello
Calcolare l’area del
terzo pannello
Calcolare l’area del
rettangolo
(del terzo pannello)
Calcolare l’area del
triangolo
(del terzo pannello)
Livello di astrazione
Livello di complessità
Costo complessivo
La scomposizione in sottoproblemi
• Se il sottoproblema è semplice allora viene risolto,
viene cioè scritto l’algoritmo di risoluzione
• Se il sottoproblema è complesso viene riapplicato lo
stesso procedimento scomponendolo in
sottoproblemi più semplici
• Diminuisce il livello di astrazione
(si affrontano problemi sempre più concreti)
• Diminuisce il livello di complessità
(i sottoproblemi devono essere più semplici del
problema che li ha originati)
• Fino ad arrivare alla stesura di tutti gli algoritmi
necessari
Moduli
• modulo = codice di implementazione dell’algoritmo di
risoluzione di un sottoproblema
• Si parla quindi di progettazione e di programmazione
modulare
• Introduzione di una nuova complessità: l’interazione tra i
moduli; perché il problema sia risolto nella sua interezza i
moduli devono infatti necessariamente comunicare tra loro.
• Perché questa nuova complessità sia governabile i moduli
devono essere il più possibile indipendenti l’uno dall’altro e le
interazioni definite da regole semplici e chiare.
Procedure
• Gli strumenti messi a disposizione dai vari linguaggi
per la programmazione modulare sono le procedure
e le funzioni, per questa ragione si parla di
scomposizione funzionale.
• La procedura racchiude il codice necessario alla
soluzione di un sottoproblema (modulo)
• Individuiamo due fasi:
– Dichiarazione della procedura: fase in cui viene definito il
suo nome e l’insieme delle istruzioni che la compongono
– Esecuzione (chiamata) della procedura: fase in cui vengono
eseguite le istruzioni che la compongono
Dichiarazione e definizione di
procedura
• E’ la fase in cui viene definito il nome
(<NomeProcedura>) e l’insieme delle
istruzioni
• Pseudolinguaggio
Procedura <NomeProcedura>
<istruzioni>
<…>
Fineprocedura <NomeProcedura>
• Linguaggio C
<NomeProcedura> ()
{
<istruzioni>
<…>
}
Esecuzione (chiamata della procedura)
• In qualunque punto del programma può essere
invocata (chiamata) la procedura
• La chiamata è inserita nel programma mediante una
istruzione composta dal nome della procedura
• La chiamata provoca l’interruzione momentanea
dell’esecuzione del programma, l’esecuzione del
codice interno alla procedura e la ripresa poi del
programma dall’istruzione successiva alla chiamata
• Nel programma è possibile chiamare più volte una
procedura
chiamata
ritorno
Procedura
Programma
chiamata
ritorno
Un problema d’esempio
• Problema:
Per la valutazione di una prova scritta viene
fornito il numero degli studenti ed il voto
ottenuto da ognuno di questi.
Viene controllato che ogni voto sia
ammissibile (non sono ammessi voti minori di
0 e maggiori di 10) poi viene calcolata la
valutazione media
• Input: numero studenti, voti degli studenti.
• Output: voto medio
Algoritmo VotoMedio
/* Richiesta voti degli studenti */
Per s da 1 a numeroStudenti
/* Procedura che visualizza un messaggio di errore */
Ripeti
// dichiarazione e definizione della procedura
Scrivi("Voto studente n. ", s);
Procedura messaggioErrore
Leggi(voto);
Scrivi("Errore nell'immissione di un dato")
Scrivi("Immetterlo di nuovo. Corretto per favore!")
FineProcedura messaggioErrore
Se (voto<0 || voto>10) Allora
messaggioErrore
// chiamata della procedura
Altrimenti
sommaVoti<-sommaVoti+voto
voto Di Tipo Intero
//voto di uno studente
sommaVoti Di Tipo Reale
//somma dei voti
numeroStudenti Di Tipo Intero
//numero degli studenti
s Di Tipo Intero
//variabile di ciclo
Ripeti
Scrivi("Quanti studenti compongono la classe: ")
FineSe
Finquando ( voto<0 || voto>10 )
FinePer
Scrivi("Il voto medio ottenuto e' ",
sommaVoti/numeroStudenti);
Leggi(numeroStudenti)
Se (numeroStudenti<=0) Allora
messaggioErrore
// chiamata della procedura
FineSe
Finquando (numeroStudenti<=0)
sommaVoti<-0;
//inizializzazione
FineAlgoritmo VotoMedio
/* Voto medio */
/* Richiesta voti degli studenti */
#include <stdio.h>
for(s=1; s<=numeroStudenti; s++)
{
/* Funzione che visualizza un messaggio di errore */
do
// dichiarazione e definizione della procedura
{
messaggioErrore()
printf("Voto studente n. %d: ", s);
{
scanf("%d", &voto);
printf("\nErrore nell'immissione di un dato\n");
if(voto<0 || voto>10)
printf("Immetterlo di nuovo. Corretto per
favore!\n\n");
messaggioErrore();
// chiamata della procedura
else
}
sommaVoti+=voto;
}
main()
while(voto<0 || voto>10);
{
}
int voto;
//voto di uno studente
float sommaVoti;
//somma dei voti
printf("Il voto medio ottenuto e'
sommaVoti/numeroStudenti);
int numeroStudenti;
//numero degli studenti
}
int s;
//variabile di ciclo
do
{
printf("Quanti studenti compongono la classe: ");
scanf("%d", &numeroStudenti);
if(numeroStudenti<=0)
messaggioErrore();
// chiamata della procedura
}
while (numeroStudenti<=0);
sommaVoti=0;
//inizializzazione
%f\n",
/* Voto medio */
/* Richiesta voti degli studenti */
#include <iostream.h>
for(s=1; s<=numeroStudenti; s++)
#include <conio.h>
{
do
/* Funzione che visualizza un messaggio di errore */
{
// dichiarazione e definizione della procedura
cout<<"Voto studente n. "<<s<<" ";
messaggioErrore()
cin>>voto;
{
if(voto<0 || voto>10)
cout<<endl<<"Errore nell'immissione di un dato"<<endl;
messaggioErrore();
cout<<endl<<"Immetterlo di nuovo. Corretto per favore!";
// chiamata della procedura
else
}
sommaVoti+=voto;
}
main()
while(voto<0 || voto>10);
{
}
int voto;
//voto di uno studente
float sommaVoti;
//somma dei voti
int numeroStudenti;
//numero degli studenti
int s;
//variabile di ciclo (studente)
do
{
cout<<"Quanti studenti compongono la classe: ";
cin>>numeroStudenti;
if(numeroStudenti<=0)
messaggioErrore();
// chiamata della procedura
}
while (numeroStudenti<=0);
sommaVoti=0;
//inizializzazione
cout<<"Il voto medio ottenuto e'
"<<sommaVoti/numeroStudenti;
getch();
}
Riusabilità del codice
• Identiche porzioni di codice sono spesso utilizzate
più volte all’interno di un programma
• La duplicazione pone due tipi di problemi:
– Aumento della lunghezza del codice e quindi minore
leggibilità
– Difficoltà nell’apportare modifiche che devono essere
effettuate in tutte le copie del codice
• Con le procedure si evita di duplicare parti del codice
sorgente, quando si chiama o invoca una procedura
si esegue il codice corrispondente. A ogni nuova
chiamata il suo codice è eseguito nuovamente.
Scambio di dati fra programma e procedura
• Nell’esempio precedente la procedura
messaggioErrore non scambiava nessun
dato con il programma chiamante
• Molto spesso si rende necessario uno
scambio di dati fra il programma e la
procedura e fra la procedura e il programma
chiamante
• I linguaggi di programmazione offrono vari
metodi per realizzare questo scambio
Variabili globali
• Il metodo più semplice per scambiare
informazioni è l’uso di uno spazio di
memoria comune.
• La visibilità di una variabile definisce le parti
del programma in cui questa è utilizzabile
• Una variabile locale è visibile solo all’interno
di una procedura
• Una variabile globale è visibile in tutto il
programma
Variabili locali in linguaggio C
• Avrete notato che la struttura di un programma C
prevede un main che ha la stessa struttura di una
procedura
• In effetti main è una procedura particolare, la
procedura principale
• Ogni variabile dichiarata all’interno di una procedura
è locale e visibile solo all’interno di questa
• Ogni variabile dichiarata esternamente alle procedure
di un programma è globale e quindi visibile in ogni
punto
Un esempio di scambio di dati
• Riprendiamo un problema affrontato
nell’unità E1: determinare se un numero
è primo
• Il procedimento utilizzato cerca il
minimo divisore intero maggiore di 1 del
numero, se è uguale al numero stesso
allora il numero è primo.
/* Controllo se un numero è primo */
#include <stdio.h>
int numero;
//numero da analizzare (variabile globale)
int divisore;
//divisore trovato maggiore di 1 (globale)
/* Procedura che individua il piu' piccolo divisore maggiore di 1 */
// dichiarazione e definizione della procedura
divisoreMaggiore1()
{
int resto;
//variabile locale
divisore = 1;
do
main()
{
divisore=divisore+1;
{
printf("Immetti un numero intero positivo: ");
resto = numero % divisore;
}
scanf("%d", &numero);
while(resto!=0);
divisoreMaggiore1();
if(divisore==numero)
}
printf("%d e' un numero primo\n", numero);
else
printf("%d non e' un numero primo\n", numero);
}
/* Controllo se un numero è primo */
#include <iostream.h>
#include <conio.h>
int numero;
//numero da analizzare (variabile globale)
int divisore;
//divisore trovato maggiore di 1 (globale)
/* Procedura che individua il piu' piccolo divisore maggiore di 1 */
// dichiarazione e definizione della procedura
divisoreMaggiore1()
{
int resto;
//variabile locale
divisore = 1;
do
main()
{
{
divisore=divisore+1;
cout<<"Immetti un numero intero positivo: ";
resto = numero % divisore;
cin>>numero;
}
divisoreMaggiore1();
while(resto!=0);
if(divisore==numero)
cout<<numero<<" e' un numero primo";
}
else
cout<<numero<<" non e' un numero primo";
}
La memoria dell’esempio
Memoria globale
Memoria main
numero
divisore
Memoria divisoreMaggiore1
resto
Ad ogni attivazione delle procedura viene allocata nuova memoria per i dati
locali di questa. Al termine della procedura la memoria locale “scompare”.
Le funzioni
• Una funzione svolge, come la procedura, un
compito ma, a differenza di questa, restituisce
un valore
• Nella dichiarazione di una funzione è
necessario specificare il tipo del valore
ritornato
• Nella definizione è necessario utilizzare una
specifica istruzione che fa terminare
l’esecuzione della funzione e specifica il
valore ritornato
Dichiarazione e definizione di funzione
• Pseudolinguaggio
Funzione <NomeFunzione> Di Tipo <TipoRisultato>
<istruzioni>
Ritorna <Espressione>
FineFunzione <NomeFunzione>
• Linguaggio C
<tipoFunzione> <NomeFunzione> ()
{
<istruzioni>
return <Espressione>
}
Un esempio
• La funzione cubo di tipo intero restituisce il valore
della variabile globale intera x elevato al cubo
• Pseudolinguaggio
Funzione cubo Di Tipo Intero
c Di Tipo Intero
c  x * x * x
Ritorna c
FineFunzione cubo
• Linguaggio C
int cubo ()
{
int c;
c = x * x * x;
return c;
}
Chiamata di funzione
• La chiamata di una funzione è sempre
inserita in una espressione e provoca
l’esecuzione della funzione e l’utilizzo
del valore di ritorno
• Esempi:
int potenza;
potenza = cubo();
…
printf(”%d al cubo vale %d”,x,cubo());
potenza = cubo() * x;
/* Uso della funzione cubo */
#include <stdio.h>
int x;
//variabile globale
/* Funzione che restituisce il valore di x elevato al cubo */
// dichiarazione e definizione della funzione
int cubo()
{
int c;
c=x*x*x;
return c;
}
main()
{
printf("Immetti il valore: ");
scanf("%d", &x);
printf(”%d al cubo vale %d”,x,cubo());
}
Dichiarazione e definizione
• In linguaggio C è possibile separare le due
fasi di dichiarazione e definizione di funzione
• Nella dichiarazione viene specificato solo il
nome della funzione ed il suo tipo
• Nella definizione viene inoltre specificato il
corpo della funzione
• La dichiarazione deve sempre precedere
ogni chiamata della funzione
Indipendenza funzionale
• L’uso delle variabili globali vincola l’uso delle
procedure e funzioni ad essere utilizzate in contesti
particolari
• La funzione cubo presentata in precedenza
restituisce il cubo della variabile x
• In uno stesso programma può risultare utile utilizzare
la funzione per calcolare il cubo di differenti valori, in
questo caso è necessario “spostare” questi valori
nella variabile x prima di richiamare la funzione
• La funzione può essere utilizzata anche all’interno di
un altro programma in cui potrebbe essere già
presente una variabile x utilizzata per memorizzare
dati di diverso tipo
I parametri
• I parametri permettono di rendere indipendente la
procedura o la funzione dal contesto in cui viene
inserita
• La procedura o funzione viene definita utilizzando i
parametri formali
• Al momento dell’esecuzione vengono poi specificati i
parametri attuali che vengono passati al
sottoprogramma
• I parametri vengono specificati in fase di
dichiarazione
Passaggio dei parametri per valore
• Al momento dell’esecuzione del sottoprogramma il valore dei
parametri attuali viene assegnato ai parametri formali
• La sintassi della dichiarazione di procedura viene quindi
ampliata per specificare i parametri.
• Possono essere presenti più parametri di vario tipo
• Pseudolinguaggio
Procedura <NomeProcedura> (<par1> di Tipo <tipoPar1>,…)
<istruzioni>
<…>
Fineprocedura <NomeProcedura>
• Linguaggio C
<NomeProcedura> (<tipoPar1> <par1>, …)
{
<istruzioni>
<…>
}
Un esempio di procedura con parametri
• Procedura che visualizza i divisori di un numero intero
void divisori(int n)
//procedurra che visualizza i divisori di n
{
int divisore; //variabile locale - possibile divisore di n
for (divisore=1;divisore<=n;divisore++)
//per tutti i valori fra 2 e
n-1
if (n%divisore==0)
//se ho trovato un divisore
cout<<divisore<<endl;
//visualizza il divisore trovato
}
• La procedura opera formalmente sul parametro n
• Al momento della chiamata viene specificato il valore del
parametro attuale che viene assegnato al parametro formale
– divisori(10); //visualizza i divisori di 10
– divisori(k); //visualizza i divisori di k
// (k deve essere dichiarata come variabile int)
– divisori(k+2); //come parametro attuale è possibile utilizzare
// una qualunque espressione di tipo int
Una funzione con due parametri
/* Funzione che ritorna la potenza con base base ed esponente esp
base : float base della potenza
esp
: int esponente (positivo)
*/
float potenza(float base, int esp)
{
float prod=1;
for (int i=1;i<=esp;i++)
prod=prod*base;
return prod;
}
//locale : per il calcolo della potenza
// esp volte
Esecuzione della funzione
float b;
//input valore che rappresenta la base
int e;
//input valore che rappresenta l'esponente
cout<<"Inserire il valore della base ";
cin>>b;
cout<<"Inserire il valore dell'esponente ";
cin>>e;
cout<<b<<" elevato a "<<e<<" = "<<potenza(b,e)<<endl;
cout<<"Il quadrato di "<<b<<" = "<<potenza(b,2)<<endl;
cout<<"10 elevato a "<<e<<" = "<<potenza(10,e)<<endl;
cout<<"Il cubo del doppio di "<<b<<" = "<<potenza(2*b,3)<<endl;