Esercizi svolti a lezione il 16 Novembre 2000 & Esercizi proposti

(ATTENZIONE: chi trova un errore in questa pagina ricevera' un premio!!!)

Questa lezione (e gli esercizi proposti) hanno un duplice scopo:
  1. "conquistare" una maggiore padronanza (capire quando e come devono essere usati) di array e i cicli
  2. mostrare che non sempre si arriva immediatamente alla scrittura di un buon codice. L'importante e' scrivere fin dall'inizio il codice in modo "consapevole" (cioe' mettendo commenti, invarianti, e altre asserzioni). Il codice scritto in questo modo potra' poi essere successivavente migliorato.

Copiare un array di interi in un altro al rovescio

Scriviamo una procedura che compie questa operazione.
Supponiamo di avere a disposizione una costante e un tipo: 

const LungVett = 100;
type VettInt = array [1..LungVett] of integer;

Scriviamo quindi una procedura copiaInv, che potra' essere usata in ogni programma in cui sono disponibili le dichiarazioni precedenti.

La prima procedura che abbiamo trovato e' stata la seguente (durante la lezione abbiamo disegnato sulla lavagna gli array a e b e gli indici i e j, abbiamo fatto le operazioni a mano e, traducendo da ITALIANO a PASCAL e' venuta fuori questa procedura), non e' particolarmente elegante, ma siamo ragionevolmente sicuri che e' corretta. 

{Assume 1<=n<=MaxVett.
 Non modifica a.
 Copia a[1],...,a[n] rispettivamente in b[n],...,b[1].}
procedure copiaInv(var a:VettInt; {a e' dichiarato var per risparmiare memoria}
                   var b:VettInt;
                   n:integer);

{--------------------------------------------------}
var 
    i:integer; {indice di b}
    j:integer; {indice di a}

begin
  i:=1; {i all'inizio di b}
  j:=n; {j alla fine a}
  b[i]:=a[j];
  while n>i do {1<=i<=n, j=n-i+1, e
                  b[1],...,b[i] contengono 
                  rispettivamente a[n],...,a[j]}
    begin
      i:=i+1;
      j:=j-1;
      b[i]:=a[j]; 
    end;
   {b[1],...,b[n] contengono rispettivamente a[n],...,a[1]}
end;
{--------------------------------------------------}

Cerchiamo di migliorare la procedura precedente. Per prima cosa risciviamola eliminando la variabile locale j (l'intestazione della procedura non cambia): 

{--------------------------------------------------}
var 
    i:integer; {Contatore usato nel ciclo while}

begin
   i:=1;
   b[1]:=a[n];
   while n>i do {1<=i<=n, e
                 b[1],...,b[i] contengono 
                 rispettivamente a[n],...,a[n-i+1]}
     begin
       i:=i+1;
       b[i]:=a[n-i+1]; 
     end;
end;
{--------------------------------------------------}

Ora proviamo a riscrivere la procedura usando un repeat (l'intestazione della procedura non cambia): 

{--------------------------------------------------}
var 
    i:integer; {Contatore usato nel ciclo repeat}

begin
   i:=0;
   repeat
     begin
       i:=i+1;
       b[i]:=a[n-i+1]; 
     end;
   until i=n do {b[1],...,b[i] contengono 
                 rispettivamente a[n],...,a[n-i+1]}
end;
{--------------------------------------------------}
Proviamo a riscrivere la procedura usando un for (l'intestazione della procedura non cambia). L'operazione e' abbastanza semplice: e' sufficiente sciverre un for che esegua l'assegnamento b[i]:=a[n-i+1] per tutti i valori di i per cui tale assegnamento veniva eseguito nel precedente ciclo repeat. 


{--------------------------------------------------}
var 
    i:integer; {Contatore usato nel ciclo for}

begin
   for i:=1 to n do 
     b[i]:=a[n-i+1]; {b[1],...,b[i] contengono 
                      rispettivamente a[n],...,a[n-i+1]}
end;
{--------------------------------------------------}

Ricordiamo che (in Turbo Pascal): 

   for j:=h to k do
     begin
       S
     end;
e' equivalente a: 

   j:=h;
   while j<=k do
     begin
       S;
       j:=j+1;
     end;

Proviamo quindi a tradurre il for usato in precedenza in un while: 

{--------------------------------------------------}
var 
    i:integer; {Contatore usato nel ciclo while}

begin
   i:=1;
   while i<=n do 
     begin
       b[i]:=a[n-i+1]; 
       {1<=i<=n, e b[1],...,b[i] contengono rispettivamente a[n],...,a[n-i+1]}
       i:=i+1;
     end;
end;
{--------------------------------------------------}

Spostiamo ora l'asserzione al punto in cui viene valutato il test del ciclo, il posto "standard" per l'invariante di un while: 

{--------------------------------------------------}
var 
    i:integer; {Contatore usato nel ciclo while}

begin
   i:=1;
   while i<=n do {1<=i<=n+1, e
                 b[1..i-1] contiene a[n-i+2..n] rovesciato
                 (al solito usiamo la convenzione per cui, 
                  se inf>sup allora b[inf..sup] e a[inf..sup] sono vuoti e 
                  l'asserzione e' vera)}
     begin
       b[i]:=a[n-i+1]; 
       i:=i+1;
     end;
end;
{--------------------------------------------------}

Quest'ultimo ciclo while e' decisamente piu' elegante del ciclo while che abbiamo usato nella prima e nella seconda versione della procedura. In particolare questo ultimo ciclo while

tratta in modo uniforme tutte le componenti dell'array

(come dovrebbe sempre avvenire in un ciclo ben scritto). Anche i cicli repeat e for che abbiamo scitto in precedenza sono buoni cicli: trattano in modo uniforme tutte le componenti dell'array.

Esercizi proposti

Esercizi 

1. Scrivete una procedura che soddisfa la seguente specifica.


{Assume 1<=inf<=MaxVett, e
        1<=sup<=MaxVett,
 Non modifica a.
 Se inf>=sup non fa nulla.
 Copia a[inf..sup] al rovescio in b[inf..sup].}
procedure copiaInv(var a:VettInt; {a e' dichiarato var per risparmiare memoria}
                   var b:VettInt;
                  inf,sup:integer);

Soluzioni (NON ANCORA PRESENTI)