Lezione del 30 Ottobre 2001

Il ciclo "while" e il ciclo "for". Gli invarianti di ciclo.

COSA E' STATO FATTO A LEZIONE

Questo documento contiene un RIASSUNTO degli argomenti presentati a lezione. Per eventuali chiarimenti rivolgersi al docente.

Un esempio di problema che puo' essere risolto con un ciclo "while"

Problema:Scrivere un programma Pascal che legga da terminale due numeri interi A, B e scriva su teminale la somma di tutti i numeri compresi nell'intervallo A..B.

(NOTAZIONE: "i numeri compresi nell'intervallo A..B" sono gli elementi dell'insieme { i | A <= i AND i<=B }. Inoltre, la somma di tutti i numeri contenuti nell'insieme vuoto e' 0.)

Soluzione:

Gli interi menzionati nel testo del problema saranno memorizzati in variabili di tipo "integer".
Il programma dovra' contenere le dichiarazioni:
```
var
   a,b:integer;   {i numeri letti da terminale}
   somma:integer; {il numero da stampare su terminale}
```
Un possibile strategia per calcolare la quantita' richiesta e' la seguente: inizializzare "somma" a 0, se b < a non fare nulla ("somma" contiene gia' il valore corretto), altrimenti
considerare una variabile:
```
i:integer; {indice sull'intervallo a..b+1}
```
e fare assumere ad "i" tutti i valori compresi tra a e b+1, aggiungendo ciascuno di tali valori (tranne l'ultimo, b+1, che e' il primo valore al di fuori dell'intervallo a..b) al valore contenuto nella variabile somma.

Il codice Pascal che realizza la strategia descritta al punto precedente e' la seguente:

var
   a,b:integer;  {i numeri letti da terminale}
   somma:integer;   {il numero da stampare su terminale}
   i:integer;   {indice sull'intervallo a..b+1}

begin
   writeln('Digita un numero intero:');
   readln(a);
   writeln('Digita un altro numero intero:');
   readln(b);
      
   if (b>=a) then
      begin
         i:=a; 

         {IC: a<=i<=b+1 AND somma="somma dei numeri nell'intervallo a..i-1"}
         while (i<=b)
            begin
               somma:=somma+1i;
               i:=i+1;
            end;
      end;
 
   {somma="somma dei numeri nell'intervallo a..b"}

   writeln('La somma dei numeri nell'intervallo ',a,'..',b,' e` ',somma);
end.

La riga di commento che precede il ciclo "while" e' detta "invariante di ciclo", in quanto l'affermazione in essa contenuta e' vera ogni volta che viene valutata la condizione del ciclo.

Il negato della condizione del ciclo (i>b) e l'invariante di ciclo (a<=i<=b+1 AND somma="somma dei numeri nell'intervallo a..i-1") implicano che la variabile "somma" contiene il valore desiderato (somma="somma dei numeri nell'intervallo a..b"). uni

Una versione migliorata del programma e' la seguente (in cui e' stato eliminato l'"if"). Si noti come e' cambiato l'invariante di ciclo.

var
   a,b:integer;  {i numeri letti da terminale}
   somma:integer;   {il numero da stampare su terminale}
   i:integer;   {indice sull'intervallo a..b+1}

begin
   writeln('Digita un numero intero:');
   readln(a);
   writeln('Digita un altro numero intero:');
   readln(b);

   i:=a;
      
   {IC: a<=i<=max(b+1,a) AND somma="somma dei numeri nell'intervallo a..i-1"}
   while (i<=n)
      begin
         somma:=somma+i;
         i:=i+1;
      end;
 
   {somma="somma dei numeri nell'intervallo a..b"}

   writeln('La somma dei numeri nell'intervallo ',a,'..',b,' e` ',somma);
end.

Una versione ulteriormente migliorata del programma e' la seguente (piu' facile da leggere, in cui il "while" e' stato sostituito con un "for").

var
   a,b:integer;  {i numeri letti da terminale}
   somma:integer;   {il numero da stampare su terminale}
   i:integer;   {indice sull'intervallo a..b+1}

begin
   writeln('Digita un numero intero:');
   readln(a);
   writeln('Digita un altro numero intero:');
   readln(b);

   {IC: a<=i<=max(b+1,a) AND somma="somma dei numeri nell'intervallo a..i-1"}
   for i:=a to b do
      somma:=somma+i;
 
   {somma="somma dei numeri nell'intervallo a..b"}

   writeln('La somma dei numeri nell'intervallo ',a,'..',b,' e` ',somma);
end.

Uno "schema di programma" per risovere un "certo tipo di problemi"

Dal programma sviluppato nella sezione precedente puo' essere facilmente "estratto" uno "schema di programma" che puo' essere, di volta in volta, "specializzato" per risolvere "problemi del tipo": "eseguire un certo compito" per tutti i numeri interi nell'intervallo A..B.

Lo "schema di programma e' il seguente":

var
   a,b:integer;  {i numeri letti da terminale}
   i:integer;   {indice sull'intervallo a..b+1}

   << INSERIRE eventuali altre dichiarazioni di variabili >>

begin

   << INSERIRE eventuale inizializzazione di variabili >>

   {IC: a<=i<=max(b+1,a) AND "compito eseguito per l'intervallo a..i-1"}
   while (i<=b) do
      begin
         << INSERIRE
            azione che fa passare da "compito eseguito per a..i-1"
                                   a "compito eseguito per a..i" >>
         i:=i+1;
      end;
 
   {compito eseguito per a..b}
   
   << INSERIRE eventuale restituzione del risultato >>

Una versione equivalente dello "schema di programma" e' la seguente

var
   a,b:integer;  {i numeri letti da terminale}
   i:integer;   {indice sull'intervallo a..b+1}

   << INSERIRE eventuali altre dichiarazioni di variabili >>

begin

   << INSERIRE eventuale inizializzazione di variabili >>

   {a<=i<=max(b+1,a) AND "compito eseguito per l'intervallo a..i-1"}
   for i:==a to b do
      begin
         << INSERIRE 
            azione che fa passare da "compito eseguito per a..i-1"
                                   a "compito eseguito per a..i" >>
      end;
 
   {compito eseguito per a..b}
   
   << INSERIRE eventuale restituzione del risultato >>
end;

Prima di applicare in modo "meccanico" tecniche note e' bene concedersi una "pausa di riflessione"

Supponiamo di dover risolvere (ad esempio ad un esame, oppure to della soluzione di un prioblema complesso) il seguente:

Problema:Scrivere un programma Java che legga da terminale un numero intero N e scriva su teminale la somma di tutti i numeri compresi nell'intervallo 0..N.

Non e' difficile riconoscere tale problema come un problema di quel "certo tipo" di problemi considerati nel paragrafo precedente. Potremmo quindi procedere in modo "meccanico" e produrre il seguente programma:

var
   n:integer;  {il numero letto da terminale}
   i:integer;   {indice sull'intervallo a..b+1}
   somma:integer; {il numero da stampare su terminale}

begin
   writeln('Digita un numero intero:');
   readln(n);

   {IC: a<=i<=max(n+1,0) AND somma="somma dei numeri nell'intervallo 0..i-1"}
   for i:=0 to n do
      somma:=somma+i;
 
   {somma="somma dei numeri nell'intervallo 0..n"}

   writeln('La somma dei numeri nell'intervallo ',0,'..',n,' e` ',somma);
end.

Tuttavia, se invece di partire subito "a testa bassa" con l'applicazione di una tecnica nota, avessimo riflettuto sul particolare problema che stiamo considerando, avremmo (forse) trovato una soluzione migliore.

Dobbiamo calcolare il valore della somma:

S = 0+1+2+3+ ...+(n-2)+(n-1)+n

Ovvero:

S = 1+2+3+ ...+(n-2)+(n-1)+n

Proviamo a calcolare 2*S = S+S scrivendo gli addendi che compongono ciascun termine S prima come sopra e poi in ordine rovesciato:

(S =)   1     + 2     + 3     + ... + (n-2) + (n-1) + n      +
(S =)   n     + (n-1) + (n-2) + ... + 3     + 2     + 1      =
--------------------------------------------------------------
(2*S =) (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)

Ovvero:

2*S = n*(n+1)

da cui:

S = (n*(n+1))/2

(Quest'ultima formula e' nota come "formula di Gauss", dal nome del matematico che la sopri', all'eta' di 8 anni).

Possiamo quindi scrivere il seguente programma (piu' semplice ed efficiente del precedente):

var
   n:integer;  {il numero letto da terminale}
   i:integer;   {indice sull'intervallo a..b+1}
   somma:integer; {il numero da stampare su terminale}

begin
   writeln('Digita un numero intero:');
   readln(n);
    
   somma:=0;

   if (n>0) then
      somma=(n*(n+1))/2  {formula di Gauss}
      
   {somma="somma dei numeri nell'intervallo 0..n"}

   writeln('La somma dei numeri nell'intervallo ',0,'..',n,' e` ',somma);
end.

ESERCIZI DA SVOLGERE

Per eventuali chiarimenti rivolgersi ai docenti.

Scrivere, compilare, ed eseguire un programma Pascal che legga da terminale due numeri interi A, B e scriva su terminale il prodotto di tutti i numeri compresi nell'intervallo A..B.
Scrivere, compilare, ed eseguire un programma Pascal che legga da terminale due numeri interi A, B e scriva su terminale la somma di tutti i numeri compresi nell'intervallo A..B. (SUGGERIMENTO: generalizzate la "formula di Gauss").