La rappresentazione degli algoritmiPer indicare le azioni svolte in un determinato algoritmo si utilizzano spesso due formalismi: i diagrammi di flusso (detti anche diagrammi a blocchi o Flow Chart) che sono quelli che voi conoscete e la pseudocodifica. Tali formalismi possono essere usati insieme oppure in alternativa.

Per indicare le azioni presenti negli algoritmi si può utilizzare la lingua italiana che è un linguaggio naturale. Questo linguaggio però pur essendo molto utile per chiarire le idee sul problema, non si presta bene a una precisa descrizione dell'algoritmo. Il linguaggio naturale, infatti, contiene sinonimi, ambiguità che violerebbero una delle regole degli algoritmi che devono essere non ambigui.

Se dobbiamo affermare che uno studente è molto volenteroso possiamo anche utilizzare gli aggettivi: zelante, operoso, attivo, alacre, sollecito, dinamico, solerte ecc. Inoltre, se proviamo a leggere la frase:

"Ieri sera ho visto Giuseppe con un conoscente" vediamo che può essere interpretata in due modi diversi. Vale a dire:

"Ieri sera ho visto Giuseppe che era in compagnia di un conoscente" oppure:

"Ieri sera ho visto Giuseppe mentre ero in compagnia di un conoscente".

Per evitare tali ambiguità, insite in un linguaggio naturale, per la descrizione degli algoritmi da codificare si utilizzano dei particolari “pseudolinguaggi”, detti così in quanto non sono direttamente comprensibili da un calcolatore (come lo sono invece i linguaggi di programmazione). Il vantaggio principale di tali pseudolinguaggi è che possono essere facilmente trasformati, senza ambiguità per un programmatore esperto, in un programma eseguibile mediante codifica in un particolare linguaggio di programmazione.

Consideriamo il seguente algoritmo scritto in un possibile pseudolinguaggio (si parla anche di pseudocodifica dell'algoritmo)

Algoritmo: PrelievoDalBancomat (in pseudocodice).

INIZIO

1 SE il bancomat è in servizio

ALLORA

2 Introdurre la carta nel lettore

3 Digitare il codice segreto

4 SE il codice è corretto

ALLORA

5 Digitare l'importo da prelevare

6 Ritirare le banconote

7 Ritirare la carta dal bancomat

ALTRIMENTI

8 Operazione terminata

FINESE

ALTRIMENTI

1

9 Cercare un altro bancomat

FINESE

FINE

Osservando le righe precedenti notiamo che vi è una descrizione formale dell'algoritmo detta pseudocodice perché, pur essendo strutturata come un codice scritto in un linguaggio di programmazione, si serve di un linguaggio molto vicino a quello naturale, detto pseudolinguaggio o linguaggio di progetto. L'attività di scrittura in tale pseudolinguaggio prende il nome di pseudocodifica. Tale attività è una fase intermedia che si pone tra la fase di analisi dei problema e quella di codifica in un vero e proprio linguaggio di programmazione.

Scopo principale della pseudocodifica è di portare il risolutore a esprimere le proprie istruzioni in una forma naturale, utilizzando frasi ed espressioni elementari della lingua italiana. Ciò permette di concentrarsi sulla risoluzione logica del problema, invece che sulla forma e sui vincoli da rispettare nella sua enunciazione in un linguaggio di programmazione (in pratica ci si concentra più sul COSA fare piuttosto che sul COME fare, regola aurea del progettista)

Il nostro pseudolinguaggio

Per specificare gli algoritmi senza far riferimento a nessun linguaggio (di programmazione) particolare utilizzeremo uno pseudolinguaggio che rispetta le seguenti regole

1 Le parole chiave, o parole riservate (keywords in inglese), saranno scritte in MAIUSCOLO e non potranno essere usate come identificatori (ricordo che gli identificatori sono i nomi delle variabili o funzioni scelti dal programmatore)

2 gli identificatori saranno scritti in generale in minuscolo e sempre senza spazi. Solo in alcuni casi useremo le maiuscole e precisamente

2.1 quando usiamo identificatori costituiti da più parole unite (gli identificatori sempre senza spazi) allora le parole dopo la prima potranno iniziare con la maiuscola come in laMiaVariabile. L'alternativa a tale forma sarà la_mia_variabile. Tutto ciò per una migliore leggibilità dell'algoritmo

2.2 Per le funzioni o procedure useremo l'iniziale maiuscola e poi saranno sempre seguite dalle parentesi tonde aperte e chiuse (anche nel caso non vi siano parametri)

Quando invece dobbiamo descrivere la sintassi di una istruzione (cioè le regole per formare una istruzione valida) procederemo in questo modo

1) le parole racchiuse tra parentesi angolari <> rappresentano le categorie sintattiche, ossia elementi generali del linguaggio che devono essere ulteriormente specificati. Ad esempio a←b <variabile> ← <espressione> può essere a←c+2*d c ← 0

2) le parentesi quadre [] indicano l'opzionalità, ossia i blocchi in esse racchiusi possono anche essere non presenti

3) i blocchi separati da una | (carattere chiamato pipe si legge “paip”) possono essere usati in alternativa (o si usa l'uno o l'altro ma mai insieme)

2

4) le parentesi graffe indicano possibilità di ripetizione, ossia i blocchi in essa racchiusi possono essere ripetuti più volte

La progettazione di algoritmi complessi

L'approccio Top-Down

Prerequisiti specifici

CONOSCENZE ABILITÀ

Algoritmi Saper realizzare algoritmi strutturati

Conoscere le strutture di controllo (sequenza – selezione - iterazione)

Saper utilizzare consapevolmente le variabili

Obiettivi specifici

CONOSCENZE ABILITÀ

Conoscere la definizione di programma e sottoprogramma

Saper suddividere un problema in sottoproblemi

Conoscere le forme per dichiararee chiamare un sottoprogramma

Saper definire e riconoscere ambienti locali e globali

Conoscere i concetti di top-down e bottom-up Saper implementare procedure e funzioni

Conoscere i parametri attuali e formali

Conoscere le procedure e funzioni

Conoscere l'ambiente e le regole di visibilità delle variabili

Conoscere la definizione di ricorsione

1 II ruolo della metodologia top-down e e bottom-up

Finora abbiamo posto e risolto problemi privi di grosse difficoltà. Questo per acquisire una buona padronanza nelle fasi di analisi del problema e nella ricerca del metodo risolutivo. Nella realtà, però, i problemi non sono tutti così semplici. Quando un problema appare immediatamente complesso, per risolverlo possiamo individuare e analizzare i sottoproblemi più semplici che lo compongono, oltre alle loro interrelazioni. In questo modo, è possibile articolare la progettazione dell'algoritmo complessivo in una serie di algoritmi più semplici, che verranno poi opportunamente assemblati.

La programmazione, in effetti, non è solo un processo di ideazione e formulazione di algoritmi:

3

esige attenzione ai minimi dettagli e l'adozione di opportune tecniche di analisi dei problemi da risolvere. Per questo, una buona metodologia di progettazione è quella che risolve il problema per passi: partendo da un'analisi generale, si focalizza l'attenzione su singoli punti fondamentali che lo compongono, riducendo così le difficoltà.

Tale metodologia di natura gerarchica prende il nome di top-down, ossia "dall'alto verso i basso". Gli aggettivi alto e basso si riferiscono al livello di dettaglio o astrazione. Il livello più alto (top) è quello della procedura generale di risoluzione del problema, chiamata problema principale, in cui si individuano i suoi passi fondamentali chiamati sottoproblemi.

Ciascun sottoproblema viene dettagliato a parte e, se complesso, può essere a sua volta scomposto in ulteriori sottoproblemi più semplici. Si giunge così all'analisi e alla risoluzione di tanti problemi elementari tramite algoritmi descritti a livello programmabile (il più basso è down), le cui relazioni sono ricavate dalla descrizione a livello superiore. In sintesi, si scende dal generale al particolare mediante affinamenti successivi.

La tecnica top-down, quindi, nasce come tecnica di analisi dei problemi e non come tecnica di progettazione: il risolutore, infatti, utilizza tale metodologia per affrontare agevolmente il processo risolutivo del problema.

All'atto dell'implementazione, poi, il programmatore deciderà se implementare singolarmente i vari sottoproblemi, mediante i sottoprogrammi che vedremo a breve, o se accorparne alcuni e scomporne altri

Per scomporre un problema in tanti sottoproblemi funzionali ci si sofferma su COSA debba essere fatto e NON SUL COME, che con tale metodologia viene affrontato è soltanto all'ultimo livello.

Questo modo di procedere è molto importante: all'inizio mi devo solo soffermare su COSA devo fare senza preoccuparmi dei dettagli, che mi distraggono dal problema principale. Una volta che ho

4

Problema

Sottoproblema1 Sottoproblema2 Sottoproblema3

Sottoproblema3.1Sottoproblema3.2

Sottoproblema3.2.1Sottoproblema3.1.1 Sottoproblema3.1.2

capito bene che cosa devo fare mi posso concentrare sui singoli sottoproblemi uno alla volta.

La metodologia bottom-up, ossia "dal basso verso l'alto", privilegia, invece, l'aspetto esecutivo rispetto a quello funzionale, procedendo dal particolare verso il generale. Il metodo bottom-up è una strategia induttiva e consente di concentrarsi subito sui punti cardine del problema che, però, sono molto difficili da individuare inizialmente. Proprio per questo motivo è meno adatta per la progettazione di software. I due approcci non sono comunque in contrasto tra loro e spesso coesistono senza nessun problema.

I sottoprogrammi

Esiste una possibilità di cui non abbiamo ancora parlato:

si può realizzare un sottoprogramma per ogni sottoproblema non più scomponibile.

Unendo, alla fine, tutti i sottoprogrammi, si ottiene il programma che risolve il problema originale.

Il sottoprogramma, quindi, è una parte del programma che risolve un particolare sottoproblema.

Grazie a metodologie note con il nome di tecniche dei sottoprogrammi, è possibile suddividere il procedimento generale che risolve un problema in:

1) un sottoprogramma principale (main) che descrive globalmente il problema;

2) un insieme di sottoprogrammi che risolvono i singoli sottoproblemi.

Analizziamo il seguente problema: preparare una torta gelato al cioccolato. Realizziamo il programma principale servendoci dello pseudolinquaggio

ALGORITMO Torta

SOTTOPROGRAMMA Principale

INIZIO

Preparare la base per la torta

Preparare un gelato al cioccolato

Farcire la torta con il gelato

FINE

Tutte e tre le azioni sono piuttosto complesse e anche di interesse generale: per questi motivi conviene descriverle per mezzo di sottoprogrammi. Continuiamo l'affinamento, a partire dalla prima azione, cioè Preparare la base per la torta. Avremo:

SOTTOPROGRAMMA Preparare la base per la torta

INIZIO

Preparare l'impasto

5

Preparare la teglia

Preparare il forno

Infornare

Sfornare

FINE

L'attività Preparare l'impasto è di interesse generale, in quanto lo stesso impasto potrà essere utilizzato per molti altri tipi di torte: quindi si può descriverla, laddove fosse necessario, tramite un sottoprogramma. Le altre (da Preparare la teglia a Sfornare) sono piuttosto semplici e pertanto possono essere dettagliate immediatamente. Analogo ragionamento andrà fatto per le altre azioni descritte nell'algoritmo principale.

NOTA:

E' interessante chiedersi: quando conviene usare un sottoprogramma e quando no? Ecco la risposta

Conviene descrivere un'attività per mezzo di un sottoprogramma quando

NON Conviene descrivere un'attività per mezzo di un sottoprogramma quando

È di interesse generale Non è di interesse generale

Non è di interesse generale ma si presenta più volte nel programma

Non permette una maggiore leggibilità del programma o addirittura la complica

Pur essendo di scarso interesse generale permette una maggiore leggibilità del programma

Non garantisce un risparmio di tempo

Riepilogando esistono ottimi motivi che spingono a utilizzare i sottoprogrammi. In particolare essi:

➢ migliorano la leggibilità del programma in maniera considerevole;

➢ permettono l'astrazione. Quando il programmatore inserisce un'istruzione di chiamata di sottoprogramma, astrae dalla realtà del sottoproblema. Si disinteressa cioè, in quel momento, della sua realizzazione, perché gli interessa solo cosa fare e non come farlo;

➢ consentono di scrivere meno codice e così occupano meno memoria. Si evita, infatti, di riscrivere più volte sequenze di istruzioni identiche in punti diversi del programma;

➢ sono riutilizzabili. Molto spesso accade che il sottoproblema che stiamo per risolvere sia già stato risolto in un altro programma. Abbiamo già il sottoprogramma risolutivo: possiamo riutilizzarlo senza riscriverlo.

Per eseguire un sottoprogramma è necessario utilizzare un'apposita istruzione di chiamata del sottoprogramma, che è prevista da tutti i linguaggi di programmazione (la chiamata al sottoprogramma si chiama anche invocazione del sottoprogramma) . Nel nostro pseudocodice identificheremo tale istruzione con il nome del sottoprogramma.

6

Quando la CPU incontra un'istruzione di chiamata ad un sottoprogramma, sospende temporaneamente l'elaborazione del programma chiamante e comincia a eseguire il sottoprogramma chiamato. Terminata l'esecuzione del sottoprogramma, la CPU riprende l'esecuzione del programma, ripartendo dall'istruzione successiva a quella di chiamata.Analizziamo lo schema riportato nella figura. Quando la CPU incontra l'istruzione SP1 passa immediatamente a eseguire il sottoprogramma SP1 (freccia 1).

Durante l'esecuzione, la CPU incontra una nuova chiamata di sottoprogramma: SP2. Sospende nuovamente l'esecuzione (questa volta del sottoprogramma SP1) e passa a eseguire le istruzioni contenute nel sottoprogramma SP2 (freccia 2). Quest'ultimo viene eseguito interamente: l'ultima istruzione, ossia FINE, riporta la CPU a continuare l'esecuzione del sottoprogramma SP1 (freccia 3) dal punto in cui era stato sospeso, cioè dall'istruzione immediatamente successiva (Ist. C) a quella di chiamata (SP2). Continua, così, l'esecuzione di SP1. Alla fine, la CPU incontra l'istruzione FINE e torna a eseguire il programma chiamante (freccia 4) dall'istruzione successiva alla chiamata (SP1) partendo, quindi, dalla istruzione Ist. A. E così via.

È importante ricordare che il sottoprogramma viene caricato in memoria al momento della chiamata e, terminata l'esecuzione, viene rilasciato, liberando la memoria occupata. Occorre precisare meglio questo fatto: l'esecuzione di un sottoprogramma comporta la creazione delle variabili in esso definite (e dei parametri quando presenti) e l'esecuzione di tutte le istruzioni in esso definite ed, all'uscita del sottoprogramma tali variabili (chiamate variabili locali) verranno distrutte. Questo vale anche per i parametri passati alla funzione o alla procedura che sono equivalenti alle variabili locali da questo punto di vista.

Tale metodo di gestire la memoria da parte del sistema operativo viene detto allocazione dinamica.

Per ricordare da quale istruzione va ripresa l'esecuzione del programma chiamante dopo la fine dell'esecuzione di un sottoprogramma, la CPU si serve di un'apposita struttura dati conservata in memoria detta pila dei record di attivazione. In ogni record di attivazione vengono memorizzate alcune importanti informazioni tra cui, fondamentale, l'indirizzo della cella di memoria contenente l'istruzione che dovrà essere eseguita al rientro (cioè al termine) del sottoprogramma.

La pila, detta anche stack in inglese, è una particolare struttura dati, all'interno della quale i dati possono essere inseriti o estratti solo da un'estremità che chiamiamo, solitamente, testa della pila (vedi figura)

7

Questa particolare caratteristica permette l'estrazione dei dati nell'ordine inverso in cui sono stati inseriti: cioè l'ultimo dato inserito nella pila sarà sarà il primo a uscire. Per questo motivo, la pila è anche conosciuta come struttura LIFO (Last In First Out).

Pensate a una pila di piatti. Se dovete aggiungerne uno, lo farete appoggiandolo sull'ultimo in alto. Se dovete toglierlo, lo prenderete dalla stessa posizione: ossia l'ultimo inserito è il primo ad uscire (LIFO, Last In First Out).

In nessun caso farete una delle due azioni sulla parte bassa della fila o nel mezzo (a meno di non aver deciso di combinare un pasticcio!).

Alla luce di questi nuovi concetti, rivediamo in dettaglio l'esempio riportato nelle seguenti. I punti seguenti corrispondono a quelli dettagliati nelle figure seguenti :

1. quando la CPU esegue l'istruzione SP1, prima di dedicarsi all'esecuzione del sottoprogramma memorizza nella prima posizione libera della pila (nel nostro caso la prima) l'indirizzo dell'istruzione Ist. A (oltre ad altre informazioni di cui non ci occupiamo), dalla quale riprendere l'esecuzione al rientro da SP1;

2. compiuta la memorizzazione, la CPU passa a eseguire SP1. In questo sottoprogramma, incontra una nuova chiamata di sottoprogramma, precisamente SP2. Prima di eseguirlo, quindi, deve memorizzare l'indirizzo dell'istruzione Ist. C dalla quale riprendere dopo il rientro. A memorizzazione avvenuta, la situazione della pila sarà quella n° 2;

3. procedendo con l'esecuzione di SP2, la CPU incontra l'istruzione FINE. Per conoscere l'istruzione dalla quale riprendere l'esecuzione, la CPU analizza la pila delle attivazioni ed estrae l'indirizzo contenuto in testa (nel nostro caso l'indirizzo dell'istruzione Ist. C). Dopo l'estrazione, la situazione della pila sarà quella n° 3 e l'esecuzione riprende da Ist. C, ossia dall'istruzione riportante l'indirizzo estratto;

4. l'esecuzione continua e, a questo punto, si incontra una nuova istruzione FINE. Come al solito, la CPU estrae l'indirizzo posto in testa alla pila e riprende a eseguire dall'istruzione contrassegnata da quell'indirizzo (nel nostro caso, Ist. A). Siamo rientrati nel programma principale e lo vediamo anche dal fatto che la pila è vuota (situazione n° 4).

8

Le Procedure

La procedura è un sottoprogramma contenente le istruzioni che risolvono un determinato problema. L'esecuzione della procedura viene attivata mediante l'apposita istruzione di chiamata che in quasi tutti i linguaggi è costituita dal nome che diamo alla procedura stessa.

A differenza delle funzioni (che vedremo a breve) le procedure non restituiscono un valore ma eseguono solo delle azioni.

Queste azioni possono essere per esempio delle stampe, dei calcoli, uno scambio di variabili eccetera. Non tutti i linguaggi di programmazione prevedono espressamente le procedure, ma queste possono sempre essere “imitate” con delle funzioni che non restituiscono nulla o il cui valore di ritorno non è importante.

Per definire una procedura in pseudocodifica utilizzeremo la seguente sintassi

PROCEDURA <NomeProcedura> ([<Parametro1>,<Parametro2>,...,<ParametroN>,])

da tale sintassi si nota che essa è caratterizzata da

1) un nome che deve ricordare (possibilmente) ciò che la procedura fa e che serve per richiamarla (ossia per richiedere la sua esecuzione)

2) una lista di parametri (cioè <Parametro1>,<Parametro2>,...,<ParametroN>) che è opzionale (notate nella descrizione le [] che indicano l'opzionalità) e permette lo scambio di input e/o output tra il programma chiamante e la procedura stessa. Nel caso non vi siano parametri <NomeProcedura> va comunque seguita dalle ().

9

VB

In visual Basic le procedure sono dichiarate in questo modo

private | public Sub <nomeProcedura> ([ByRef | ByVal <Parametro1> As <TipoParametro1>, ByRef | ByVal <Parametro2> As <TipoParametro2>,..., ByRef | ByVal<ParametroN> A As <TipoParametroN>,])

quindi private o public in alternativa e così pure ByVal e ByRef che vedremo dopo cosa significano; il tipo dei parametri è opzionale.

Esempi di definizioni di intestazioni di procedure valide in VB sono

private Sub StampaReport()

public Sub StampaDatiUtente(ByVal utente)

Private Sub Ordina(ByRef a, ByRef b)

la prima è senza parametri, la seconda con un parametro e l'ultima con due parametri.

Naturalmente mancano tutte le istruzioni che fanno parte delle relative procedure, cioè quello che è chiamato il corpo delle procedure

Osserviamo che esse sono, a livello di intestazione, perfettamente identiche alle funzioni: la differenza tra le due sarà all'interno del corpo della funzione: infatti nelle procedure non ci sarà alcuna istruzione return (istruzione che restituisce un valore al programma chiamante) mentre nelle funzioni ve ne sarà almeno una.

Vediamo ora un problema in cui possiamo utilizzare una procedura per risolverlo. Il problema è il semplice problema di ordinamento crescente di due numeri interi, che utilizza, quando necessario una procedura per lo scambio del contenuto di due variabili.

Problema n°1: Scrivere un algoritmo che, dati in input due numeri, li ordini in senso crescente e poi li visualizzi.

ALGORITMO Ordinamento

PROCEDURA Scambia()

INIZIO

c ← a

a ← b

b ← c

FINE

PROCEDURA Main() #questo è il programma principale

a, b As Intero

INIZIO

SCRIVI(“Inserisci il primo numero: “)

LEGGI(a)

SCRIVI(“Inserisci il secondo numero: “)

LEGGI(b)

SE a < b ALLORA

10

SCAMBIA(a,b)

SCRIVI(“I due numeri ordinati sono: “, a,” “,b)

FINE

Vediamo ora come realizzare tale programma in VB.

Public Class Procedure'definiamo la procedura Scamba()Private Sub Scambia() 'procedura per lo scambio due variabili, senza parametri 'è importante capire che questo funziona solo se a e b sono presenti nel main program c=a a=b b=cEnd Sub

'programma principale, al cui interno richiamiamo la procedura Scambia()Private Sub cmdEsegui_click(...)...

dim a,b As Integera=inputBox("Inserisci il primo numero: "))b=inputBox("Inserisci il secondo numero: "))if a < b then

Scambia() 'chiamata alla procedura Scambia()End IfmsgBox ("i numeri ordinati sono:" & a & " " & b

End SubEnd Class

Le Funzioni

La funzione è un sottoprogramma contenente le istruzioni che risolvono un particolare sottoproblema. Quando essa è attivata da una istruzione di chiamata essa esegue le operazioni e restituisce un valore al programma chiamante. Il valore restituito dalla funzione è di solito usato come elemento di una istruzione (per esempio in una stampa o a destra di una istruzione di assegnazione sia esso solo o all'interno di una espressione)

A differenza delle procedure, quindi, le funzioni restituiscono un risultato, oltre a svolgere delle azioni; per questo motivo la funzione può essere richiamata in un'assegnazione a una variabile oppure all'interno di una generica espressione.

Per questi motivi, e anche per evitare confusione, nell'implementazione dei nostri pseudocodici utilizzeremo la nuova pseudoistruzione RITORNO <NomeVariabile> | <espressione> | <valore>. Almeno una di tali istruzioni deve essere sempre presente in una funzione.

L'intestazione della funzione che utilizzeremo nella pseudocodifica si rifà al codice VB in cui è necessario definire il tipo del valore restituito dalla funzione stessa. Differisce un po' da quella della procedura:

FUNZIONE <NomeFunzione> ([ByVal | ByRef <Par1 >, ByVal | ByRef <Par2>, ... , ByVal | ByRef <ParN>]) As <Tipo Restituito>

dove:

1) <NomeFunzione> è il nome a essa associato;

2) <Par1>, <Par2>, ... <ParN> costituiscono la lista di parametri necessari per lo scambio delle

11

informazioni con il programma chiamante. Come per le procedure, se la funzione non dovesse contenere parametri, il <NomeFunzione> va comunque seguito da una parentesi tonda aperta e da una chiusa ();

3) ByVal e ByRef si riferiscono alle modalità del passaggio dei parametri (Vedi più avanti)

4) As <Tipo Restituito> indica il tipo del valore restituito dalla funzione

Problema n° 2 Scrivere un algoritmo che, data in input una sequenza di N numeri interi chiusa dallo 0, calcoli, per ciascuno di essi, il fattoriale.

Dalla matematica sappiamo (se no ve lo sto dicendo adesso) che il fattoriale di un numero naturale N maggiore o uguale a zero, indicato con il simbolo N! (che si legge “N fattoriale”), è dato dalla seguente formula:

0! = 1

N! = N * (N - 1) * (N - 2) * ... * 2 * 1

il che significa: il fattoriale del numero 0 (zero) è pari a 1, mentre il fattoriale di un qualunque numero maggiore di 0 (zero) è pari al prodotto del numero stesso per tutti i numeri interi che lo precedono sino all'uno

Ad esempio, il fattoriale di 5 è 5! = 5 * 4 * 3 * 2 * 1= 120

il fattoriale di 4 è 4! = 4*3*2*1=24 e così via per gli altri numeri.

Passiamo all'algoritmo:

ALGORITMO CalcoloFattoriale

num As Intero Lungo

INIZIO

SCRIVI("Inserisci un numero (0 per finire))

LEGGI(num)

MENTRE num !=0 ESEGUI

SCRIVI('Il fattoriale di ", num,” e' ”, Fattoríale()) # Viene chiamata la funzione-#Fattoriale, senza parametri

SCRIVI("Inserisci un numero (0 per finire)")

LEGGI(num)

FINEMENTRE

FINE

FUNZIONE Fattoriale() As Reale Lungo

f As Reale Lungo 'qui memorizzeremo il fattoriale

i As intero 'questa è solo una variabile locale

INIZIO

f =1

i=num 'i è locale mentre Num è globale

MENTRE i >= 1 ESEGUI

12

f ← f * i

i=i-1

FINEMENTRE

RITORNO (f)

FINE

Abbiamo utilizzato una funzione di nome Fattoriale che, per ogni numero intero inserito, restituisce il suo fattoriale (anch'esso ovviamente intero, ma poiché può essere molto grande lo abbiamo indicato come reale lungo). II risultato viene restituito dalla funzione per mezzo dell'istruzione:

RITORNO(f)

dove f è la variabile reale lunga che è stata utilizzata per calcolare il fattoriale del singolo numero intero inserito. Ribadiamo che, grazie a questa pseudoistruzione, viene restituito al programma chiamante il valore della variabile f in essa calcolato.

La funzione, inoltre, può essere utilizzata nelle espressioni come una semplice variabile, ma non può mai comparire a sinistra di una istruzione di assegnazione o in un'istruzione di lettura. Ad esempio, se in un programma è stata definita la funzione di nome Prod(), l'istruzione:

Tot ← Prod() * N

risulta valida e viene interpretata come: assegna alla variabile Tot il prodotto che si ottiene dal risultato fornito dalla funzione Prod() per il valore della variabile N.

Vediamo ora di realizzare la nostra funzione in VB.

Public class Fattoriali'Definiamo la funzione FattorialePrivate Function Fattoriale() As Double 'Funzione che restituisce il fattoriale di un numero Dim f As double Dim i As Integer f=1 i=num do while i>=1 f = f *i i=i-1 Loop return fEnd Function'fine funzione Fattoriale()

'Programma principalePrivate Sub cmdCalcola_click(...) …Dim Num As Integernum=inputBox("Inserisci un numero intero positivo (0 per terminare): "))do while num <> 0 msgBox ("Il fattoriale di" & num & " è " & Fattoriale()) num=inputBox("Inserisci un numero intero positivo (0 per terminare): "))loopEnd SubAnche questa funzione è molto semplice e, come potete vedere, è stata utilizzata all'interno di una msgBox. Per ogni numero che inseriamo essa calcola il valore del del fattoriale di quel numero.

13

Ambiente locale e globale e visibilità (scope) delle variabili

Durante la realizzazione di un sottoprogramma occorre definire tutte le risorse necessarie al suo funzionamento, vale a dire il suo ambiente.

Con il termine ambiente di un sottoprogramma definiamo l'insieme delle risorse (variabili, costanti, sottoprogrammi, costanti) alle quali esso può accedere.

Per il momento, diciamo che l'ambiente è costituito:

1) Dall'ambiente locale, cioè dalle risorse dichiarate all'interno del sottoprogramma (risorse locali);

2) dall'ambiente globale, ossia dalle risorse utilizzabili da tutti i sottoprogrammi (risorse globali).

Un corretto stile di programmazione impone di minimizzare l'uso dell'ambiente globale e di privilegiare quello locale.

Quindi

Implementare un sottoprogramma significa descrivere le istruzioni contenute nel suo corpo e dichiarare (nei LDP1 che prevedono dichiarazione di variabili) o utilizzare (nei LDP tipizzati dinamicamente come python, PHP) le risorse che compongono il suo ambiente locale.

Problema n°3: Visualizzare il prodotto di due numeri interi utilizzando la sola operazione di somma.

Supponiamo di voler svolgere il prodotto di 5*3: si tratterà di sommare 3 volte 5 (ossia eseguire 5+5+5). Generalizzando, dati due numeri in input a e b, si tratterà di sommare b volte il numero a.

1 LDP: Linguaggi Di Programmazione

14

Sottoprogramma A(Z1,Z2,Z3)

Sottoprogramma B(X1,X2)

Sottoprogramma A(K1,K2)

Programma Esempio(Y1,Y2,Y3)

il sottoprogramma A VEDE (cioè ha accesso a) le sue variabili Z1, Z2, Z3 e le variabili globali Y1, Y2, Y3. NON VEDE le variabili dichiarate nei sottoprogrammi B e C.II sottoprogramma B VEDE (cioè ha accesso a) le sue variabili X1, X2 e le variabili globali Y1, Y2, Y3.NON VEDE le variabili dichiarate nei sottoprogrammi A e C.Il sottoprogramma C VEDE (cioè ha accesso a) le sue variabili K1, K2 e le variabili globali Y1, Y2, Y3.NON VEDE le variabili dichiarate nei sottoprogrammi A e B.

Nel programma principale abbiamo accesso alle variabili Y1,Y2,Y3 ed ai sottoprogrammi A(), B() e C() ma non alle variabili locali a tali sottoprogrammi

ALGORITMO Moltiplicazione

FUNZIONE Moltiplica()

'funzione che esegue la moltiplicazione di a per b usando solo somme

INIZIO

prod ← 0 'variabile locale accumulatore che conterrà il prodotto di a per b

j=1 'variabile locale di controllo del ciclo

MENTRE j <= b ESEGUI

prod ← prod + a

j ← j + 1

FINEMENTRE

RITORNO prod # restituiamo il valore di prodotto al programma chiamante ed anche il # controllo all'istruzione successiva del programma chiamante

FINE

FUNZIONE MAIN() #d'ora in poi il programma principale lo chiamiamo così

INIZIO

SCRIVI(“Inserire il primo fattore: “)

LEGGI(a)

SCRIVI(“Inserire il secondo fattore: “)

LEGGI(b)

SCRIVI(“Il prodotto di “,a, “ e “, b, ” e' “, Moltiplica()) #si attiva la funzione Moltiplica()

FINE

Le variabili a e b sono variabili globali e possono essere utilizzate da tutti i sottoprogrammi dichiarati nello stesso programma.

Le variabili prod e I, invece, sono definite all'interno della funzione Moltiplica() e possono essere utilizzate solo da essa. Vengono quindi utilizzate solo durante l'esecuzione del sottoprogramma: sono, pertanto, variabili locali.

SCELTA DELLE VARIABILI LOCALI

La scelta delle variabili locali non deve essere affidata al caso. Nel nostro esempio, infatti, abbiamo deciso di definire variabili locali prod e j perché vengono utilizzate esclusivamente dal sottoprogramma e anche perché l'utilizzo di tali variabili permette di:

1) agevolare la lettura del programma, in quanto mette in evidenza in quale ambito hanno significato le risorse (le variabili);

2) individuare facilmente errori commessi, in quanto ci si sofferma solo sulle risorse (variabili) locali nell'ambito di quel sottoprogramma.

Le regole di visibilità

È ormai chiaro che all'interno di un programma ogni oggetto ha un suo campo di validità (scope, in inglese), ossia un ambito in cui può essere usato e riconosciuto.

15

È pertanto necessario definire delle regole per determinare il campo di visibilità degli oggetti globali e locali di un programma. Si parte dai seguenti principi:

1) gli oggetti globali sono accessibili a (visibili in) tutto il programma;

2) un oggetto dichiarato in un sottoprogramma ha significato solo in quel sottoprogramma e in tutti quelli in esso dichiarati. L'ambiente di un sottoprogramma, quindi, include anche tutte le risorse dei sottoprogrammi che contengono il sottoprogramma stesso (ambiente non locale)

OSCURAMENTO (SHADOWING)

Nella descrizione di un algoritmo, può succedere che si dia lo stesso nome ad una variabile locale ed ad una globale. Esse sono due variabili diverse senza alcuna relazione fra loro. Se per esempio la variabile A viene dichiarata nel programma principale e nel sottoprogramma SP1 e se, all'interno del sottoprogramma SP1 eseguo l'istruzione A ← 3 a quale variabile sarà assegnato il valore 3?

La risposta è alla variabile A locale al sottoprogramma SP1 in quanto essa “oscura” l'omonima variabile globale

I parametri

Un sottoprogramma è più utile se è funzionalmente indipendente dal programma principale. Un sottoprogramma, infatti, può essere utilizzato più volte all'interno di un programma e può anche essere trasportato, cioè, utilizzato con successo in altri programmi. Spesso accade di dover riscrivere interi sottoprogrammi che, pur essendo uguali nella logica e nelle istruzioni, operano su dati diversi.

Ciò comporta notevoli inconvenienti:

1) l'algoritmo appare pesante nella sua struttura e molto ripetitivo;

2) esiste un elevato rischio di commettere errori in fase di copiatura;

3) durante la fase di test, occorre necessariamente ricontrollare parti di algoritmo praticamente uguali;

4) eventuali analoghe modifiche dell'algoritmo potrebbero dover essere apportate in più punti.

Con le attuali conoscenze, purtroppo, non possiamo fare altrimenti. Analizziamo il seguente pseudocodice che visualizza un messaggio di saluto per tre differenti nominativi forniti in input:

ALGORITMO VisualizzaNomi

PROCEDURA Visualizza1()

INIZIO

SCRIVI("Ciao" , 'Mario")

FINE

PROCEDURA Visualizza2()

INIZIO

16

SCRIVI("Ciao" , "Paolo")

FINE

PROCEDURA Visualizza3()

INIZIO

SCRIVI("Ciao" , "Fabio")

FINE

FUNZIONE Main():

INIZIO

Visualizza1()

Visualizza2()

Visualizza3()

FINE

Come dicevamo, non abbiamo ancora preso in esame alcuno strumento che permetta di riutilizzare lo stesso sottoprogramma. In questo esercizio l'utilizzo dei sottoprogrammi perde il suo alto valore metodologico: le tre procedure sono identiche, ma operano su dati diversi. Siamo stati per questo costretti a riscrivere più volte il sottoprogramma, cambiando il suo nome e i dati su cui opera.

Si rende necessario, quindi, uno strumento che renda i sottoprogrammi autonomi e indipendenti dai dati del programma principale.

Per far questo, i linguaggi di programmazione mettono a disposizione i parametri.

I parametri sono oggetti caratterizzati da:

1) un identificatore;

2) un tipo;

3) un valore;

4) una posizione;

5) una direzione.

Grazie a essi si stabilisce attraverso quali oggetti debba avvenire l'input dei dati (al sottoprogramma chiamato) e l'output dei risultati (al programma o sottoprogramma chiamante).

L'identificatore e il tipo dei parametri sono noti al momento della dichiarazione del sottoprogramma (nei linguaggi statici quali C, C++, Pascal, è necessario conoscere il tipo al momento della dichiarazione, nei linguaggi dinamici quali python, perl non è necessario e tale fatto può essere un grande vantaggio) ma il valore è noto solo all'atto della chiamata.

I parametri permettono, quindi, di gestire la comunicazione del sottoprogramma con l'esterno.

All'atto della chiamata del sottoprogramma, occorrerà specificare i parametri attuali (chiamati anche argomenti o parametri effettivi), ossia le informazioni reali che devono essere trasmesse a esso. I valori di tali parametri saranno accolti dal sottoprogramma per mezzo dei parametri formali dichiarati nell'intestazione del sottoprogramma (vedi figura).

17

Un sottoprogramma parametrizzato lavora con variabili fittizie (nel nostro caso i parametri formali X e Y), che vengono collegate al programma principale solo al momento della chiamata del sottoprogramma.

È per questo motivo che tali parametri vengono detti formali. Dei parametri attuali (quindi al momento della chiamata da parte del programma chiamante) occorre indicare solo il nome; dei parametri formali, invece, è necessario indicare il nome e il tipo (il tipo è necessario solo nei linguaggi statici come Pascal, C, C++, in python, php, VB ed altri non è necessario).

E importante dire che il numero, il tipo e l'ordine dei parametri attuali devono essere sempre uguali a quelli dei corrispondenti parametri formali. Nel nostro esempio, infatti, la chiamata della procedura Proc1() associa il parametro attuale A di tipo intero al parametro formale X (anch'esso, ovviamente, di tipo intero) e il parametro attuale B di tipo intero al parametro formale Y di tipo intero.

I parametri attuali e i parametri formali possono anche avere casualmente lo stesso nome, ma si consiglia di utilizzare nomi diversi (per evitare inutili confusioni).

Spesso, all'atto della dichiarazione di un sottoprogramma, nasce il problema della scelta dei parametri. Suggeriamo di rispettare le seguenti regole:

1) dovrà essere gestito come parametro un oggetto necessario allo svolgimento delle operazioni/elaborazioni del sottoprogramma (oggetto di input) o che dovrà essere comunicato al programma chiamante (oggetto di output);

2) non dovrà essere gestito come parametro un oggetto il cui significato è limitato all'interno di un sottoprogramma.

E ora, a conclusione di questo paragrafo, vediamo come può essere trasformato il nostro algoritmo:

ALGORITMO VisualizzaNomi

PROCEDURA Visualizza (name):

INIZIO

SCRIVI("Ciao" , name)

18

FINE

FUNZIONE Main():

INIZIO

SCRIVI(“Inserisci il primo nome: “)

LEGGI(nome)

Visualizza(nome)

SCRIVI(“Inserisci il secondo nome: “)

LEGGI(nome)

Visualizza(nome)

SCRIVI(“Inserisci il terzo nome: “)

LEGGI(nome)

Visualizza(nome)

FINE

Qui si incomincia ad intravedere l'utilità dei sottoprogrammi che sta principalmente nel riutilizzo del codice: ho scritto una sola volta il codice per risolvere un particolare problema e poi l'ho riutilizzato tre volte (ricordi che nel caso senza parametri ho dovuto scriverlo tre volte?)

Il passaggio dei parametri

Con passaggio o trasmissione dei parametri intendiamo l'operazione con la quale valore dei parametri attuali viene associato (trasmesso) a quello dei parametri formali

Il passaggio dei parametri può avvenire principalmente secondo due distinte modalità, ognuna rispondente a esigenze diverse: passaggio per valore (by value) e passaggio per indirizzo o referenza (by reference).

Vediamo in dettaglio queste due modalità. Consideriamo la procedura Scambia() che dovrà scambiare i valori dei due parametri attivati.

PROCEDURA Esempio ()

INIZIO

.....

Scambia(A,B)

......

FINE

PROCEDURA Scambia(X,Y)

INIZIO

....

FINE

19

nel passaggio dei parametri per valore (by value) si ha soltanto una copia dei valori dei parametri attuali nei rispettivi parametri formali. Durante l'esecuzione del sottoprogramma, qualsiasi modifica apportata ai parametri formali sarà visibile solo all'interno del sottoprogramma e non verrà riportata sui parametri attuali (che continueranno, così, a conservare il valore inizialmente trasmesso).

Copia dei valori

Per capire ancora meglio può essere interessante fare un disegno che rappresenti la memoria del calcolatore. Supponiamo che A e B valgano 3 e 8 rispettivamente: la situazione di memoria prima della chiamata alla procedura scambia è la seguente: abbiamo le due locazioni di memoria A e B che contengono 3 e 8

Al momento della chiamata al sottoprogramma, la prima cosa che avviene è che vengono create due variabili temporanee e locali che si chiamano X e Y e in esse viene copiato il contenuto di A e B (in base all'ordine con cui sono state scritte, ossia la situazione è la seguente

Le celle X e Y verranno usate dal sottoprogramma e poi alla fine verranno distrutte (tecnicamente si parla di allocazione della memoria al momento della creazione delle due variabili temporanee e locali e di deallocazione o rilascio della memoria al momento dell'uscita dal sottoprogramma.

I parametri formali vengono considerati come variabili locali il cui valore, al ritorno dal sottoprogramma, perde il suo significato;

PROCEDURA Esempio ()

INIZIO

.....

Scambia(A,B)

......

FINE

PROCEDURA Scambia(Ref: X,Y)

INIZIO

....

....

....

FINE

Anche in questo caso facciamo un disegno che rappresenti la memoria del calcolatore. Supponiamo che A e B valgano 8 e 2 rispettivamente: la situazione di memoria prima della chiamata alla procedura scambia è la seguente: abbiamo le due locazioni di memoria A e B che contengono 8 e 2

Al momento della chiamata al sottoprogramma, la prima cosa che avviene è che vengono creati due nuovi nomi temporaneei e locali che si chiamano X e Y ma nessuna zona nuova di memoria è associata ad essi: questi nomi faranno riferimento il primo X alla locazione A e il secondo Y alla locazione B (questo in base all'ordine con cui sono stati scritti parametri stessi) ossia la situazione è

20

nel passaggio dei parametri per indirizzo (by reference) invece i parametri formali contengono l'indirizzo di memoria dei parametri attuali. Di conseguenza non si ha soltanto una copia dei valori dei parametri attuali nei rispettivi parametri formali ma una modifica dei parametri formali comporta una eguale e contemporanea modifica dei parametri attuali).

Coincidono

3A B

8

3A B

8 3X Y

8

8A B

2

la seguente

In questo caso quindi non c'è alcuna memoria locale associata ai parametri ma solo dei nomi locali e temporanei (cioè che esistono solo per il tempo di esecuzione della procedura e che sono visibili solo in ambiente locale) che però, fanno riferimento alle locazioni di memoria dei parametri attuali e quindi possono modificarli: in realtà ciascuna operazione eseguita su X è come se fosse fatta su A e lo stesso si può dire per la copia Y e B.

Con questo tipo di passaggio, quindi, si può perdere il contenuto originale dei parametri attuali. Secondo il nostro formalismo, il passaggio per indirizzo viene indicato anteponendo la parola chiave REF (referenza) al parametro o alla lista di parametri formali interessati.

Non tutti i linguaggi prevedono ambedue i tipi di passaggio di parametri. Il Pascal, il Visual Basic li gestisce entrambi, mentre nel linguaggio C è ammesso soltanto il passaggio per valore, anche se il passaggio per referenza può essere imitato. In python il discorso è ancora diverso.

N.B. Nel passaggio dei parametri per valore, all'atto della chiamata del sottoprogramma, viene allocata un'area di memoria utilizzata per contenere i parametri formali. Si ha, così, una duplicazione dello spazio di memoria riservato ai parametri. Al passaggio, i parametri formali verranno inizializzati con il valore dei rispettivi parametri attuali. In questo modo, il processore opera su questa nuova area di memoria lasciando inalterato il valore dei parametri attuali.

Al rientro dal sottoprogramma, quest'area viene rilasciata, proprio come avviene per le variabili locali.

Servendoci delle nuove conoscenze acquisite sul passaggio dei parametri vogliamo rendere più generale l'algoritmo di ordinamento di due numeri visto in precedenza.

ALGORITMO Ordinamento

PROCEDURA Scambia(x,y)

INIZIO

temp ← x

x ← y

y ← tmp

FINE

PROCEDURA Main()

INIZIO

SCRIVI(“Inserisci il primo numero: “)

LEGGI(primo)

SCRIVI(“Inserisci il secondo numero: “)

LEGGI(secondo)

SE primo > secondo ALLORA

Scambia(primo, secondo)

21

8A B

2X Y

FINE SE

SCRIVI(“I due numeri ordinati sono: “,primo,secondo)

FINE

Il passaggio dei parametri è per valore per cui l'algoritmo così come è strutturato non funziona (cioè non fa ciò che vorremmo facesse): questo è dovuto al fatto che al momento della chiamata della procedura scambia vengono create le variabili x e y (e anche temp che è sempre una variabile locale) che sono solo una copia dei valori di primo e secondo ma, come abbiamo appena imparato, le modifiche effettuate su x e y non hanno alcuna influenza sui parametri attuali primo e secondo. Per convincerci di ciò implementiamo tale problema in VB e vediamo che succede

Public Class frmScambiaErrato

Private Sub cmdEsegui_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdEsegui.Click Dim primo, secondo As Integer primo = txtPrimo.Text secondo = txtSecondo.Text If primo > secondo Then scambia(primo, secondo) End If lblPrimoScambiato.Text = lblPrimoScambiato.Text & " " & primo lblSecondoScambiato.Text = lblSecondoScambiato.Text & " " & secondo End Sub Private Sub scambia(ByVal x, ByVal y) 'dovrebbe scambiare x con y ma è sbagliata in quanto i parametri sono 'solo passati per valore e non hanno effetto sulle variabili del programma chiamante Dim temp As Integer temp = x x = y y = temp End Sub

Private Sub cmdEsci_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdEsci.Click End End SubEnd ClassL'esecuzione di questo programma porta ad esempio a questo risultato

come vedete i numeri e le variabili non sono state affatto scambiate

Come vedete all'interno della procedura i dati sono stati ordinati ma non all'esterno.

Vediamo di risolvere subito il problema sia in pseudocodifica che in VB.

L'unica modifica nel pseudocodice è l'introduzione del passaggio per referenza evidenziato dalla parola chiave REF nella definizione della procedura Scambia

22

ALGORITMO Ordinamento

PROCEDURA Scambia(REF: x,y)

INIZIO

temp ← x

x ← y

y ← tmp

FINE

PROCEDURA Main()

INIZIO

SCRIVI(“Inserisci il primo numero: “)

LEGGI(primo)

SCRIVI(“Inserisci il secondo numero: “)

LEGGI(secondo)

SE primo > secondo ALLORA

Scambia(primo, secondo)

FINE SE

SCRIVI(“I due numeri ordinati sono: “,primo,secondo)

FINE

In Visual Basic le modifiche sono dello stesso tipo: occorre cambiare il tipo di passaggio di parametri da “passaggio per valore” a “passaggio per riferimento”.

Public Class frmScambiaCorretto

Private Sub cmdEsegui_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdEsegui.Click Dim primo, secondo As Integer primo = txtPrimo.Text secondo = txtSecondo.Text If primo > secondo Then scambia(primo, secondo) End If lblPrimoScambiato.Text = lblPrimoScambiato.Text & " " & primo lblSecondoScambiato.Text = lblSecondoScambiato.Text & " " & secondo End Sub Private Sub scambia(ByRef x, ByRef y) 'scambia x con y ossia i rispettivi parametri attuali con cui viene chiamata Dim temp As Integer temp = x x = y y = temp End Sub

Private Sub cmdEsci_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdEsci.Click End End SubEnd Class

23

Precisazioni riguardo visual Basic.

Il modello di programmazione di VB è chiamato programmazione ad eventi: infatti il programma va in esecuzione e poi aspetta gli eventi che possono accadere, generalmente causati dall'utente umano ma non necessariamente, che possono essere il click di un mouse, lo spostamento del mouse, l'inizio della scrittura etc.; a questi eventi, se previsto dal codice, il VB esegue le cosiddette procedure di gestione degli eventi, che sono quelle che abbiamo sempre eseguito ed associato al click del pulsante esegui per esempio.

Le procedure e funzioni che stiamo vedendo qui vengono invece chiamate procedure generali e, a differenza delle altre non sono associate ad eventi, ma sono associate a del codice mediante le famose istruzioni di chiamata al sottoprogramma.

Per quanto riguarda la visibilità delle risorse (variabili e sottoprogrammi stessi) in VB abbiamo le seguenti possibilità. Si possono creare sottoprogrammi generali di due tipi diversi:

1) ci sono i sottoprogrammi contenuti all'interno di un form (sono quelli visti sinora e le cui definizioni sono scritte all'interno di public class...end class. Queste procedure sono note all'interno del form stesso, ossia possono essere richiamate da qualunque sottoprogramma presente all'interno del forma. Stessa cosa dicasi per le variabili: le variabili dichiarate nella sezione generale di un form sono note a tutti i sottoprogrammi del form stesso

2) ci sono poi i sottoprogrammi a livello di modulo (questi non li abbiamo ancora visti). Questo tipo di sottoprogrammi possono essere usati da tutti i form del programma. In qualche modo sono sottoprogrammi più globali dei precedenti

24