Cicli

Stampa di numeri interi

Si vogliono stampare su schermo i numeri interi da 10 a 50. In Java si potrebbe fare un programma con una linea per ogni valore di da 10 a 50, ossia un programma di questo genere:

class Interi {
  public static void main(String[] args) {

    System.out.println("10");
    System.out.println("11");
    System.out.println("12");

    ...

    System.out.println("50");
  }
}

Come è facile immaginare, il programma completo Interi.java in cui ci sono tutte le istruzioni al posto dei puntini ... è piuttosto lungo. Se si pensa a quando potrebbe essere lungo un programma che stampa i numeri interi da -400 a +23000, risulta evidente che questo tipo di programmi sequenziali non è fattibile.

In Java esistono delle istruzioni composte, dette istruzioni di ciclo, che permettono di ripetere una stessa istruzione per più volte. Questo è utile per esempio nel caso della stampa dei numeri interi, in cui vogliamo ripetere molte volte la istruzione di stampa.

Una tipica istruzione di ciclo è il for. Iniziamo dando una versione semplificata.

for( variabile=valore1; variabile<=valore2; variabile=variabile+1 ) {
  istruzione1
  istruzione2
  ...
}

Questa istruzione composta viene detta ciclo for. Le istruzioni dentro il blocco (istruzione1, istruzione2, ecc.) vengono eseguite una prima volta con variabile=valore1, una seconda volta con variabile=valore1+1, una terza volta con variabile=valore1+2, ecc. fino a che non si arriva alla esecuzione con variabile=valore2, e a questo punto l'esecuzione del ciclo finisce, cioè si passa ad eseguire la prima instruzione che sta fuori dal ciclo.

Riconsideriamo ora il programma di stampa di interi da 10 a 50. Il problema si risolve con una operazione di stampa che viene ripetuta per ogni numero intero da 10 a 50. In altre parole, si può pensare a ripetere la singola istruzione

System.out.println(i);

una volta con i=10, una volta con i=11, una volta con i=12, ecc fino all'ultima volta con i=50. Questo è chiaramente equivalente al problema di partenza. Inoltre, è esattamente il tipo di problema che si risolve con un ciclo for: la ripetizione di una stessa istruzione con valori crescenti di una variabile. Dal momento che la variabile che deve cambiare valore è i, e deve andare da 10 a 50, un programma complessivo che usa il ciclo for è il seguente InteriFor.java.

/*
  Stampa i numeri interi da 10 a 50.
*/

class InteriFor {
  public static void main(String[] args) {
    int i;

    for(i=10; i<=50; i=i+1) {
      System.out.println(i);
    }
  }
}

Nel caso ci fossero dubbi sulla interpretazione dei cicli for, un meccanismo che permette di chiarire in che modo vengono eseguite le istruzioni è quello di scrivere esplicitamente il ciclo per esteso. Si parte da un generico ciclo for:

for( variabile=valore1; variabile<=valore2; variabile=variabile+1 ) {
  istruzione1;
  istruzione2;
  istruzione3;
}

Per semplicità si considerano solo tre istruzioni. Per definizione, le istruzioni interne al ciclo vengono eseguite una volta con variabile=valore1, una volta con variabile=valore1+1, ecc. Quindi, per definizione, si può pensare al ciclo di sopra come al programma senza cicli di sotto:

variabile=valore1;
istruzione1;
istruzione2;
istruzione3;
variabile=valore1+1;
istruzione1;
istruzione2;
istruzione3;
variabile=valore1+2;
istruzione1;
istruzione2;
istruzione3;

...

variabile=valore2;
istruzione1;
istruzione2;
istruzione3;

Il programma di sotto, per poter essere effettivamente scritto ed eseguito, richiede tutte le istruzioni scritte per esteso: non si possono lasciare i puntini ... per indicare le istruzioni in mezzo. Questo procedimento di scrivere per esteso il ciclo conviene solo per capire cosa viene effettivamente fatto da un ciclo, mentre non è conveniente programmare scrivendo i cicli per esteso.

Per esercizio, provare a seguire questo procedimento di scrittura esplicita del ciclo for sul programma InteriFor.java che stampa i numeri interi da 10 a 50 con un ciclo for.

Stampa dei valori di una funzione

Si vogliono stampare su schermo i valori di una funzione a numeri interi. Sia x2+10x-2 questa funzione: vogliamo stampare i valori che assume per tutti i valori interi da -50 a +100. Un programma Java per fare questo potrebbe essere fatto in questo modo: si definiscono due variabili x e f, poi si assegna x=-50, si calcola f e si stampa. Poi si ripete per x=-49, ecc:

class Valori {
  public static void main(String[] args) {
    int x,f;

    x=-50;
    f=x*x+10*x-2;
    System.out.println("f vale "+f);

    x=-49;
    f=x*x+10*x-2;
    System.out.println("f vale "+f);

    ...

    x=100;
    f=x*x+10*x-2;
    System.out.println("f vale "+f);
  }
}

Come è facile immaginare, il programma completo (senza i puntini ...) è piuttosto lungo: Valori.java è composto di 458 linee di testo. È chiaramente impensabile usare programmi di questo genere per risolvere il problema. Se si pensa che potrebbero verificarsi casi in cui si vuole la stampa di valori da -1000 a +2000, risulta evidente che occorre qualche meccanismo che permetta di dire all'interprete che certe istruzioni vanno ripetute più volte.

Il programma si semplifica notevolmente grazie ai cicli for. Quello che si richiede è il calcolo della funzione, e la sua stampa, per valori di x crescenti, in cui si parte dal valore -50 e si arriva al valore 100. Le due istruzioni che vanno ripetute sono in questo caso:

   f=x*x+10*x-2;
   System.out.println("f vale "+f);

Queste due istruzioni vanno ripetute una prima volta con x=-50, poi x=-49, poi x=-48, eccetera, fino a x=100. Il programma ValoriFor.java contiene un ciclo for al cui interno ci sono queste due istruzioni.

/*
  Stampa i valori di una funzione in un intervallo
*/

class ValoriFor {
  public static void main(String[] args) {
    int x,f;

    for(x=-50; x<=100; x=x+1) {
      f=x*x+10*x-2;
      System.out.println("f vale "+f);
    }
  }
}

Per esercizio, si può verificare che scrivendo le istruzioni del ciclo in modo esplicito si ottiene esattamente il programma di prima.

Somma dei primi elementi di una serie

Consideriamo questo problema: abbiamo una serie definitita come la somma dei valori di una funzione f(x). Vogliamo calcolare la somma di questi valori per x che va da 0 a un certo valore prefissato, per esempio 5 oppure 29. In altre parole, si vuole sapere il valore di:

Per fare questo, si può procedere nel modo seguente: si dichiara una variabile somma che contiene la somma parziale calcolata fino a questo punto. Si comincia con somma=0;. Poi si aggiunge a questa variabile il valore della funzione valutata con argomento 0, poi con argomento 1, poi 2, ecc. fino al limite considerato. Questo procedimento è stato seguito nel programma Serie.java per la funzione f(x)=x*x.

/* 
  Calcola la somma dei primi valori di una serie.
*/

class Serie {
  public static void main(String[] args) {
    int x;
    int somma;

    somma=0;

    x=0;
    somma=somma+x*x;

    x=1;
    somma=somma+x*x;

    x=2;
    somma=somma+x*x;

    x=3;
    somma=somma+x*x;

    x=4;
    somma=somma+x*x;

    x=5;
    somma=somma+x*x;
  
    System.out.println("La somma vale "+somma);
  }
}
    

Tutto questo funziona perfettamente, ma è possibile solo se i valori da calcolare sono pochi. Se si volesse per esempio la somma dei valori della funzione da 0 a 100, sarebbero necessarie più di 200 linee di codice. Questo meccanismo risolutivo ha un altro problema: ogni volta che si vuole effettuare un calcolo su un intervallo diverso (per esempio di vuole passare da 200 a 90) occorre modificare radicalmente il codice del programma, eliminando o aggiungendo istruzioni.

Il programma di somma dei valori di una funzione si può facilmente realizzare usando un ciclo. Vogliamo infatti eseguire la istruzione somma=somma+x*x per i che vale prima 0, poi 1, poi 2, ecc, fino a un valore da noi scelto. Il programma SerieFor.java calcola il valore della somma usando un ciclo.

/*
  Somma dei primi valori di una serie
*/

class SerieFor {
  public static void main(String[] args) {
    int x;
    int somma;

    somma=0;
    for(x=0; x<=5; x=x+1) {
      somma=somma+x*x;
    }

    System.out.println("La somma vale "+somma);
  }
}


A parte la brevità del programma, si fa notare come sia facimente modificabile: per esempio, se si vuole calcolare la somma da 0 a 100 (invece che da 0 a 5), basta modificare la istruzione for, facendola diventare for(x=0; x<=100; x=x+1) {.

Stampa dei valori positivi di una funzione

Sia data una funzione da interi a interi, per esempio x*x-10*x+2. Si scriva un programma Java che stampi i soli valori positivi che la funzione assume in un certo intervallo, per esempio da -100 a +100.

Il problema si può riformulare cosí: per ogni valore di x da -100 a +100, se la funzione assume valore positivo, si stampi il valore. In termini di programmazione, è quindi necessario un ciclo in cui x va da -100 a +100; in ogni passo, si controlla se il valore della funzione è positivo oppure no, stampando eventualmente il valore. Il programma SoloPositivi.java risolve il problema in questo modo.

/*
  Stampa i valori positivi che una funzione assume
  in un certo intervallo.
*/

class SoloPositivi {
  public static void main(String[] args) {
    int x,f;

    for(x=-100; x<=100; x=x+1) {
      f=x*x-10*x+2;
      if( f>=0 ) {
        System.out.println("Per x="+x+" la funzione vale "+f);
      }
    }
  }
}

L'unica cosa nuova di questo programma rispetto a quelli precedenti è che all'interno del ciclo, oltre a istruzioni semplici, compare anche una istruzione condizionale. In effetti, all'interno di un ciclo possono apparire istruzioni qualsiasi, incluse istruzioni condizionali, e anche altri cicli (questo risulta utile sulle matrici, che si vedranno più avanti). Lo stesso vale anche per le istruzioni condizionali: all'interno si possono mettere altre istruzioni condizionali, e anche dei cicli.

Presenza di valori negativi

Questo esercizio riguarda ancora l'uso dei cicli. Sia data una funzione f(x) a valori interi; si vuole sapere se esiste un valore intero x compreso in un certo intervallo dato in cui f(x) è negativa. Per esempio, dato f(x)=-x*x+90*i, ci si chiede se esiste un valore di x compreso fra 0 e 100 tale che f(x) sia negativa per quel valore.

Questo è un tipico esempio di utilizzo dei cicli. Infatti, il problema si può risolvere con un ciclo in cui una variabile assume tutti i valori interi compresi nell'intervallo. Per ogni valore, si valuta la funzione e si verifica se è positiva o negativa. Il programma SottoZero.java risolve il problema in questo modo.

/* 
  Verifica se esistono valori negativi per una funzione.
  Si valutano solo valori interi dell'argomento, e solo
  per un intervallo fissato.
*/

class SottoZero {
  public static void main(String[] args) {
    int x;
    int f;
    int positivo;

    positivo=1;

    for(x=0; x<=100; x=x+1) {
      f=-x*x+90*x;
      if( f<0 ) {
        positivo=0;
      }
    }

    if( positivo==1 ) {
      System.out.println("La funzione e' positiva nell'intervallo");
    }
    else {
      System.out.println("La funzione ha valori negativi");
    }
  }
}

Naturalmente, esistono altri programmi che fanno la stessa cosa. D'altra parte, molti programmi che sembrano risolvere questo problema sono in effetti errati. Per esempio, è facile pensare che la variabile positivo non sia necessaria, e procedere quindi secondo il programma seguente:

    for(i=0; i<=100; i=i+1) {		/* ERRATO */
      f=-i*i+90*i;
      if( f<0 ) {
        System.out.println("La funzione e' positiva nell'intervallo");
      }
      else {
        System.out.println("La funzione ha valori negativi");
      }
    }

In questo caso, per ogni valore di x viene stampato il messaggio che dice se la funzione è positiva oppure negativa. Si voleva invece una stampa sola, che riassumesse la presenza o meno di valori negativi nell'intervallo. Questo indica chiaramente che la stampa non si può fare all'interno del ciclo, perchè altrimenti si avrebbe un messaggio per ogni valore, e non uno solo alla fine. Per questa ragione è necessaria la variabile positivo, il cui valore alla fine indica la presenza di valori negativi, e permette quindi di decidere cosa stampare.

    for(i=0; i<=100; i=i+1) {		/* ERRATO */
      f=-i*i+90*i;
      if( f<0 ) {
        positivo=0;
      }
      else {
        positivo=1;
      }
    }

Questo è un altro errore tipico. A prima vista, il programma può sembrare corretto, dal momento che, per ogni valore di x si verifica se la funzione è positiva o negativa. Si supponga però che la funzione sia negativa in tutto l'intervallo tranne che per l'estremo superiore, ossia che f(x) sia negativa per x che va da 0 a 99, e sia positiva solo per x=100. Questo programma effettua la valutazione delle istruzioni interne al ciclo per ogni valore di x; l'ultima esecuzione avviene assegnando 100 ad x. A questo punto, si valuta f, che risulta positiva, per cui la condizione f<0 risulta falsa, e si assegna positivo=1;. La istruzione che segue il ciclo è la istruzione condizionale in cui la condizione è sul valore di positivo. A questo punto, viene stampato il messaggio che dice che la funzione è sempre positiva nell'intervallo. Questo comportamento è chiaramente errato, dal momento che, al contrario, la funzione è quasi sempre negativa nell'intervallo.

L'errore è che la variabile positivo cambia valore ad ogni esecuzione del ciclo. Questo è un errore, perchè in questo modo assume un valore che dipende solo dall'ultimo valore di x. Quello che invece si vuole fare è: si comincia assumendo che la funzione sia sempre positiva; se si trova un valore per cui è negativa si cambia il valore della variabile.

Uscita forzata da un ciclo

Nel programma di verifica di esistenza di valori negativi, si può fare una osservazione riguardo al numero di istruzioni che vengono effettivamente eseguite. Supponiamo che la funzione sia positiva per x che va da 0 a 34, sia negativa per x=35. Simulando l'esecuzione del programma, si esegue il contenuto del ciclo una prima volta per x che vale 0, e qui la f risulta positiva, e quindi la condizione f<0 è falsa, e la variabile positivo non cambia valore. Lo stesso avviene per x=1, x=2, .... , x=34. Quando si arriva al valore 35, la funzione diventa negativa, per cui la condizione f<0 è verificata, per cui la variabile positivo diventa 0.

Cosa succede sulle successive esecuzioni con x=36,...,100? Se ci sono altri valori di x per i quali la f assume valori negativi, si esegue ancora la istruzione positivo=0, ma la variabile aveva già valore 0. Per i valori positivi, non succede niente. In altre parole, i valori successivi di x non possono cambiare più niente.

In questo caso, una volta raggiunto il primo valore in cui la funzione è negativa, non è necessario controllare i valori successivi. In effetti, il problema di verifica dei valori negativi si può riformulare come: per ogni valore di x, controlla se f(x) è negativa: se lo è, fermati e stampa che la funzione assume valori negativi.

La istruzione break è stata introdotta per permettere di uscire dai cicli senza aspettare che l'ultimo valore sia stato raggiunto. L'uso della istruzione è molto semplice: ogni volta che ci si trova all'interno di un ciclo, se si raggiunge una istruzione break si interrompe il ciclo e si passa direttamente alla prima istruzione che segue il ciclo. Nel caso della verifica di valori negativi, il break si può usare come nel programma SottoZeroBreak.java.

/*
  Dice se una funzione assume valori negativi in un
  certo intervallo
*/

class SottoZeroBreak {
  public static void main(String[] args) {
    int x;
    int f;
    int positivo;

    positivo=1;

    for(x=0; x<=100; x=x+1) {
      f=-x*x+90*x;
      if( f<0 ) {
        positivo=0;
        break;
      }
    }

    if( positivo==1 ) {
      System.out.println("La funzione e' positiva nell'intervallo");
    }
    else {
      System.out.println("La funzione ha valori negativi");
    }
  }
}

L'unica cosa che cambia rispetto al programma precedente SottoZero.java è l'istruzione break all'interno della istruzione condizionale dentro il ciclo. L'effetto di questa istruzione è che si esce dal ciclo se la istruzione viene eseguita, ossia il ciclo si interrompe se la condizione f<0 è verificata.

Possiamo considerare due casi:

  1. la funzione è sempre positiva;
  2. la funzione ha valori negativi.

Nel primo caso, si procede alla valutazione per x che assume valori crescenti da 0 a 100, nei quali la condizione f<0 è sempre falsa, per cui la variabile positivo non cambia mai valore, e la istruzione break non viene mai eseguita (questo fa sí che il ciclo proceda come al solito).

Nel secondo caso, si parte sempre con x=0 e, finchè la funzione è positiva, si procede come al solito. Non appena la x assume un valore per cui f<0, si esegue positivo=0;, e si arriva alla istruzione break; Questa istruzione fa sí che il ciclo venga interrotto sul momento, ossia non si incrementa nuovamente la variabile x, ma si passa direttamente ad eseguire la prima istruzione dopo il ciclo, ossia if( positivo==1 ) ... . Questo è esattamente il comportamento voluto: quando si trova un valore negativo, si esce dal ciclo senza terminare il controllo sui rimanenti valori di x.

Esempio

Stampare il più piccolo valore intero di x nell'intervallo [-100,250] in cui la funzione f(x)=x2-20x assume un valore nullo.

Questo problema si può riformulare come segue: per ogni valore di x che va da -100 a +250, se la funzione vale 0, si stampi il valore di x e si esca dal ciclo. Se la funzione non vale 0, si continua la esecuzione del ciclo. Il programma Zero.java usa un ciclo in cui a seconda del valore di f si decide se uscire dal ciclo oppure no.

/*
  Trova il primo valore di x nell'intervallo [-100,250]
  in cui f(x)=xx-20x+2 vale 0.
*/

class Zero {
  public static void main(String[] args) {
    int x,f;

    for(x=-100; x<=250; x=x+1) {
      f=x*x+20*x;
      if( f==0 ) {
        System.out.println("La funzione vale 0 quando x vale "+x);
        break;
      }
    }
  }
}

In altre parole, si esegue un ciclo con x che va da -100 a +250. Se per un qualche valore si trova che la funzione vale 0, si stampa il valore di x che ha reso nulla la funzione e si esce dal ciclo. Si noti che il break in questo caso è necessario: si veda per esempio il programma ZeroNoBrk.java che è uguale al precedente tranne che per la assenza del break. Compilando ed eseguendo questo secondo programma, si vede che il messaggio viene stampato per tutti i valori di x per i quali la funzione vale zero, e non solo per il primo, come era specificato.

Cicli con decremento

Tutti i cicli visti fino ad ora consistevano nella ripetizione di istruzioni, con una variabile che assumeva valori crescenti. In particolare, ad ogni esecuzione delle istruzioni, questa variabile viene aumentata di 1. In alcuni casi, è invece necessario ripetere delle istruzioni decrementando una variabile ad ogni passo, per esempio se si vuole eseguire delle istruzioni mettendo prima x=100 poi x=99, ecc. Un altro caso che non si può fare con i cicli visti fino ad ora è quello in cui la variabile deve aumentare o diminuire di 10 ad ogni passo. Per questo genere di casi, occorre introdurre la struttura generica del ciclo for. Il generico ciclo for contiene come argomenti una istruzione, una condizione e un'altra istruzione:

for(istruzione1, condizione, istruzione2) {
  A
}

In questo schema, A è un blocco di istruzioni. La esecuzione di questo ciclo equivale alla seguente sequenza di istruzioni:

instruzione1;
if( condizione ) {
  A;
  istruzione2;
  if( condizione ) {
    A;
    istruzione2;
    ....

In altre parole, si esegue istruzione1 e si controlla la condizione. Se la condizione è verificata, si eseguono prima A e poi istruzione2, si verifica di nuovo la condizione e si ripete da capo. In altre parole, una volta eseguita istruzione1, si ripete la esecuzione di A e istruzione2, e questo viene ripetuto ancora e ancora se condizione è verificata. In italiano:

esegui instruzione1
se la condizione e' verificata
allora: -esegui A
        -esegui istruzione2
        -se la condizione e' verificata
         allora: .esegui A
                 .esegui istruzione2
                 .se la condizione e' verificata
                  ....

Si noti che non è sempre possibile scrivere esplicitamente il blocco di istruzioni condizionali che corrisponde a un ciclo for. Questa traduzione è utile nel caso in cui si abbia qualche dubbio sul comportamento di un certo ciclo for: in questo caso si può pensare di sviluppare la espansione in istruzioni condizionali (fino a un certo punto) per verificare se il comportamento del ciclo è quello previsto.

Con questa definizione, è facile realizzare dei cicli nei quali una variabile, invece di assumere valori crescenti, prende valori decrescenti. Per esempio, se si vogliono stampare i numeri interi da 100 a 0 in ordine decrescente (si parte da 100 e si arriva a 0), si può usare un ciclo for in cui la istruzione2 decrementa a ogni passo il valore di una variabile, come viene fatto nel programma ContaIndietro.java:

/*
  Stampa gli interi da 100 a 0 in ordine decrescente.
*/

class ContaIndietro {
  public static void main(String[] args) {
    int x;

    for(x=100; x>=0; x=x-1) {
      System.out.println(x);
    }
  }
}

Il ciclo questa volta contiene x=x-1 come seconda istruzione. Questo vuol dire che, ad ogni passo, il valore di i scende di uno. Si noti l'inversione della condizione: dal momento che occorre terminare il ciclo quando x raggiunge il valore 0, e x vale più di zero prima, la condizione che fa continuare ad eseguire il ciclo delve essere x>=0. Nel caso di cicli con incremento la condizione sarebbe stata, sempre nel caso in cui l'ultimo valore con cui eseguire il ciclo è 10, x<=10.

Esempio

Stampare i valori della funzione f(x)=x3-45 per x che vale 100, 90, 80, ..., -100, ossia valori che decrescono di 10 per volta, partendo da 100 e arrivando a -100. Si tratta chiaramente di un problema risolubile con un ciclo for in cui la variabile x parte da 100, viene decrementata di dieci ad ogni passo, e si continua ad eseguire un ciclo se x è maggiore o uguale a -100. Il ciclo for è simile al precedente, in cui la istruzione che viene eseguita per prima assegna 100 alla variabile x, la istruzione che viene eseguita ogni volta è il decremento di x, e la condizione è x>=-100. Il programma ValoriDecrescenti.java risolve questo problema.

/*
  Stampa i valori di una funzione con valori
  decrescenti dall'argomento.
*/

class ValoriDecrescenti {
  public static void main(String[] args) {
    int x,f;

    for(x=100; x>=-100; x=x-10) {
      f=x*x-10*x+50;
      System.out.println("Per x="+x+" la funzione vale "+f);
    }
  }
}

La istruzione che viene eseguita ad ogni passo è la istruzione x=x-10; che decremea il contenuto di x di 10.

Cicli while

I cicli while sono la forma più generica di ciclo. La struttura generale è questa:

while( condizione ) {
  istruzione1;
  istruzione2;
  ...
}

Quando questo blocco viene eseguito, si compiono i seguenti passi:

  1. si verifica se la condizione è vera;
  2. se lo è, si eseguono in sequenza le istruzioni istruzione1, istruzione2, ecc., altrimenti si esce dal ciclo
  3. si verifica di nuovo la condizione,
  4. se è verificata si eseguono di nuovo le istruzioni;
  5. ...

La frase "si esce dal ciclo" indica che si passa ad eseguire la prima istruzione che segue il blocco, ossia la prima istruzione che viene dopo il }. In italiano, il ciclo while si potrebbe tradurre come: "finchè la condizione è verificata, continua ad eseguire le istruzioni".

È facile far vedere che ogni ciclo for si può tradurre in un ciclo while:

for(istruz1; condiz; istruz2) {           istruz1;
  A;                                -->   while(condiz) {
}                                           A;
                                            istruz2;
                                          }

D'altra parte, i cicli in cui una variabile deve venire assegnata a valori crescenti o decrescenti in un intervallo si codificano in maniera più naturale usando cicli for: il codice risulta in questo modo più breve da scrivere e più facile da capire. D'altra parte, i cicli while sono più conveniente negli altri casi di iterazione di istruzioni ma non c'è una variabile che si incrementa o decrementa.

Esempio: serie di Fibonacci

Si vogliono i valori inferiori a 10000 della serie di Fibonacci. La serie di Fibonacci è definita in questo modo: i primi due elementi f0 e f1 valgono 1. Gli elementi successivi sono determinati con la formula:

fi=fi-1+fi-2

Il problema si risolve facimente usando due variabili penultimo e ultimo in cui si memorizzano gli ultimi due valori trovati della serie. All'inizio, queste due variabili hanno valore 1, dato che i primi due elementi della serie valgono 1 per definizione. Per determinare il successivo elemento della serie, è sufficiente sommare queste due variabili. A questo punto, la variabile ultimo deve assumere il valore dell'ultimo elemento della serie, e quindi il valore della somma, mentre penultimo deve diventare il valore del penultimo elemento trovato, per cui deve prendere il valore che aveva ultimo in precedenza. Il programma Fibonacci.java risolve il problema in questo modo.

/*
  La serie di Fibonacci per valori minori di 10000.
*/

class Fibonacci {
  public static void main(String[] args) {
    int penultimo, ultimo, nuovo;
    int limite=10000;

    penultimo=1;
    ultimo=1;

    System.out.println(penultimo);

    while( ultimo < limite ) {
      System.out.println(ultimo);

      nuovo=penultimo+ultimo;
      penultimo=ultimo;
      ultimo=nuovo;
    }
  }
}

Il programma funziona nel modo seguente. Ad ogni passo, penultimo e ultimo sono gli ultimi due valori trovati della serie, e si stampa ultimo. Si calcola il nuovo valore della serie, che è la somma di questi due, e lo si memorizza nella variabile nuovo. A questo punto, penultimo e ultimo sono diventati il terz'ultimo e il penultimo elemento della serie, per cui è necessario cambiarli per far sí ritornino ad essere il penultimo e l'ultimo. Questo significa che penultimo prende il valore di ultimo, mentre ultimo prende il valore di nuovo. Dal momento che questa sequenza di passi si trova all'interno di un ciclo while, viene eseguita fino a che la condizione è verificata. In questo caso, si continua fino a che l'ultimo valore trovato non supera il limite imposto.

Ultima nota: dal momento che a venire stampato è sempre il valore di ultimo dopo questo cambiamento, nelle stampe si perde il primo elemento della serie. Per questa ragione è stata messa l'istruzione System.out.println(penultimo); prima della esecuzione del ciclo.

Esempio: zero di una funzione

È noto che una funzione, se è continua in un intervallo [a,b], ha valore positivo in a e negativo in b, allora è nulla in almeno un punto dell'intervallo. Si vuole un programma che calcola un intervallo sufficientemente piccolo in cui la funzione ha (almeno) uno zero. Siano quindi dati la funzione, i valori (reali) di a e b, e un terzo valore e, e si vuole un intervallo [c,d] che sia contenuto in [a,b], che contenga un punto x tale che f(x)=0, e la dimensione di questo intervallo sia minore di e, ossia d-c <= e.

Un possibile meccanismo risolutivo è il seguente: si parte con c,d pari agli estremi dell'intervallo dato. Poi si assegna x=(c+d)/2, e si valuta f(x). In altre parole, si fissa x al punto esattamente in mezzo all'intervallo, e si valuta f nel punto. Dal momento che f(c) e f(d) hanno segni diversi, almeno uno dei due ha un segno uguale a quello di f(x). Nel caso in cui f(c) e f(x) hanno lo stesso segno, si assegna c=x. Nel caso in cui sono f(d) e f(x) ad avere lo stesso segno, si assegna d=x. Alla fine di questo passo, la proprietà che f(c) e f(d) hanno segni diversi continua a valere. D'altra parte, la differenza fra d e c si è dimezzata.

Il programma Nullo.java contiene il programma Java che ripete questi passi fino a che la ampiezza dell'intervallo non diventa minore o uguale del numero dato e.

/*
  Trova un punto in cui una funzione f(x) ha un
  valore sufficientemente vicino allo zero.
  Siano a e b due valori tali che f(a) ha segno
  opposto a f(b). Si assume che la funzione sia
  continua.
*/

class Nullo {
  public static void main(String[] args) {
    double a=0,b=10;
    double c,d;
    double e=0.01;
    double x,f,f1,f2;

    f1=a*a-5*a-2;
    f2=b*b-5*b-2;

    if( f1*f2 >0 ) {
      System.out.println("La funzione non ha segno diverso negli estremi");
      System.out.println(f1+" "+f2);
    }
    else {
      c=a;
      d=b;
  
      while( d-c>e ) {
        x=(c+d)/2;
        System.out.println("Intervallo: ["+c+","+d+"], Medio: "+x);
  
        f=x*x-5*x-2;
        f1=c*c-5*c-2;
        f2=d*d-5*d-2;
  
        if( f*f2 < 0 ) {
          c=x;
        }
        else if( f*f1 < 0 ) {
          d=x; 
        }
        else {
          c=x;
          d=x;
          break;
        }
      }
  
      System.out.println("Trovato intervallo ["+c+","+d+"]");
    }
  }
}

Usiamo la condizione f*f1>0 per decidere se due numeri hanno lo stesso segno. Una delle prime istruzioni del programma è la verifica se effettivamente la funzione ha segno differente pre a e per b. Se il segno risulta uguale, si stampa un messaggio di errore e basta. In caso contrario, si esegue il resto della procedura.

Correttezza dei cicli

Assunzioni

Quando si usano dei cicli, è facile commettere degli errori legati alle assunzioni che vengono fatte. Molto spesso, ci sono delle assunzioni che sono valide all'inizio della prima esecuzione del ciclo, ma che non sono valide alle successive iterazioni. Prendiamo il seguente programma FibonacciErrato.java, che dovrebbe stampare gli elementi della serie di fibonacci.

/*
  La serie di Fibonacci per valori minori di 10000.
*/

class FibonacciErrato {
  public static void main(String[] args) {
    int penultimo, ultimo, nuovo;
    int limite=10000;

    penultimo=1;
    ultimo=1;

    System.out.println(penultimo);
    System.out.println(ultimo);

    while( penultimo+ultimo < limite ) {
      nuovo=penultimo+ultimo;
      System.out.println(nuovo);
    }
  }
}

Eseguendo questo programma, vengono stampati i primi due valori della sequenza 1 e 1, e poi viene stampato ripetutamente il terzo valore 2. Quindi, i primi tre valori che escono sono giusti, ma dal quarto valore in poi si ottengono risultati errati.

L'errore è che le variabili penultimo e ultimo dovrebbero sempre rappresentare il penultimo e l'ultimo elemento trovato della serie. Questo è vero alla prima iterazione del ciclo, dal momento che i primi due valori trovati sono 1 e 1 (e questi sono i valori delle due variabili). A questo punto viene calcolato il nuovo valore nuovo=1+1, e questo è effettivamente il terzo elemento della serie. A questo punto si parte con una nuova iterazione del ciclo. Questa volta però la assunzione che penultimo e ultimo rappresentano gli ultimo due valori trovati non è più valida, dal momento che l'ultimo valore trovato è quello che sta nella variabile nuovo, mentre il valore che sta in ultimo è il penultimo valore trovato. Questo è il motivo per cui il programma non funziona: la assunzione che è vera alla prima iterazione del ciclo non lo è più alle successive iterazioni. Per rendere il programma corretto occorre fare in modo che la assunzione risulti valida anche alle successive iterazioni. Il programma corretto Fibonacci.java modifica il contenuto delle variabili penultimo e ultimo in modo tale che, alla fine di ogni iterazione del ciclo, contenengano gli ultimi due elementi trovati.

Analogamente, nel programma di ricerca di un intervallo che contiene uno zero di una funzione, Nullo.java, si parte dall'assunzione che c,d siano due valori per i quali la funzione ha segno diverso. È quindi necessario che la stessa condizione sia verificata alla fine di ogni singola iterazione del ciclo. Il concetto si può riassumere come segue:

Se nel corpo un ciclo uso una assunzione A, allora:
  • la assunzione A deve essere vera la prima volta che eseguo il ciclo;
  • devo verificare che, assumendo A vera all'inizio del corpo del ciclo, allora A risulta vera anche alla fine.

In genere nei cicli c'è sempre una proprietà che viene mantenuta in tutte le iterazioni, e che è necessaria perché il tutto funzioni. La prima cosa da controllare è che la assunzione sia vera alla prima iterazione del ciclo. Questo risulta di solito abbastanza naturale, ed è quindi difficile trovare errori legati a questo. La seconda cosa che si deve fare è controllare che, assumendo che la assunzione si vera all'inizio di una generica iterazione del ciclo, ed eseguendo il corpo del ciclo, la assunzione alla fine è ancora verificata.

Naturalmente, non è necessario che la assunzione valga anche in mezzo al corpo del ciclo. Per esempio, il fatto che le due variabili contenessere gli ultimi due valori trovati non vale a metà della iterazione (per esempio non vale subito dopo la istruzione System.out.println(nuovo)).

Terminazione

Non è difficile fare esempi di cicli che non terminano. Per esempio, il ciclo

while( 1==1 ) {
  ...
}

viene eseguito all'infinito, dal momento che la condizione è sempre vera (a meno che non ci sia un break all'interno del ciclo).

In alcuni casi, il ciclo infinito è esattamente quello che si vuole. Di solito però si vuole che un programma faccia delle operazioni le sue escuzioni e poi termini, il che implica che tutti i cicli che contiene devono prima o poi terminare. In particolare, se dopo il ciclo ci sono altre istruzioni da eseguire, allora la mancata terminazione fa sí che le istruzioni seguenti non siano eseguite, il che è chiaramente un errore. In generale, i cicli devono sempre terminare.

Nel caso dei cicli for usati per assegnare ripetutamente a una variabile valori crescenti o decrescenti la terminazione di rado è un problema: i cicli for(var=val1; var<=val2; var=var+1) terminano sempre: l'unico problema che può verificarsi è quello di scrivere una condizione con il <= mentre la istruzione che segue è un decremento x=x-1. In altre parole, questi cicli possono non terminare se si scrive per errore una delle due cose seguenti:

Il problema può essere più grave nel caso dei cicli while e dei cicli for generici (cioè quelli di tipo for(istruzione1; condizione; istruzione2) in cui condizioni e istruzioni sono generiche). In questi casi, la verifica di terminazione può essere più complicata. Per esempio, il programma FibonacciErrato.java non termina, e il motivo è che le variabili che si trovano nella condizione di terminazione non vengono modificate dopo la prima iterazione del ciclo (questo è a sua volta dovuto al fatto che una assunzione che veniva usata non era più vera alla fine della prima iterazione).

In generale, verificare se un ciclo termina è difficile. Ci sono però delle cose che è possibile controllare facilmente. Per esempio, all'interno del ciclo deve esistere sempre la possibilità di cambiare le variabili della condizione, e deve essere sempre possibile che queste variabili assumano valori che fanno uscire dal ciclo. Per esempio, se si ha un ciclo while( a!=0 ), e all'interno del ciclo le uniche operazioni che modificano il valore di a sono le assegnazioni a=1 e a=-1, è chiaro che la variabile non assume mai il valore nullo che fa uscire dal ciclo.

Si tenga altresí presente che la istruzione break fa comunque uscire dai cicli. A volte si usano cicli in cui si sa che la condizione è sempre verificata, come per esempio while( 1!=0 ), semplicemente perchè la uscita dal ciclo è garantita da una istruzione break. In questo caso, occorre verificare se è sempre possibile che la istruzione di break venga effettivamente eseguita.

Note sulla nidificazione e sull'allineamento

In alcuni programmi visti, alcune istruzioni composte come per esempio i cicli contenevano al loro interno altre istruzioni composte come per esempio le istruzioni condizionali. Questo è vero in generale: una istruzione composta può contenere al suo interno altre istruzioni, siano esse semplici o composte a loro volta. Per esempio, all'interno di un ciclo for si può mettere un altro ciclo for che può contenere una istruzione condizionale, ecc. In questi casi, occorre prestare attenzione alla chiusura delle parentesi. Se per esempio abbiamo due istruzioni di ciclo messe l'una dentro l'altra, nel modo seguente:

for(....) {
  ...
  ...
  for(....) {
    ...
    ...
  }
  ...
  ...
}

allora ognuna delle due istruzioni ha la struttura for(....) {istruzioni}. Se una delle istruzioni è ancora un ciclo, questa contiene ancora for(....) {istruzioni}. Per questa ragione, alla fine del blocco occorrono due parentesi graffe chiuse: la prima è l'ultimo carattere del ciclo più interno, mentre la seconda è l'ultimo carattere del ciclo esterno.

In programmi complicati la struttura dei programmi con molte istruzioni composte l'una dentro l'altra può non risultare molto chiara. Questo può portare a degli errori di programmazione.

L'allineamento serve a rendere più chiaro un programma, e permette quindi di individuare errori legati alla struttura del programma. Il metodo generale è molto semplice: ogni volta che si ha una istruzione composta, le sue istruzioni componenti vengono scritte uno o due caratteri più avanti di tutte le altre. Se all'interno di una istruzione composta appare un'altra istruzione composta, le istruzioni che compongono quest'ultima vengono scritte altri due caratteri più avanti, per cui si lasciano quattro spazi prima dell'istruzione.

Dal punto di vista del compilatore, l'allineamento non è necessario, dal momento che tutti gli spazi vengono ignorati. D'altra parte, l'uso di questa tecnica permette di:

  1. capire di quale istruzione composta una istruzione semplice fa parte;
  2. capire se mancano parentesi chiuse, e dove;
  3. capire se le parentesi sono state chiuse nel punto sbagliato.

Nella scrittura di programmi lunghi questi vantaggi risultano immediatamente chiari.