6.1 Introduzione.

Prima di introdurre i vettori vediamo con un esempio come con i tipi scalari standard diventa complesso risolvere problemi anche molto semplici.

Problema: dati 10 numeri interi positivi calcolare per ognuno lo scarto dalla media aritmetica.

L'obiettivo è chiaramente espresso dal testo così come il risultato atteso.

RISULTATI: lo scarto per ogni numero

DATI: a1, a2, .. a10 numeri interi positivi

ALGORITMO

BEGIN

READ( a1, a2, ..., a10 );
media:=(a1+a2+...+a10)/10;
WRITE(a1-media, a2-media, ... , a10-media);

Se si prova a generalizzare il problema per un numero n qualunque di valori ci si accorge subito delle difficoltà che si debbono affrontare. Questo perchè i tipi di dato utilizzati sinora, detti scalari, hanno la caratteristica di rappresentare un singolo valore mentre per risolvere il problema precedente sono necessarie delle variabili, dette strutturate, che permettano di indicare con un nome unico un insieme di dati. Un primo esempio di variabile strutturata è il tipo ARRAY.

6.2 Tipo ARRAY.

Per definire il tipo di una variabile strutturata è necessario indicare il tipo della struttura e il tipo delle singole componenti. Per quanto riguarda l'array devono inoltre essere soddisfatte le seguenti condizioni:

- deve esssere indicato il numero delle componenti

- ogni elemento deve essere accessibile direttamente attraverso un indice

In Pascal sono stabilite delle convenzioni per poter indicare il tipo array con il numero di componenti e per poter accedere direttamente alle singole componenti. Per la dichiarazione si procede così:

TYPE

vettore=ARRAY[dominio_indice] OF tipo_delle_componenti;

dove

- ARRAY indica che vettore è un nuovo tipo di dato strutturato

- dominio_indice stabilisce l'insieme finito di valori che può assumere l'indice. Può essere un qualsiasi tipo scalare escluso il real.

- tipo_componenti indica il tipo di ciascuna componente

Esempio.

TYPE

vettore1=ARRAY[char] OF REAL;
vettore2=ARRAY[boolean] OF INTEGER;
vettore3=ARRAY[1..150] OF BOOLEAN;

VAR

v1:vettore1;
v2:vettore2;
v3:vettore3;

v1 è una variabile di tipo array con 256 (o 128) real. I valori possibili dell'indice sono tutti gli elementi della tabella ascii.

v2 è una variabile di tipo array con 2 elementi di tipo integer. I valori possibili dell'indice sono true e false.

v3 è una variabile di tipo array con 150 elementi di tipo boolean. I valori possibili dell'indice sono i numeri interi compresi nell'intervallo [1, 150].

A livello sintattico è possibile la seguente dichiarazione:
 

grosso=ARRAY[INTEGER] OF tipo;

Poichè lo spazio richiesto per una variabile di tipo "grosso" è rilevante alcune implementazioni del pascal generano errore.

Per individuare un elemento di un array dobbiamo indicare la posizione.

Ad esempio
 

v3[2] indica la seconda posizione del vettore v3;
v2[false] indica la prima posizione del vettore v2;
v1['A'] indica la posizione ord('A'), cioè la posizione 65;

Le seguenti assegnazioni sono valide.

v1['a']:=23.6; v1['b']:=1e5; v3[1]:=FALSE;
v2[true]:=1; v2[false]:=1;

v1[1]:=23.9; { L'indice deve essere di tipo char }
v1['a']:='a'; { Il singolo elemento è di tipo real }
v3[151]:=TRUE; { 151 supera la dimensione stabilita per il vettore }

6.3 Input/output di un vettore.

L'inserimento dei dati in un vettore, così come la stampa, deve essere effettuata elemento per elemento. Ad esempio se definiamo la seguente struttura dati:

TYPE

vettore=ARRAY[1..100] OF INTEGER;

VAR

v:vettore;

La lettura e la scrittura possono essere effettuate cosi:
 

readln(v[1], v[2], ..., v[100]);
writeln(v[1], v[2], ..., v[100]);

REPEAT

READLN( n )

READLN( v[i] );

dove n è una variabile di tipo integer utilizzata per memorizzare quante componenti di v sono effettivamente utilizzate. Si ricorda che n, oltre ad essere positivo, non può superare la dimensione del vettore.

In modo analogo per la stampa

FOR i:=1 TO n DO

WRITELN( v[i] );

E` da notare che la stampa è solo di n elementi del vettore, poichè solo i primi n sono stati effettivamente utilizzati. Questo è un problema che deve essere gestito sempre quando si utilizza un vettore. Si deve cioè stabilire un metodo per identificare con precisione le celle del vettore effettivamente utilizzate. Negli esempi precedenti abbiamo utilizzato un'ulteriore variabile ( n ) per contenere il numero di elementi effettivamente gestito, avendo poi cura di inserire i valori nel vettore in posizioni consecutive. Nei problemi risolti nelle prossime pagine affronteremo dettagliatamente questo problema proponendo diverse soluzioni.

6.4 Problemi con utilizzo di vettori.

Problema 1: dato un vettore di numeri sommarli.

RISULTATI: somma = somma degli elementi del vettore

DATI: gli n numeri da inserire nel vettore

STRUTTURE DATI:

CONST

dim=100;

numeri=ARRAY[1..dim] OF REAL;

VAR

num:numeri;

ALGORITMO:

BEGIN

leggi vettore
somma elementi
stampa risultati

Il programma completo sarà:

PROGRAM somma( INPUT, OUTPUT );
CONST
dim=100;
TYPE
numeri=ARRAY[1..dim] OF REAL;
VAR
num :numeri;
n, { quantità di numeri da gestire }
i :INTEGER; { indice }
somma:REAL;
BEGIN
{ lettura dei numeri }
REPEAT
WRITE( 'Numeri da esaminare = ' );
READLN( n )

UNTIL (n>0) AND (n<=dim);

FOR i:=1 TO n DO BEGIN

WRITE( 'Numero di posizione ', i );

READLN( num[i] )

END;

{ somma dei valori }

somma:=0; { inizializzazione accumulatore }

FOR i:=1 TO n DO

somma:=somma+num[i];

{ stampa risultato }

WRITELN( 'La somma è ', somma )

END.

Esercizi 1

1.1 Calcolare il prodotto degli elementi di un vettore di numeri.

1.2 Contare i numeri negativi di un vettore di interi.

1.3 Calcolare la somma dei numeri pari di un vettore di interi.

1.4 Calcolare la somma degli elementi di posto dispari di un vettore di numeri.

Problema 2: calcolare il prodotto di uno scalare per un vettore.

Il vettore è chiaramente un vettore di numeri, ad esempio un vettore di real. Il prodotto di un numero a per un vettore v è un nuovo vettore le cui componenti sono ottenute moltiplicando ciascuna componente di v per a.

RISULTATO: numeri contenuti nel vettore risultato

DATI: i numeri da inserire nel vettore

STRUTTURA DATI: analoga a quella dell'esercizio precedente

ALGORITMO:

BEGIN

leggi numeri

calcola prodotto

scrivi risultati

END.

Il programma definitivo sarà:

PROGRAM prodotto( INPUT, OUTPUT );

CONST

dim=100;

TYPE

numeri=ARRAY[1..dim] OF REAL;

VAR

num :numeri;

n, { quantità di numeri da gestire }

i :INTEGER; { indice }

a: REAL; { scalare }

BEGIN

{ leggi vettore }

{ identico all'esempio precedente }

{ calcola prodotto }

FOR i:=1 TO n DO

num[i]:=num[i]*a;

{ stampa risultati }

WRITELN( 'VETTORE RISULTATO' );

FOR i:=1 TO n DO

WRITELN( 'Posizione ', i, ' valore ', num[i] )

END.

Abbiamo già osservato come sia importante conoscere quante e quali celle sono effettivamente occupate. Se il vettore viene riempito occupando consecutivamente le celle ci basta conoscere la quantità. Negli esercizi precedenti abbiamo utilizzato una nuova variabile, n, per contenere questo dato. Sono possibili altre scelte. Per esempio si potrebbe sprecare una posizione del vettore, la prima, per memorizzare questa informazione. Così:

PROGRAM prodotto( INPUT, OUTPUT );

CONST

dim=100;

TYPE

numeri=ARRAY[0..dim] OF REAL;

VAR

num :numeri;

i :INTEGER; { indice }

a: REAL; { scalare }

BEGIN

{ leggi vettore }

REPEAT

WRITE('Numero elementi = ');

READLN( i ) {la cella di posizione 0 viene utilizzata per la quantità di dati }

UNTIL (i>0) AND (i<=dim);

num[0]:= i;

FOR i:=1 TO trunc(num[0]) DO BEGIN

WRITE( 'Numero di posizione ', i,' ' );

READLN( num[i] )

END;

{ calcola prodotto }

FOR i:=1 TO trunc(num[0]) DO

num[i]:=num[i]*a;

{ stampa risultati }

WRITELN( 'VETTORE RISULTATO' );

FOR i:=1 TO trunc(num[0]) DO

WRITELN( 'Posizione ', i, ' valore ', num[i] )

END.

Esercizi 2.

2.1 Dato un numero x e un vettore contare gli elementi uguali, i maggiori e i minori di x.

2.2 Dato un vettore calcolarne la media aritmetica degli elementi.

2.3 Dato un vettore di interi calcolare la media dei pari e dei dispari.

2.4 Dato un vettore di interi stampare la posizione dei pari.

Problema 3: prodotto scalare di due vettori.

Siano V e T due vettori. Il prodotto scalare TxV è un numero che si ottiene sommando il prodotto delle componenti corrispondenti. Ovviamente T e V debbono avere uguale numero di componenti.

RISULTATI: p = prodotto scalare

DATI: V e T vettori

STRUTTURE DATI:

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF REAL;

VAR

v, t :vettore;

p :REAL;

ALGORITMO:

BEGIN

leggi dati

calcola prodotto

scrivere risultati

END.

E` necessario ricordare che i due vettori debbono avere lo stesso numero di componenti per cui v[0]=t[0]. Il programma completo sarà:

PROGRAM scalare( INPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF REAL;

VAR

v, t :vettore;

p :REAL;

i :INTEGER; { indice }

BEGIN

REPEAT

WRITE( 'Numero componenti = ' );

READLN( i )

UNTIL (i>0) AND (i <=dim);

v[0]:= i;

t[0]:= i; { t e v hanno lo stesso numero di componenti }

WRITELN( 'PRIMO VETTORE ' );

FOR i:=1 TO trunc(v[0]) DO BEGIN

WRITE( 'Elemento di posizione ', i );

READLN( v[i] )

END;

WRITELN( 'SECONDO VETTORE ' );

FOR i:=1 TO trunc(t[0]) DO BEGIN

WRITE( 'Elemento di posizione ', i );

READLN( t[i] )

END;

{ calcola prodotto }

p:=0;

FOR i:=1 TO trunc(v[0]) DO

p:=p+v[i]*t[i];

WRITELN( 'Il prodotto scalare è ', p )

END.

Esercizi 3.

3.1 Sommare due vettori di interi.

3.2 Dato un vettore scambiare il primo elemento con l'ultimo, il secondo con il penultimo e così via.

3.3 Dato un vettore scambiare gli elementi di posto pari con quelli di posto dispari.

3.4 Dato un vettore calcolare la differenza tra ogni elemento e il precedente memorizzandola in un nuovo vettore.

Problema 4: convertire un numero decimale positivo in binario.

Il dato del problema è un numero intero positivo. Il risultato sarà lo stesso numero in rappresentazione binaria. E` necessario allora stabilire una struttura dati opportuna per memorizzare la rappresentazione binaria. Le scelte possibili sono molte ma se consideriamo che ogni bit può essere in solo due stati si può utilizzare un boolean. Poichè occorreranno diversi bit per ogni numero utilizzeremo un vettore di boolean con la convenzione che ogni valore true sarà interpretato come 1, ogni false 0.

RISULTATI: numero in binario

DATI: numero intero positivo

STRUTTURA DATI:

CONST

cifre = 32;

TYPE

binario = ARRAY [1..cifre] OF BOOLEAN;

VAR

bin:binario;

ALGORITMO:

BEGIN

leggi numero

converti in binario

stampa risultati

END.

Vediamo nei dettagli "converti ...".

Sia k un numero intero: la sua rappresentazione binaria è del tipo

A1 * 2^n + A2 * 2^(n -1) ... + An * 2^1 + An+1 * 2^0

An+1 è il resto di k / 2. Se si procede sino ad ottenere 0 si ottengono tutte le cifre della rappresentazione binaria. L'algoritmo sarà:

i:=0;

WHILE (val<>0) AND (i<cifre) DO BEGIN { la conversione non deve chiedere più di 32 bit e prosegue sino a quando non si ottiene 0 }

i:=i+1;

bin[i]:= (val mod 2 <> 0); { memorizzo il resto nel vettore bin }

val:= val div 2

END;

Il numero in binario ha la cifra con minor peso alla posizione 1, quella con maggior peso alla posizione i. Per stampare il numero correttamente bisognerà procedere da i a 1.

Il programma completo sarà:

PROGRAM conv_binario (INPUT , OUTPUT);

CONST

cifre = 32;

TYPE

binario = ARRAY [1..cifre] of BOOLEAN;

VAR

val, i, j ,sup : INTEGER;

bin : binario;

BEGIN

REPEAT

WRITE('inserisci numero = ');

READLN(val)

UNTIL val >= 0;

sup:= val;

{ conversione }

i:=0;

WHILE (val<>0) AND (i < cifre) DO BEGIN

i:=i+1;

bin[i]:= (val mod 2 <> 0);

val:= val div 2

END;

{ stampa rappresentazione binaria }

WRITE('La rappresentazione binaria di ', sup ,' è 0');

FOR j:= i DOWNTO 1 DO

IF bin[j] THEN

WRITE('1')

ELSE

WRITE('0');

WRITELN

END.

Esercizi 4.

4.1 Converire un numero da base A a base B.

4.2 Convertire un intero in una sequenza di caratteri e viceversa.

4.3 Convertire una sequenza di caratteri rappresentanti un numero in un real.

Problema 5: dato un vettore di numeri stampare il valore massimo.

RISULTATI: valore massimo

DATI: vettore

STRUTTURA DATI:

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

VAR

numeri:vettore;

n, { quantità di numeri da analizzare }

i:INTEGER; { indice }

max:REAL;

ALGORITMO:

BEGIN

leggi i numeri

calcola max

scrivi max

END.

L'algoritmo per il calcolo del massimo è già stato affrontato in precedenza. Vediamo cosa cambia utilizzando i vettori.

max:=numeri[1]; { inizializzazione di max }

FOR i:=2 TO n DO

IF max < numeri[i] THEN max:=numeri[i];

Il programma finale sarà:

PROGRAM massimo( INPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

VAR

numeri:vettore;

n, { quantità di numeri da analizzare }

i :INTEGER;

max :REAL;

BEGIN

REPEAT

WRITE( 'Quanti numeri? ' );

READLN( n )

UNTIL (n>0) AND (n<=dim);

FOR i:=1 TO n DO BEGIN

WRITE( 'Numero ', i, ' ');

READLN( numeri[i] )

END;

max:=numeri[1];

FOR i:=2 TO n DO

IF max < numeri[i] THEN max:=numeri[i];

WRITELN( 'Il massimo è ', max );

END.

Problema 6: dati n numeri stampare la posizione del massimo.

A prima vista il problema sembra simile al precedente: si tratta di determinare il massimo in una sequenza di numeri e quindi di stampare il numero d'ordine e non il valore. Ma se nella sequenza esistono più valori uguali al massimo non basta una variabile scalare ma occorre memorizzare i numeri d'ordine dei massimi in un vettore. Formalizzando avremo:

RISULTATI: le posizioni del massimo

DATI: i numeri da analizzare

STRUTTURE DATI

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

posizione=ARRAY[1..dim] OF INTEGER;

{ i due vettori hanno la stessa dimensione massima perchè se i numeri fossero tutti uguali ..... }

VAR

numeri :vettore; { numeri da analizzare }

m :posizione; { indici del massimo }

n, { quantità di numeri da analizzare }

n_m, { quantità di indici inseriti in m }

i :INTEGER; { indice per percorre i numeri }

max :REAL; { valore massimo }

Per quanto riguarda l'algoritmo osserviamo che, dato un numero, si potranno verificare tre casi:

- il numero è uguale al massimo: si deve aggiungere nel vettore dei massimi il nuovo indice

- il numero è minore del massimo: si passa al successivo

- il numero è maggiore del massimo: tutti i precedenti indici memorizzati nel vettore dei massimi devono essere eliminati e sostituiti con il nuovo indice

Si può allora osservare che ogni qual volta viene modificato il valore massimo si deve annullare il contenuto del vettore m, e quindi inserire il nuovo indice, mentre quando il valore è uguale al massimo si deve solo aggiungere il nuovo indice. L'algoritmo per il confronto sarà:

IF numeri[i] > max THEN BEGIN

max:=numeri[i]; { modifica del massimo con }

n_m:=0; { annullamento degli elementi in m }

n_m:=n_m+1 { ed inserimento nuovo valore }

m[n_m]:=i

END ELSE IF numeri[i] = max THEN BEGIN

n_m:=n_m+1; { predisposto l'indice di m }

m[n_m]:=i { inserimento nuovo valore }

END

Come abbiamo già osservato in precedenti problemi è necessario inizializzare il massimo con il primo valore da esaminare. In questo caso, poichè ad ogni modifica di max deve essere aggiornato il vettore m, dovremo operare l'inizializzazione così:

max:=numeri[1]; { si inizializza max con il primo valore, }

n_m:=1; { il numero di massimi trovato ad 1, }

m[n_m]:=1; { l'indice del massimo nel vettore m }

Il programma completo sarà:

PROGRAM massimo( INPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

posizione=ARRAY[1..dim] OF INTEGER;

VAR

numeri :vettore; { numeri da analizzare }

m :posizione; { indici del massimo }

n, { quantità di numeri da analizzare }

n_m, { quantità di indici inseriti in m }

i :INTEGER; { indice per percorre i numeri }

max :REAL; { valore massimo }

BEGIN

{ inserimento dei valori }

REPEAT

WRITE( 'Quanti numeri? ' );

READLN( n )

UNTIL (n>0) AND (n<=dim);

FOR i:=1 TO n DO BEGIN

WRITE( 'Numero ', i, ' = ');

READLN( numeri[i] )

END;

{ inizializzazione }

max:=numeri[1];

n_m:=1;

m[n_m]:=1;

{ ricerca posizioni del massimo }

FOR i:=2 TO n DO BEGIN

IF numeri[i] > max THEN BEGIN

max:=numeri[i];

n_m:=0;

n_m:=n_m+1;

m[n_m]:=i

END ELSE

IF numeri[i] = max THEN BEGIN

n_m:=n_m+1;

m[n_m]:=i

END

END;

{ stampa degli indici }

WRITELN('Le posizioni del massimo sono: ');

FOR i:=1 TO n_m DO

WRITELN(m[i])

END.

Problema 7: dato un vettore v di numeri e un numero x stampare la posizione della prima occorenza di x in v.

RISULTATI: posizione di x

DATI: x = numero da ricercare

v = vettore di numeri

STRUTTURA DATI

CONST

dim=100;

TYPE

numeri=ARRAY[1..dim] OF INTEGER;

VAR

v :numeri;

x, { numero da ricercare }

n, { numero di elementi di v }

i, :INTEGER; { indice per percorrere v }

ALGORITMO:

Dato un vettore v ed un valore x si possono verificare tre casi:

- x non è presente in v

- x è presente una sola volta

- x è presente più di una volta

Il testo del problema richiede che in caso di più di una presenza venga segnalata solo la prima. Allora il secondo e il terzo caso si possono identificare. In prima analisi l'algoritmo di ricerca sarà:

i:=0;

REPEAT

i:=i+1

UNTIL v[i]=x;

Si può subito osservare che tale algoritmo è corretto solo se x è presente in v, altrimenti la condizione di fine ciclo non sarà mai verificata. Si può ovviare a questo inconveniente facendo in modo che tale condizione sia sempre verificata aggiungendo nel vettore, all'ultima posizione, l'elemento da ricercare.

v[n+1]:=x; i:=0;

REPEAT

i:=i+1

UNTIL v[i]=x;

In questo modo l'algoritmo terminerà sempre. Per sapere se l'elemento x è effettivamente contenuto in v si confronta l'indice i con n+1: se i=n+1 allora x non è presente in v, altrimenti x è presente alla posizione i. L'algoritmo che abbiamo presentato si chiama ricerca con sentinella.

Il programma completo sarà:

PROGRAM sentinella( INPUT, OUTPUT );

CONST

dim=100;

TYPE

numeri=ARRAY[1..dim] OF INTEGER;

VAR

v :numeri;

x, { numero da ricercare }

n, { numero di elementi di v }

i, :INTEGER; { indice per percorrere v }

BEGIN

{ lettura vettore come nei problemi precedenti }

{ ricerca con sentinella }

v[n+1]:=x; i:=0;

REPEAT

i:=i+1

UNTIL v[i]=x;

{ stampa risultato }

IF i=n+1 THEN WRITELN('NON TROVATO ')

ELSE WRITELN('TROVATO ALLA POSIZIONE ',i);

END.

E` possibile utilizzare l'algoritmo di ricerca con sentinella tutte le volte che il vettore non è completamente occupato. Infatti se n=dim non si può svolgere l'operazione v[n+1]=x.

Esercizi 5.

5.1 Stampare tutte le posizioni occupate da un numero x in un vettore v.

5.2 Ricerca di un elemento in un vettore nel caso in cui n=dim

Problema 8: dato un vettore di numeri modificarlo inserendo alla prima posizione il valore massimo.

Il testo del problema è chiaro sia per quanto riguarda l'obiettivo, sia per i risultati, i dati, e le strutture dati da utilizzare.

RISULTATI: vettore modificato

DATI: vettore di numeri

STRUTTURA DATI:

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

VAR

v :vettore;

ALGORITMO:

Per spostare il valore massimo alla prima posizione sarà necessario non solo conoscerne il valore ma anche la sua posizione per scambiarlo con il primo. L'algoritmo sarà:

i_max = posizione del massimo

scambia il contenuto della cella 1 con quella i_max

Per quanto riguarda la ricerca della posizione del massimo osserviamo che non serve conoscerle tutte. Possiamo allora sfruttare l'algoritmo visto in precedenza, utilizzando però una variabile scalare e non un vettore per memorizzare la posizione. Nel dettaglio:

{ inizializzazione }

max:=numeri[1];

i_max:=1;

{ ricerca del massimo }

FOR i:=2 TO n DO BEGIN

IF numeri[i] > max THEN BEGIN

max:=numeri[i];

i_max:=i;

END;

Il programma completo sarà:

PROGRAM max_in_prima( IMPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[1..dim] OF REAL;

VAR

numeri :vettore;

i,

i_max, { indice del massimo }

n :INTEGER; { numero elementi di v }

max :REAL;

BEGIN

leggi n numeri

max:=numeri[1]; { inizializza max e }

i_max:=1; { i_max }

{ ricerca della posizione del massimo }

FOR i:=2 TO n DO

IF v[i]>max THEN BEGIN

max:=numeri[i];

i_max:=i;

END;

numeri[i_max]:=numeri[1]; { scambia l'elemento di posizione }

numeri[1]:=max; { i_max con quello di posizione 1 }

END.

Problema 9: ordinare in ordine decrescente un vettore di numeri.

L'obiettivo, il risultato e i dati sono chiari. Per quanto riguarda l'algoritmo riprendiamo quanto svolto nel problema 8.

Si può pensare di ordinare un vettore ricercando il massimo e spostandolo alla prima posizione, poi tra i rimanenti si può nuovamente ricercare il massimo, spostandolo alla seconda posizione, e così via sino a quando non si arriva all'ultimo elemento. Si tratta in pratica di ripetere l'algoritmo precedente tante volte quanti sono gli elementi da ordinare. Il nuovo algoritmo sarà:

BEGIN

FOR k:=1 TO n DO

cerca il massimo tra gli ultimi n-k elemnti e portalo alla posizione k

END.

dove con "cerca il massimo ....." si intende l'algoritmo descritto prima.

La stesura definitiva sarà:

BEGIN

FOR k:=1 TO n DO BEGIN

max:=v[k]; { la prima volta k=1, la seconda si parte da due etc }

i_max:=k; { la prima volta i_max=1, la seconda i_max=2, etc }

{ si ricerca il massimo tra i rimanenti n-k elementi }

FOR i:=k+1 TO n DO

IF v[i]>max THEN BEGIN

max:=v[i];

i_max:=i;

END;

v[i_max]:=v[k]; { scambia l'elemento di posizione }

v[k]:=max; { i_max con quello di posizione k }

END;

END.

Come ultima osservazione si può notare che il primo ciclo FOR può essere terminato quando k=n-1.

Problema 10: inserire un elemento in un vettore ordinato mantenendo l'ordinamento.

Obiettivo, risultati e dati sono chiaramente espressi nel problema. Per quanto riguarda la struttura dati utilizziamo un vettore di real memorizzando nella prima posizione la dimensione.

STRUTTURA DATI:

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF REAL;

VAR

v :vettore;

ALGORITMO:

Per inserire un nuovo elemento mantenendo l'ordinamento del vettore si devono spostare tutti gli elementi del vettore, a partire dall'ultimo sino a quando non si arriva alla posizione giusta e quindi inserire il nuovo elemento.

i:=trunc(v[0])+1;

WHILE non è posizione giusta DO BEGIN

v[i]:=v[i-1];

i:=i-1

END;

v[ posizione giusta ]:=x;

La posizione giusta sarà quella per cui v[i-1]<x<v[i]. Sicuramente se x è minore di tutti gli elementi la "posizione giusta" sarà la prima, mentre se è maggiore di tutti sarà l'ultima. La condizione di fine ciclo sarà allora:

WHILE (i>1) AND (v[i-1]>x) DO

Alla fine del ciclo i sarà tale per cui v[i-1]<=x<v[i] oppure sarà i=1 per cui l'inserimento avverrà alla posizione i.

Si può anche osservare che se x> ultimo elemento del vettore la condizione del ciclo sarà subito falsa. Il programma completo sarà:

PROGRAM ins_ord( INPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF REAL;

VAR

v :vettore;

nuovo :REAL;

i :INTEGER;

BEGIN

{ lettura vettore }

REPEAT

WRITE( 'Numero elementi = ' );

READLN( i );

UNTIL (i>0) AND (i<dim); { deve esserci lo spazio per

il nuovo elemento }

v[0]:=i; { v[0] = dimensione del vettore }

{ inserimento crescente degli elementi }

WRITE( 'Elemento di posizione ', 1 );

READLN( v[1] );

FOR i:=2 TO trunc(v[0]) DO

REPEAT

WRITE( 'Elemento di posizione ', i, ' ' );

READLN( v[i] )

UNTIL v[i]>v[i-1];

WRITE( 'Nuovo elemento = ' );

READLN( nuovo );

{ inserimento del nuovo elemento nel vettore }

i:=trunc(v[0]);

WHILE (i>1) AND (v[i-1]> nuovo) DO BEGIN }

v[i]:=v[i-1];

i:=i-1

END;

v[i]:=nuovo;

v[0]:=v[0]+1; { aggiorna il numero di elementi }

FOR i:=1 TO trunc(v[0]) DO

WRITELN( 'Elemento di posizione ', i, ' = ', v[i] );

END.

Problema 11: dati due vettori ordinati di numeri fonderli in un nuovo vettore mantenendo l'ordinamento.

Il problema presentato è conosciuto come problema di merge. L'obiettivo, il risultato e i dati sono chiaramente espressi nel testo. La struttura dati che utilizzeremo sarà simile a quella del problema precedente. Osserviamo solo che il nuovo vettore avrà numero di elementi uguale alla somma del numero di elementi dei due vettori iniziali.

STRUTTURA DATI:

CONST

dim=100;

dim2=200;

TYPE

vettore =ARRAY[0..dim] OF REAL;

vettorone=ARRAY[0..dim2] OF REAL;

VAR

v1,v2 :vettore;

v3 :vettorone;

i,j,k,

n1,n2,n3 :integer;

ALGORITMO: Supponiamo che i due vettori v1 e v2 siano ordinati in ordine crescente. L'algoritmo sarà

BEGIN

i:=1; { elemento da analizzare in v1 }

j:=1; { elemento da analizzare in v2 }

WHILE non sono finiti i due vettori DO

IF v1[i]<v2[j] THEN BEGIN

inserisci nel terzo v1[i];

i:=i+1; { passa al successivo in v1 }

END

ELSE BEGIN

inserisci nel terzo v2[j];

j:=j+1; { passa al successivo in v2 }

END;

Per controllare la fine dei vettori si deve confrontare rispettivamente i con il numero di elementi di v1 e j con il numero di elementi di v2. Così:

n1:=trunc(v1[0]); { numero elementi di v1 }

n2:=trunc(v2[0]); { numero elementi di v2 }

i:=1; j:=1;

WHILE (i<=n1) AND (j<=n2) DO

Per inserire nel terzo vettore è necessario utilizzare un indice, inizializzato a 1 per individuare la posizione. L'algoritmo completo sarà:

BEGIN

n1:=trunc(v1[0]);

n2:=trunc(v2[0]);

i:=1; j:=1;

k:=1; { posizione dove inserire in v3 }

WHILE (i<=n1) AND (j<=n2) DO BEGIN

IF v1[i] <= v2[j] THEN BEGIN

v3[k]:=v1[i];

i:=i+1

END

ELSE BEGIN

v3[k]:=v2[j];

j:=j+1

END;

k:= k+1 { passa al successivo in v3 }

END;

{ se v1 non è finito copia tutti gli elementi che rimangono in v3 }

WHILE (i<=n1) DO BEGIN

v3[k]:=v1[i];

i:=i+1;

k:=k+1

END;

{ se v2 non è finito copia tutti gli elementi che rimangono in v3 }

WHILE (j<=n2) DO BEGIN

v3[k]:=v2[j];

j:=j+1;

k:=k+1

END;

n3:=k-1;

v3[0]:=k-1

END.

Problema 12: cancellazione di un elemento di posizione i da un vettore ordinato.

Obiettivo, risultati e dati sono chiaramente espressi nel problema. Per quanto riguarda la struttura dati utilizziamo una struttura identica a quella del problema precedente.

ALGORITMO:

Per "cancellare" l'elemeto di posizione p da un vettore è necessario scorrere tutti gli elementi successivi di una posizione. L'algoritmo sarà:

FOR i:=p TO trunc(v[0])-1 DO

v[i]:=v[i+1];

Se p indica l'ultima posizione del vettore il ciclo for non sarà eseguito. Il programma completo sarà:

PROGRAM cancella( INPUT, OUTPUT );

CONST

dim=100;

TYPE

vettore=ARRAY[0..dim] OF REAL;

VAR

v :vettore;

posizione,

i :INTEGER;

BEGIN

{ la lettura vettore sarà identica a quella svolta nell'esempio precedente }

{ lettura indice }

REPEAT

WRITE( 'Posizione da cancellare ' );

READLN( posizione )

UNTIL (posizione>0) AND (posizione<=trunc(v[0]));

{ cancellazione elemento }

FOR i:=posizione TO trunc(v[0])-1 DO

v[i]:=v[i+1];

v[0]:=v[0]-1; { aggiornamento numero elementi }

FOR i:=1 TO trunc(v[0]) DO

WRITELN( 'Elemento di posizione ', i, ' = ', v[i] );

END.

N.B. Se il vettore non fosse ordinato l'algoritmo di cancellazione diventa:

n:=trunc(v[0]);

v[p]:=v[n];

v[0]:=v[0]-1;

Problema 13: dati due vettore di caratteri determinare il maggiore.

Il testo del problema non fornisce indicazioni sul criterio di confronto da adottare. Considerando che si lavora con vettori di caratteri scegliamo l'ordinamento alfabetico. Allora il problema è così riformulato: dati due nomi indicare quale dei due precede in ordine alfabetico.

RISULTATI: primo maggiore secondo |

secondo maggiore primo |

uguali

DATI: due nomi inseriti in due vettori di caratteri

STRUTTURE DATI:

CONST

dim=254;

TYPE

nome=ARRAY[1..dim] OF CHAR;

VAR

a,b :nome;

dim_a, dim_b,

i :INTEGER;

ALGORITMO

BEGIN

leggi a

leggi b

confronta a, b

scrivi risultato

END.

L'algoritmo proposto deve essere analizzato con cura. Le operazioni di lettura non dovrebbero più presentare problemi. E` necessario però ricordarsi che vogliamo inserire dei nomi, per cui potrebbe risultare scomodo per l'operatore inserire un carattere alla volta seguito da <return>. Una possibile soluzione è la seguente:

i:=0;

WRITELN('Primo nome (* per finire) ');

REPEAT

i:=i+1;

READ(a[i]);

UNTIL a[i]='*';

READLN;

dim_a:=i-1;

In questo modo l'operatore inserirà il nome terminando con un carattere '*' per segnalare la fine del nome stesso. Similmente si procederà per b. Inoltre il nome non dovrà essere maggiore di 253 caratteri.

L'operazione "confronta a, b" va analizzata con attenzione. Nell'algoritmo proposto il confronto e la stampa dei risultati sono operazioni separate. Questo significa che il risultato del confronto deve in qualche maniera essere memorizzato in una variabile per poterlo poi utilizzare nell'operazione successiva. Considerando poi che i possibili risultati di un confronto sono tre (uguale, maggiore, minore) ma tra di loro esclusivi, si può utilizzare una variabile scalare nelle quale memorizzare tre valori diversi. In fase di stampa si assocerà ad ognuno dei tre valori un significato particolare. Ad esempio si può utilizzare un intero. I possibili risultati saranno:

un valore negativo --> a < b

zero --> a=b

un valore positivo --> a > b

Tenuto conto poi che i nomi sono terminati da '*' l'algoritmo sarà:

i:=0

REPEAT

i:=i+1;

UNTIL ( a[i]='*') OR ( a[i]<>b[i] );

risultato:=ORD(a[i])-ORD(b[i]);

"scrivi risultato" dovrà verificare se risultato è >, =, < 0 e stampare il messaggio opportuno. Il programma completo sarà:

PROGRAM confronto( INPUT, OUTPUT );

CONST

dim=254;

TYPE

nome=ARRAY[1..dim] OF CHAR;

VAR

a,b :nome;

i,

risultato :INTEGER;

BEGIN

{ inserimento nomi }

i:=0;

WRITELN('Primo nome (* per finire) ');

REPEAT

i:=i+1;

READ(a[i]);

UNTIL a[i]='*';

READLN;

i:=0;

WRITELN('Secondo nome (* per finire) ');

REPEAT

i:=i+1;

READ(b[i]);

UNTIL b[i]='*';

READLN;

{ confronto tra i nomi }

i:=0;

REPEAT

i:=i+1;

UNTIL ( a[i]='*') OR ( a[i]<>b[i] );

risultato:=ORD(a[i])-ORD(b[i]);

{ stampa del risultato }

IF risultato=0 THEN WRITELN( 'Uguali ' )

ELSE IF risultato<0 THEN WRITELN( 'Primo precede secondo' )

ELSE WRITELN( 'Secondo precede primo' );

END.

Ricordiamo ancora una volta che il confronto tra lettere avviene in base al codice ascii per cui il programma proposto sarà corretto solo se le parole da confrontare conterranno solo o lettere maiuscole o lettere minuscole.

Problema 14: dato un nome riscriverlo utilizzando solo lettere maiuscole.

Il problema non è chiaramente formulato. Bisogna intendersi sul significato di riscriverlo. Basta avere in output il nome scritto con caratteri maiuscoli o vogliamo memorizzarlo in un vettore? Supponiamo di scegliere la seconda via.

RISULTATO nome maiuscolo

DATI nome

STRUTTURE DATI

CONST

dim=254;

TYPE

stringa=ARRAY[1..dim] OF CHAR;

VAR

nome:stringa;

ALGORITMO

BEGIN

leggi nome

modifica nome

stampa nome

END.

"leggi nome" e "stampa nome" sono lasciate al lettore. Affrontiamo invece "modifica nome".

Un modo banale per sostituire le lettere minuscole con le corrispondenti maiuscole potrebbe essere una serie di confronti del tipo

IF nome[i]='a' THEN nome[i]='A';

IF nome[i]='b' THEN ...........

...............................

e così per tutte le lettere. Ma e ` possibile fare meglio se consideriamo che qualunque sia la lettera maiuscola X

ord( x ) - ord( X ) = costante

dove con x si è indicato la corrispondente lettera minuscola.

Allora potremmo scrivere il seguente algoritmo di conversione:

i:=1;

WHILE nome[i] <> '*' DO BEGIN

IF (nome[i]>='a') AND (nome[i]<='z') THEN

nome[i]:=CHR( ORD(nome[i])-ORD('a')+ORD('A') );

i:=i+1;

END;

Il programma completo sarà:

PROGRAM maiuscolo( INPUT, OUTPUT );

CONST

dim=254;

TYPE

stringa=ARRAY[1..dim] OF CHAR;

VAR

nome :stringa;

i :INTEGER;

BEGIN

{ lettura nome }

i:=0;

WRITELN('Primo nome (* per finire) ');

REPEAT

i:=i+1;

READ(nome[i]);

UNTIL nome[i]='*';

READLN;

{ maiuscolizzazione }

i:=1;

WHILE nome[i] <> '*' DO BEGIN

IF (nome[i]>='a') AND (nome[i]<='z') THEN

nome[i]:=CHR( ORD(nome[i])-ORD('a')+ORD('A') );

i:=i+1;

END;

{ stampa }

i:=1;

WHILE nome[i]<>'*' DO BEGIN

WRITE( nome[i] );

i:=i+1

END;

WRITELN;

END.

Negli esempi precedenti si è utilizzato un algoritmo per inserire i nomi che non controlla se il nome è troppo lungo. Vediamo allora di modificarlo per eliminare questa possibile fonte di errore. Una possibile soluzione è la seguente:

nome[dim]:='*';

i:=0;

REPEAT

i:=i+1;

READ(nome[i]);

UNTIL (nome[i]='*') OR (i=dim-1);

In questo modo si ha la garanzia che il nome sia sempre terminato da * e che non sarà più lungo del vettore predisposto per contenerlo.

Problema 15: dato un nome terminato dal carattere * stamparne la lunghezza.

L'obiettivo e il risultato del problema sono chiari.Per quanto riguarda l'algoritmo, considerando che il nome è terminato dal carattere * e che sarà memorizzato in un vettore a partire dalla prima posizione, si può calcolare la lunghezza ricercando nel vettore la posizione del carattere *.

RISULTATO: lunghezza nome

DATO: nome

STRUTTURA DATI vedi problema 7

ALGORITMO

BEGIN

leggi nome

posizione:=indice del carattere *

lunghezza:=posizione-1;

WRITELN('Lunghezza = ', lunghezza);

END.

Analizziamo "indice del carattere * ". E` un problema di ricerca. Sapendo con certezza che il carattere da ricercare è presente nel vettore si può operare così:

i:=0;

REPEAT

i:=i+1;

UNTIL nome[i]='*';

Il programma completo sarà:

PROGRAM lunome( INPUT, OUTPUT );

CONST

dim=254;

TYPE

nome=ARRAY[1..dim] OF CHAR;

VAR

a :nome;

i,

lunghezza :INTEGER;

BEGIN

i:=0;

WRITELN('Nome (* per finire) ');

REPEAT

i:=i+1;

READ(a[i]);

UNTIL a[i]='*';

READLN;

i:=0;

REPEAT

i:=i+1;

UNTIL ( a[i]='*');

lunghezza:=i-1;

WRITELN( 'La lunghezza è ', lunghezza );

END.

Esercizi 6.

6.1 Chiamiamo stringa il vettore di caratteri presentato nel problema 14. Risolvere i seguenti problemi:

a- Data una stringa eliminare gli eventuali blank finali.

b- Concatenare due stringhe.

c- Data una stringa s copiare in una stringa s1 tutti i caratteri a partire da una determinata posizione p e per lunghezza l.

d- Data una stringa s e una stringa s1 indicare la prima occorrenza di s1 in s.

e- Data una stringa s riscriverla eliminando tutti i blank.

f- Data una stringa s riscriverla eliminando tutti i caratteri a partire da una determinata posizione p e per lunghezza l.

Problema 16: dato un vettore di caratteri maiuscoli, stampare le occorrenza per ogni lettera.

I dati per questo problema sono chiari. Per quanto riguarda i risultati sappiamo che dobbiamo contare tutte le occorrenze delle lettere maiuscole dell'alfabeto per cui sarà necessario un contatore per ogni lettera.

STRUTTURA DATI:

CONST

dim = 254;

TYPE

stringa=ARRAY[1..dim] OF CHAR;

contatori=ARRAY['A'..'Z'] OF INTEGER;{ un contatore per ogni lettera }

VAR

s:stringa;

c:contatori;

i:CHAR; { indice per percorrere il vettore c }

k:INTEGER; { indice per percorrere il vettore s }

DATI: s = nome in input con sole lettere maiuscole

RISULTATI: c = contatori

ALGORITMO:

azzera i contatori

per ogni lettera incrementa il contatore corrispondente

Sviluppando nel dettaglio sarà:

{ azzera }

FOR i:='A' TO 'Z' DO

c[i]:=0;

{ incrementa }

k:=1;

WHILE s[k]<>'*' DO BEGIN

c[ s[k] ]:=c[ s[k] ] + 1;

k:=k+1;

END;

Problema 17: supponendo di utilizzare un vettore di caratteri che ha alla prima posizione la dimensione, inserire una sottostringa in una stringa a partire da una prefissata posizione.

Esempio: La stringa a = Marcello

la stringa b = in

Se si inserisce b in a alla posizione 8 si ottiene Marcellino

La struttura dati da utilizzare è definita nel testo:

STRUTTURA DATI:

CONST

dim=254;

TYPE

nome=ARRAY[0..dim] OF CHAR;

VAR

a,b :nome;

Alla posizione 0 è memorizzata la lunghezza sotto forma di carattere. Per leggere correttamente la lunghezza scriveremo:

lunghezza:=ord( a[0] );

Dove lunghezza è una variabile di tipo integer.

Per modificarla scriveremo:

a[0]:=chr( nuova_lunghezza );

dove nuova_lunghezza è una variabile di tipo integer il cui valore deve essere compreso tra 0 e 255.

RISULTATI: a = vettore modificato

DATI: a = nome iniziale

b = sottostringa da utilizzare per la modifica

p= posizione in cui inserire b in a

ALGORITMO:

Prima di iniziare la stesura dell'algoritmo stabiliamo che, se aggiungendo b ad a si supera la dimensione massima di a, la nuova parola sarà troncata. Inoltre supponiamo che p sia un "numero corretto".

In prima stesura l'algoritmo di inserimento potrebbe essere:

"crea il buco" nel vettore a

copia il vettore b in a partendo da p

In un problema precedente abbiamo già affrontato "crea il buco" ma per inserire un solo elemento. In questo caso però dovremo inserire tanti elementi quanti quelli di b. Allora crea buco sarà:

len_a:=ord(a[0]); len_b:=ord(b[0]);

FOR i:=len_a DOWNTO p DO { per tutte le lettere dopo p }

a[i+len_b]:=a[i]; { sposta l'elemento di len_b posizioni }

Prima di procedere osserviamo ancora che i+len_b potrebbe essere maggiore di dim. L'algoritmo dovrà essere così modificato:

len_a:=ord(a[0]); len_b:=ord(b[0]);

FOR i:=len_a DOWNTO p DO

IF (i+len_b) <= dim THEN { se ci stà spostalo }

a[i+len_b]:=a[i];

Per copiare il vettore b in a

i:=posizione; j:=1;

WHILE (j<=len_b) AND (i<=dim) DO BEGIN { inserisci nel buco } a[i]:=b[j];

i:=i+1;

j:=j+1

END;

Dovremo inoltre ricordarci di aggiornare la nuova lunghezza di a. Il programma completo sarà:

PROGRAM instringa( INPUT, OUTPUT );

CONST

dim=254;

TYPE

nome=ARRAY[0..dim] OF CHAR;

VAR

a, { nome }

b :nome; { sottostringa }

i, j,

p, { posizione di inserimento }

len_a, len_b :INTEGER;

BEGIN

{ lettura stringhe }

i:=0;

WRITELN('Primo nome (* per finire) ');

REPEAT

i:=i+1;

READ(a[i])

UNTIL a[i]='*';

READLN;

a[0]:=chr(i-1); { aggiornamento contatore caratteri }

i:=0;

WRITELN('stringa da inserire (* per finire) ');

REPEAT

i:=i+1;

READ(b[i]);

UNTIL b[i]='*';

READLN;

b[0]:=chr(i-1); { aggiornamento contatore caratteri }

WRITE( 'Posizione dove inserire ' );

READLN( p );

{ inserisci b in a }

len_a:=ord(a[0]); len_b:=ord(b[0]);

FOR i:=len_a DOWNTO p DO { crea buco per inserire }

IF (i+len_b) <= dim THEN

a[i+len_b]:=a[i];

i:=p; j:=1;

WHILE (j<=len_b) AND (i<=dim) DO BEGIN { inserisci nel buco }

a[i]:=b[j];

i:=i+1;

j:=j+1

END;

{ aggiorna contatore della stringa a }

IF (len_a+len_b) <=dim THEN a[0]:=chr(len_a+len_b)

ELSE a[0]:=chr(dim);

FOR i:=1 TO ord(a[0]) DO

WRITE( a[i] );

WRITELN

END.

Il programma che abbiamo presentato può generare errori se p > len_a+1 o p< 1.

Esercizi 7.

7.1 Con la struttura dati presentata nel problema 15 risolvere i seguenti problemi:

a- Data una stringa s determinarne la lunghezza.

b- Concatenare due stringhe.

c- Data una stringa s copiare in una stringa s1 tutti i caratteri a partire da una determinata posizione p e per lunghezza l.

d- Data una stringa s e una stringa s1 indicare la prima occorrenza di s1 in s.

e- Data una stringa s riscriverla eliminando i blank.

f- Data una stringa s riscriverla eliminando tutti i caratteri a partire da una determinata posizione p e per lunghezza l.

6.5 Packed Array.

In Pascal è possibile definire una variabile packed. In questo modo si segnala all'esecutore pascal di riservare lo spazio minimo indispensabile per contenerla. Anche un vettore può essere definito packed premettendo la parola riservata PACKED alla definizione del vettore.

Esempio.

TYPE

numero=PACKED ARRAY[1..64] OF BOOLEAN;

In questo esempio numero è un vettore di 64 bit. L'accesso a ciascun bit avviene esattamente come nel caso di ARRAY.

Molto importante è il caso del vettore di caratteri.

TYPE

stringa=PACKED ARRAY[1..64] OF CHAR;

Anche in questo caso è possibile accedere alle singole celle del vettore come se fosse un ARRAY. Però è possibile utilizzare una variabile di tipo stringa come se fosse una variabile scalare.

Sia

VAR

a, b :stringa;

E' possibile leggere e scrivere le variabili a e b:

READLN( a );

WRITELN( a, b );

E' possibile l'assegnazione:

a:=b;

a:='Elisa'; { a[1]=E, a[2]=l, a[3]=i, a[4]=s, a[5]=a }

E' possibile il confronto in base alla tabella ascii

a:='Elisa'

b:='Elena'

IF a>b THEN WRITELN( 'a segue b');

ELSE WRITELN( 'a precede b' );

Poichè Elena precede Elisa in ordine alfabetico il messaggio stampato sarà il primo.