Figura 421.23. Situazione iniziale della torre di Hanoi all'inizio del gioco.
|
|
[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [translators] [docinfo] [indice analitico] [volume] [parte]
Un tempo la programmazione avveniva attraverso lunghe fasi di studio a tavolino. Prima di iniziare il lavoro di scrittura del programma (su moduli cartacei che venivano trasferiti successivamente nella macchina) si passava per la realizzazione di un diagramma di flusso, o flow chart.
Il diagramma di flusso andava bene fino a quando si utilizzavano linguaggi di programmazione procedurali, come il COBOL. Quando si sono introdotti concetti nuovi che rendevano tale sistema di rappresentazione più complicato del linguaggio stesso, si è preferito schematizzare gli algoritmi attraverso righe di codice vero e proprio o attraverso una pseudocodifica più o meno adatta al concetto che si vuole rappresentare di volta in volta.
In questo capitolo viene presentata una pseudocodifica e alcuni esempi di algoritmi tipici, utilizzabili nella didattica della programmazione. Gli esempi proposti non sono ottimizzati perché si intende puntare sulla chiarezza piuttosto che sull'eventuale velocità di esecuzione.
La pseudocodifica utilizzata in questo capitolo si rifà a termini e concetti comuni a molti linguaggi di programmazione recenti. Vale la pena di chiarire solo alcuni dettagli:
le variabili di scambio di una subroutine (una procedura o una funzione) vengono semplicemente nominate a fianco del nome della procedura, tra parentesi, cosa che corrisponde a una dichiarazione implicita di quelle variabili con un campo di azione locale e con caratteristiche identiche a quelle usate nelle chiamate relative;
il trasferimento dei parametri di una chiamata alla subroutine avviene per valore, impedendo l'alterazione delle variabili originali;
per trasferire una variabile per riferimento, in modo che il suo valore venga aggiornato al termine dell'esecuzione di una subroutine, occorre aggiungere il simbolo @ di fronte al nome della variabile utilizzata nella chiamata;
il simbolo # rappresenta l'inizio di un commento;
il simbolo := rappresenta l'assegnamento;
il simbolo :==: rappresenta lo scambio tra due operandi.
Nelle sezioni seguenti sono descritti alcuni problemi elementari attraverso cui si insegnano le tecniche di programmazione ai principianti. Assieme ai problemi vengono proposte le soluzioni in forma di pseudocodifica.
La somma di due numeri positivi può essere espressa attraverso il concetto dell'incremento unitario: n+m equivale a incrementare m, di un'unità, per n volte, oppure incrementare n per m volte. L'algoritmo risolutivo è banale, ma utile per apprendere il funzionamento dei cicli:
|
In questo caso viene mostrata una soluzione per mezzo di un ciclo enumerativo, FOR. Il ciclo viene ripetuto Y volte, incrementando la variabile Z di un'unità. Alla fine, Z contiene il risultato della somma di X per Y. La pseudocodifica seguente mostra invece la traduzione del ciclo FOR in un ciclo WHILE:
|
La moltiplicazione di due numeri positivi, può essere espressa attraverso il concetto della somma: n*m equivale a sommare m volte n, oppure n volte m. L'algoritmo risolutivo è banale, ma utile per apprendere il funzionamento dei cicli:
|
In questo caso viene mostrata una soluzione per mezzo di un ciclo FOR. Il ciclo viene ripetuto Y volte, incrementando la variabile Z del valore di X. Alla fine, Z contiene il risultato del prodotto di X per Y. La pseudocodifica seguente mostra invece la traduzione del ciclo FOR in un ciclo WHILE:
|
La divisione di due numeri positivi, può essere espressa attraverso la sottrazione: n:m equivale a sottrarre m da n fino a quando n diventa inferiore di m. Il numero di volte in cui tale sottrazione ha luogo, è il risultato della divisione.
|
L'elevamento a potenza, utilizzando numeri positivi, può essere espresso attraverso il concetto della moltiplicazione: n**m equivale a moltiplicare m volte n per se stesso.
|
In questo caso viene mostrata una soluzione per mezzo di un ciclo FOR. Il ciclo viene ripetuto Y volte; ogni volta la variabile Z viene moltiplicata per il valore di X, a partire da uno. Alla fine, Z contiene il risultato dell'elevamento di X a Y. La pseudocodifica seguente mostra invece la traduzione del ciclo FOR in un ciclo WHILE:
|
La pseudocodifica seguente mostra una soluzione ricorsiva:
|
Il calcolo della parte intera della radice quadrata di un numero si può fare per tentativi, partendo da 1, eseguendo il quadrato fino a quando il risultato è minore o uguale al valore di partenza di cui si calcola la radice.
|
Il fattoriale è un valore che si calcola a partire da un numero positivo. Può essere espresso come il prodotto di n per il fattoriale di n-1, quando n è maggiore di 1, mentre equivale a 1 quando n è uguale a 1. In pratica, n! = n * (n-1) * (n-2)... * 1.
|
La soluzione appena mostrata fa uso di un ciclo WHILE in cui l'indice I, che inizialmente contiene il valore di X-1, viene usato per essere moltiplicato al valore di X, riducendolo ogni volta di un'unità. Quando I raggiunge lo zero, il ciclo termina e X contiene il valore del fattoriale. L'esempio seguente mostra invece una soluzione ricorsiva che dovrebbe risultare più intuitiva:
|
Il massimo comune divisore tra due numeri può essere ottenuto sottraendo a quello maggiore il valore di quello minore, fino a quando i due valori sono uguali. Quel valore è il massimo comune divisore.
|
Un numero intero è numero primo quando non può essere diviso per un altro intero diverso dal numero stesso e da 1, generando un risultato intero.
|
Nelle sezioni seguenti sono descritti alcuni problemi legati alla scansione di array. Assieme ai problemi vengono proposte le soluzioni in forma di pseudocodifica.
La ricerca di un elemento all'interno di un array disordinato può avvenire solo in modo sequenziale, cioè controllando uno per uno tutti gli elementi, fino a quando si trova la corrispondenza cercata. Segue la descrizione delle variabili più importanti che appaiono nella pseudocodifica successiva:
Ecco un esempio di pseudocodifica che risolve il problema in modo iterativo:
|
Solo a scopo didattico, viene proposta una soluzione ricorsiva:
|
La ricerca di un elemento all'interno di un array ordinato può avvenire individuando un elemento centrale: se questo corrisponde all'elemento cercato, la ricerca è terminata, altrimenti si ripete nella parte di array precedente o successiva all'elemento, a seconda del suo valore e del tipo di ordinamento esistente.
Il problema posto in questi termini è ricorsivo. La pseudocodifica mostrata utilizza le stesse variabili già descritte per la ricerca sequenziale.
|
Nelle sezioni seguenti sono descritti alcuni problemi classici attraverso cui si insegnano le tecniche di programmazione. Assieme ai problemi vengono proposte le soluzioni in forma di pseudocodifica.
Il Bubblesort è un algoritmo relativamente semplice per l'ordinamento di un array, in cui ogni scansione trova il valore giusto per l'elemento iniziale dell'array stesso. Una volta trovata la collocazione di un elemento, si ripete la scansione per il segmento rimanente di array, in modo da collocare un altro valore. La pseudocodifica dovrebbe chiarire il meccanismo.
Viene mostrata una soluzione iterativa:
|
Segue una soluzione ricorsiva:
|
Due array a una dimensione, con la stessa struttura, ordinati secondo qualche criterio, possono essere fusi in un array singolo, che mantiene l'ordinamento.
Viene mostrata una soluzione iterativa, dove si presume che gli array siano ordinati in modo non decrescente:
|
La torre di Hanoi è un gioco antico: si compone di tre pioli identici conficcati verticalmente su una tavola e di una serie di anelli di larghezze differenti. Gli anelli sono più precisamente dei dischi con un foro centrale che permette loro di essere infilati nei pioli.
Il gioco inizia con tutti gli anelli collocati in un solo piolo, in ordine, in modo che in basso ci sia l'anello più largo e in alto quello più stretto. Si deve riuscire a spostare tutta la pila di anelli in un dato piolo muovendo un anello alla volta e senza mai collocare un anello più grande sopra uno più piccolo.
|
Figura 421.23. Situazione iniziale della torre di Hanoi all'inizio del gioco.
|
Nella figura 421.23 gli anelli appaiono inseriti sul piolo 1; si supponga che questi debbano essere spostati sul piolo 2. Si può immaginare che tutti gli anelli, meno l'ultimo, possano essere spostati in qualche modo corretto, dal piolo 1 al piolo 3, come nella situazione della figura 421.24.
|
Figura 421.24. Situazione dopo avere spostato n-1 anelli.
|
A questo punto si può spostare l'ultimo anello rimasto (l'n-esimo), dal piolo 1 al piolo 2; quindi, come prima, si può spostare in qualche modo il gruppo di anelli posizionati attualmente nel piolo 3, in modo che finiscano nel piolo 2 sopra l'anello più grande.
Pensando in questo modo, l'algoritmo risolutivo del problema deve essere ricorsivo e potrebbe essere gestito da un'unica subroutine che può essere chiamata opportunamente HANOI.
|
Segue la pseudocodifica ricorsiva per la soluzione del problema:
|
Se N, il numero degli anelli da spostare, è minore di 1, non si deve compiere alcuna azione. Se N è uguale a 1, le istruzioni che dipendono dalla struttura IF-END IF vengono eseguite, ma nessuna delle chiamate ricorsive fa alcunché, dato che N-1 è pari a zero. In questo caso, supponendo che N sia uguale a 1, che P1 sia pari a 1 e P2 pari a 2, il risultato è semplicemente:
Muovi l'anello 1 dal piolo 1 al piolo 2 |
Il risultato è quindi corretto per una pila iniziale consistente di un solo anello.
Se N è uguale a 2, la prima chiamata ricorsiva sposta un anello (N-1 = 1) dal piolo 1 al piolo 3 (ancora assumendo che i due anelli debbano essere spostati dal primo al terzo piolo) e si sa che questa è la mossa corretta. Quindi viene stampato il messaggio che dichiara lo spostamento del secondo piolo (l'N-esimo) dalla posizione 1 alla posizione 2. Infine, la seconda chiamata ricorsiva si occupa di spostare l'anello collocato precedentemente nel terzo piolo, nel secondo, sopra a quello che si trova già nella posizione finale corretta.
In pratica, nel caso di due anelli che devono essere spostati dal primo al secondo piolo, appaiono i tre messaggi seguenti.
Muovi l'anello 1 dal piolo 1 al piolo 3 Muovi l'anello 2 dal piolo 1 al piolo 2 Muovi l'anello 1 dal piolo 3 al piolo 2 |
Nello stesso modo si potrebbe dimostrare il funzionamento per un numero maggiore di anelli.
L'ordinamento degli elementi di un array è un problema tipico che si può risolvere in tanti modi. Il Quicksort è un algoritmo sofisticato, ottimo per lo studio della gestione degli array, oltre che per quello della ricorsione. Il concetto fondamentale di questo tipo di algoritmo è rappresentato dalla figura 421.29.
|
Figura 421.29. Il concetto base dell'algoritmo del Quicksort: suddivisione dell'array in due gruppi disordinati, separati da un valore piazzato correttamente nel suo posto rispetto all'ordinamento.
|
Una sola scansione dell'array è sufficiente per collocare definitivamente un elemento (per esempio il primo) nella sua destinazione finale e allo stesso tempo per lasciare tutti gli elementi con un valore inferiore a quello da una parte, anche se disordinati, e tutti quelli con un valore maggiore, dall'altra.
In questo modo, attraverso delle chiamate ricorsive, è possibile elaborare i due segmenti dell'array rimasti da riordinare.
L'algoritmo può essere descritto grossolanamente come:
localizzazione della collocazione finale del primo valore, separando in questo modo i valori;
ordinamento del segmento precedente all'elemento collocato definitivamente;
ordinamento del segmento successivo all'elemento collocato definitivamente.
Viene qui indicato con PART la subroutine che esegue la scansione dell'array, o di un suo segmento, per determinare la collocazione finale (indice CF) del primo elemento (dell'array o del segmento in questione).
Sia LISTA l'array da ordinare. Il primo elemento da collocare corrisponde inizialmente a LISTA[A] e il segmento di array su cui intervenire corrisponde a LISTA[A:Z] (cioè a tutti gli elementi che vanno dall'indice A all'indice Z).
Alla fine della prima scansione, l'indice CF rappresenta la posizione in cui occorre spostare il primo elemento, cioè LISTA[A]. In pratica, LISTA[A] e LISTA[CF] vengono scambiati.
Durante la scansione che serve a determinare la collocazione finale del primo elemento, PART deve occuparsi di spostare gli elementi prima o dopo quella posizione, in funzione del loro valore, in modo che alla fine quelli inferiori o uguali a quello dell'elemento da collocare si trovino nella parte inferiore e gli altri dall'altra. In pratica, alla fine della prima scansione, gli elementi contenuti in LISTA[A:(CF-1)] devono contenere valori inferiori o uguali a LISTA[CF], mentre quelli contenuti in LISTA[(CF+1):Z] devono contenere valori superiori.
Indichiamo con QSORT la subroutine che esegue il compito complessivo di ordinare l'array. Il suo lavoro consisterebbe nel chiamare PART per collocare il primo elemento, continuando poi con la chiamata ricorsiva di se stessa per la parte di array precedente all'elemento collocato e infine alla chiamata ricorsiva per la parte restante di array.
Assumendo che PART e le chiamate ricorsive di QSORT svolgano il loro compito correttamente, si potrebbe fare un'analisi informale dicendo che se l'indice Z non è maggiore di A, allora c'è un elemento (o nessuno) all'interno di LISTA[A:Z] e inoltre, LISTA[A:Z] è già nel suo stato finale. Se Z è maggiore di A, allora (per assunzione) PART ripartisce correttamente LISTA[A:Z]. L'ordinamento separato dei due segmenti (per assunzione eseguito correttamente dalle chiamate ricorsive) completa l'ordinamento di LISTA[A:Z].
Le figure 421.30 e 421.31 mostrano due fasi della scansione effettuata da PART all'interno dell'array o del segmento che gli viene fornito.
|
Figura 421.30. La scansione dell'array da parte di PART avviene portando in avanti l'indice I e portando indietro l'indice CF. Quando l'indice I localizza un elemento che contiene un valore maggiore di LISTA[A] e l'indice CF localizza un elemento che contiene un valore inferiore o uguale a LISTA[A], gli elementi cui questi indici fanno riferimento vengono scambiati, quindi il processo di avvicinamento tra I e CF continua.
|
|
Figura 421.31. Quando la scansione è giunta al termine, quello che resta da fare è scambiare l'elemento LISTA[A] con LISTA[CF].
|
In pratica, l'indice I, iniziando dal valore A+1, viene spostato verso destra fino a che viene trovato un elemento maggiore di LISTA[A], quindi è l'indice CF a essere spostato verso sinistra, iniziando dalla stessa posizione di Z, fino a che viene incontrato un elemento minore o uguale a LISTA[A]. Questi elementi vengono scambiati e lo spostamento di I e CF riprende. Ciò prosegue fino a che I e CF si incontrano, momento in cui LISTA[A:Z] è stata ripartita e CF rappresenta l'indice di un elemento che si trova nella sua collocazione finale.
|
Segue la pseudocodifica delle due subroutine:
|
|
|
Vale la pena di osservare che l'array viene indicato nelle chiamate in modo che alla subroutine sia inviato un riferimento a quello originale, perché le variazioni fatte all'interno delle subroutine devono riflettersi sull'array originale. |
La permutazione è lo scambio di un gruppo di elementi posti in sequenza. Il problema che si vuole analizzare è la ricerca di tutte le permutazioni possibili di un dato gruppo di elementi.
Se ci sono n elementi in un array, allora alcune delle permutazioni si possono ottenere bloccando l'n-esimo elemento e generando tutte le permutazioni dei primi n-1 elementi. Quindi l'n-esimo elemento può essere scambiato con uno dei primi n-1, ripetendo poi la fase precedente. Questa operazione deve essere ripetuta finché ognuno degli n elementi originali è stato usato nell'n-esima posizione.
Segue la pseudocodifica:
|
La gestione dei file è sempre la questione più complessa nello studio degli algoritmi, quanto si esclude la possibilità di gestire semplicemente tutto nella memoria centrale. In questo tipo di situazione, il file deve essere inteso come un insieme di record, che spesso sono di dimensione uniforme.
Nelle sezioni seguenti sono descritti alcuni problemi legati alla gestione dei file, con la soluzione in forma di pseudocodifica.
La fusione di due file ordinati, aventi la stessa struttura, avviene leggendo un record da entrambi i file, confrontando la chiave di ordinamento e scrivendo nel file da ottenere il record con chiave più bassa. Successivamente, viene letto solo record successivo del file che conteneva la chiave più bassa e si ripete il confronto.
|
Figura 421.37. Il file
|
Segue un esempio di pseudocodifica per la soluzione del problema della fusione tra due file. La funzione riceve il riferimento ai file da elaborare e si può osservare l'utilizzo di variabili strutturate per accogliere i record dei file da elaborare. Come si può intuire, le variabili booleane il cui nome inizia per EOF, rappresentano l'avverarsi della condizione di «fine del file»; in pratica, quando contengono il valore Vero, indicano che la lettura del file a cui si riferiscono è andata oltre la conclusione del file.
|
Un file non ordinato può essere ordinato, attraverso una serie di passaggi, che prevedono la divisione in due parti del file (ovvero biforcazione), contenenti le raccolte dei blocchi di record che risultano essere nella sequenza corretta, per poi fondere queste due parti e ripetere il procedimento. Le figure successive mostrano le due fasi: la separazione in due file, la fusione dei due file. Se il file risultante non è ordinato completamente, occorre procedere con una nuova fase di separazione e fusione. Si osservi, in particolare, che nelle figure, il file iniziale contiene solo tre blocchi di record in sequenza, pertanto, l'ultimo di questi blocchi viene collocato nel file finale senza una fusione con un blocco corrispondente.
|
Figura 421.39. Biforcazione del file.
|
|
Figura 421.40. Fusione.
|
Per costruire un programma che utilizza questa tecnica di ordinamento, si può considerare che sia avvenuta l'ultima fase di biforcazione quando si contano un massimo di due blocchi; pertanto, la fase successiva di fusione produce sicuramente il file ordinato finale.
Segue un esempio di pseudocodifica per eseguire la biforcazione. Si osservi che i nomi dei file vengono passati in qualche modo, così che dopo la chiamata di questa procedura sia possibile riaprire tali file per la fusione; inoltre, l'informazione contenuta nella BIFORCAZIONE, viene restituita come valore della chiamata della funzione, in modo da poter conoscere, dopo la chiamata, quante separazioni sono state eseguite nel file di partenza.
|
Segue un esempio di pseudocodifica per eseguire la fusione a blocchi. Si osservi che i nomi dei file vengono passati in qualche modo, così che dopo la chiamata di questa procedura sia possibile riaprire tali file per la biforcazione e di nuovo per la fusione. Come si può intuire, le variabili booleane il cui nome inizia per EOB, rappresentano l'avverarsi della condizione di «fine del blocco» non decrescente; in pratica, quando contengono il valore Vero, indicano che la lettura del file a cui si riferiscono ha prodotto un record che ha una chiave inferiore rispetto a quello letto precedentemente, oppure che non sono disponibili altri record.
|
Per poter riordinare effettivamente un file, utilizzando le procedure descritte, si può utilizzare la pseudocodifica seguente, che si avvale di quanto già descritto. Per non dover mostrare nella pseudocodifica come si dichiarano i file, si suppone che questo sia compito di un'altra porzione di codice assente, nel quale si chiama la procedura sottostante, indicando i riferimenti ai file da utilizzare. Si osservi che il file originale non viene modificato, producendo eventualmente un altro file ordinato.
|
Appunti di informatica libera 2006.07.01 --- Copyright © 2000-2006 Daniele Giacomini -- <daniele (ad) swlibero·org>
Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome pseudocodifica.htm
[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [translators] [docinfo] [indice analitico]
