I cicli

Modo facile per eseguire molte istruzioni simili.

Si basano su una costruzione in cui una stessa istruzione (o blocco) vengono eseguite più volte.

Perchè servono i cicli?

Esercizio: scrivere il programma che stampa la seguente stringa 100 volte:

non devo parlare durante la lezione

La soluzione dello scriba

Ripeto cento volte la istruzione.

class Cento {
  public static void main(String args[]) {
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
    System.out.println("non devo parlare durante la lezione");
  }
}

Soluzione con ciclo

Questo programma fa la stessa cosa:

class CentoCiclo {
  public static void main(String args[]) {
    int a;

    for(a=0; a<100; a=a+1) {
      System.out.println("non devo parlare in aula");
    }

  }
}

Forma semplificata di ciclo

Per fare i cicli si usano for e while

Ora vediamo una forma particolare di for

for(variabile=valore1; variabile<valore2;
  variabile=variabile+1) 
  istruzione;

Al posto di una sola istruzione, posso mettere un blocco:
(come sempre!)

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

Cosa succede quando si esegue

for(variabile=valore1; variabile<valore2;
  variabile=variabile+1)
  istruzione;

L'istruzione viene eseguita una volta con valore1, poi con valore1+1, ecc.

Attenzione! il valore2 è il primo valore per il quale NON si esegue l'istruzione.

Unfolding del ciclo

Un ciclo di questo tipo

for(variabile=valore1; variabile<valore2; variabile=variabile+1)
  istruzione;

Equivale a queste istruzioni:

variabile=valore1;
istruzione;
variabile=valore1+1;
istruzione;
variabile=valore1+2;
istruzione;
variabile=valore1+3;
...
variabile=valore2-1;
istruzione;
variabile=valore2;

Quando variabile arriva a valore2, l'istruzione non viene eseguita.

È un modo per capire cosa fa un ciclo, non bisogna scriverlo per esteso nel programma!

Non devo parlare in aula

Il programma stampa cento volte, perchè eseguo l'istruzione per a=0, poi a=1 fino ad a=99.

Sono cento valori diversi

L'istruzione viene eseguita cento volte.

Esercizio

Stampare i primi cento numeri pari positivi, escludendo lo zero.

Se non ci riuscite, stampate i primi cento interi positivi (sia pari che dispari), escludendo lo zero.

Cento interi

Il primo valore da stampare è 1

L'ultimo è 100

Il primo da non stampare è 101

class CentoInt {
  public static void main(String args[]) {
    int a;

    for(a=1; a<101; a=a+1) 
      System.out.println(a);
  }
}

Cento Pari

Due soluzioni possibili:

faccio il ciclo da 1 a 200, stampando solo i pari;
faccio il ciclo da 1 a 100, ma poi stampo a*2

Soluzione con la moltiplicazione

Se moltiplico i primo cento numeri per due,
ottengo i primi cento numeri pari.

101 è il primo numero da non considerare

class CentoPari {
  public static void main(String args[]) {
    int a;

    for(a=1; a<101; a=a+1) 
      System.out.println(a*2);
  }
}

Soluzione con `if`

Il condizionale è una istruzione come le altre.

Dove ci va una istruzione, ci posso mettere un condizionale.

Vado da 1 a 201, ma stampo solo i numeri pari.

Condizione: numero pari = la divisione per 2 dà resto 0

class CentoIf {
  public static void main(String args[]) {
    int a;

    for(a=1; a<201; a=a+1) 
      if(a%2==0)
        System.out.println(a);
  }
}

Cicli dipendenti dai dati

Il numero di esecuzioni di un ciclo può dipendere anche dai dati.

I valori iniziali e finali sono due espressioni intere qualsiasi.

Esercizio: leggere due interi n ed m, e stampare tutti gli interi fra n ed m, inclusi.

Assumere n<m

Soluzione

Il ciclo inizia da n;
il primo valore da non stampare è m+1

import javax.swing.*;

class DaA {
  public static void main(String args[]) {
    String s;
    int n, m;

    s=JOptionPane.showInputDialog("Inizio");
    n=Integer.parseInt(s);

    s=JOptionPane.showInputDialog("Fine");
    m=Integer.parseInt(s);

    int a;

    for(a=n; a<m+1; a=a+1) 
      System.out.println(a);

    System.exit(0);
  }
}

Cicli: se `m<n`?

Se la condizione è falsa subito, l'istruzione non viene eseguita nemmeno una volta.

Forma generale del ciclo `for`

for(istruzione; condizione; istruzione)
  istruzione

Il significato è:

Parti di un ciclo

inizializzazione: istruzione che viene eseguita all'inizio del ciclo
condizione di uscita: quando diventa falsa, si smette di eseguire il ciclo
istruzione di incremento: serve a modificare la variabile di ciclo
corpo del ciclo: l'istruzione che viene eseguita ripetutamente

Unfolding del ciclo: caso generale

for(iniz; cond; incr)
  corpo;

Questa istruzione si può interpretare come:

iniz;
if(cond) {
  corpo;
  incr;
  if(cond) {
    corpo;
    incr;
    ...
  }
}

È un modo per capire cosa succede (non va scritto per esteso)

Unfolding, con salto

for(iniz; cond; incr)
  corpo;

altre istruzioni;

Si può pensare come:

iniz;
if(!cond)
  passa alle istruzioni successive;
corpo;
incr;
if(!cond)
  passa alle istruzioni successive;
corpo;
incr;
...

altre istruzioni

La condizione !cond è vera quando cond è falsa
(operatore booleano "not")

Ciclo: decremento

Stampare i numeri da m ad n

Voglio prima m poi m-1 ecc.

Si assume m>n

Decremento: soluzione

Come si costruisce un ciclo:

se è un ciclo "standard", ossia uno di quelli già visti, uso lo schema solito
se non lo è, devo costruire le quattro parti (iniz, cond, incr, corpo)

Corpo del ciclo

Devo ripetere System.out.println(...)

Fra parentesi ci va la variabile del ciclo, oppure una espressione che dipende da questa.

Intanto, mettiamo a; se serve, si potrà cambiare.

System.out.println(a);

Inizializzazione, e incremento

Parto con a=m.

Ad ogni passo, a deve diminuire di uno!

for(a=m; ...; a=a-1)
  corpo;

Condizione di uscita

È facile sbagliarsi di uno in più o in meno.

Fare una prova con valori precisi (es m=4 ed n=2) spesso risolve il problema.

Considero lo stato attuale del ciclo:

for(a=m; ...; a=a-1)
  System.out.println(a);

Il primo valore di a per il quale il corpo non va eseguito è n-1

for(a=m; a>n-1; a=a-1)
  System.out.println(a);

Perchè `>` invece di `<`?

La condizione dice se devo continuare ad eseguire il ciclo.

condizione vera=continua ad eseguire
condizione falsa=smetti

La condizione deve diventare falsa solo quando voglio smettere di eseguire (e non prima)

Se metto la condizione a<n-1 questa è subito falsa, per cui non si esegue il corpo nemmeno una volta.

Confondere < e > in un ciclo con decremento è un errore comune.

Uso di `<=` invece di `<`

Nel ciclo "standard":

for(a=0; a<N; a=a+1)
  istruzione;

Conviene usare a<N come condizione, perchè cosí è più evidente che il corpo viene eseguito N volte.

In generale, si può anche usare una condizione con <= o con >=

Basta ricordarsi che:

la condizione viene verificata subito dopo l'incremento
se è falsa, il corpo non viene eseguito

for(a=m; a>=n; a=a-1)
  System.out.println(a);

Esercizio sui cicli

Estendere la classe Rectangle con un metodo che stampa tutti i punti sulla base.

  void printBase()

Soluzione

Il primo punto da stampare sta in posizione this.x, this.y

L'ultimo sta in posizione this.x+this.width, this.y

import java.awt.*;

class RectBase extends Rectangle {
  void printBase() {
    int a;
    Point p;
    p=new Point();

    p.y=this.y;

    for(a=this.x; a<this.x+this.width+1; a=a+1) {
      p.x=a;
      System.out.println(p);
    }
  }
}

Soluzione alternativa, con `<=`

Per la condizione di terminazione ci sono due possibilità:

uso a < N, e poi N è il primo valore per il quale il corpo non va eseguito
uso a <= N, ma questa volta N è l'ultimo valore con cui eseguire il corpo.

import java.awt.*;

class RectBase extends Rectangle {
  void printBase() {
    int a;
    Point p;
    p=new Point();

    p.y=this.y;

    for(a=this.x; a<=this.x+this.width; a=a+1) {
      p.x=a;
      System.out.println(p);
    }
  }
}

Esercizio sui cicli

Stampare i soli valori positivi della funzione f(x) per x intero nell'intervallo [5,20]

f(x)=x²-10x+2

Stampa della funzione: soluzione

Iniziamo con la stampa di tutti i valori.

Serve una stampa di f(x) per ogni x da 5 a 20.

Il corpo del ciclo sarà una cosa del genere:

  System.out.println(x*x-10*x+2);

Non siamo ancora sicuri che il corpo sia questo: prima va scritto il resto.

Inizializzazione ed incremento

for(...; ...; ...)
  System.out.println(x*x-10*x+2);

Le parti del for sono:

iniz.: il primo valore di x per il quale il ciclo va eseguito è 5;
quindi, scrivo x=5
incr.: ad ogni passo x deve aumentare di uno, quindi ho x=x+1
cond. uscita: l'ultimo valore da considerare è 20; oppure, il primo da non contare è 21

for(x=5; x<=20; x=x+1)
  System.out.println(x*x-10*x+2);

Oppure:

for(x=5; x<21; x=x+1)
  System.out.println(x*x-10*x+2);

Stampa dei valori positivi

Stesso ciclo. Però la stampa non va fatta se la funzione ha valore negativo.

Si tratta di fare o non fare una cosa a seconda dei valori delle variabili

Serve un condizionale.

for(x=5; x<=20; x=x+1)
  se f(x) e' positiva, stampala

Valori positivi: codice

La condizione è x*x-10*x+2<=0

for(x=5; x<=20; x=x+1)
  if(x*x-10*x+2>=0)
    System.out.println(x*x-10*x+2);

Soluzione che usa una variabile per evitare di fare due volte il calcolo:

for(x=5; x<=20; x=x+1) {
  f=x*x-10*x+2;

  if(f >= 0)
    System.out.println(f);
}

Parentesi graffe

Cosa stampa questo programma?
(stesso di prima, ma senza parentesi)

for(x=5; x<=20; x=x+1) 
  f=x*x-10*x+2;

  if(f >= 0)
    System.out.println(f);

Risposta: si segue la sintassi dei cicli

La forma sintattica è:

for(....)
  istruzione;

Dove l'istruzione può essere una istruzione composta
(sequenza fra graffe, condizionale, ecc.)

for(x=5; x<=20; x=x+1)      for(...)
  f=x*x-10*x+2;               istruzione;

  if(f >= 0)                istr successive;
    System.out.println(f);

Quindi, il corpo del ciclo è dato solo da f=x*x-10*x+2;

L'istruzione if... viene eseguita solo dopo che il ciclo è terminato.

Costruzione dei cicli

In generale, occorre stabilire cosa deve essere eseguito, anche se in modo approssimativo.

In base a questo, si costruisce l'istruzione for

Il corpo potrebbe poi richiedere modifiche

Sintassi del ciclo `for`

for(istruzione; condizione; istruzione)
  istruzione;

Il corpo del ciclo può essere:

una istruzione
una sequenza di istruzioni racchiuse fra graffe
un condizionale
un altro ciclo

Nel caso 2, la sequenza può a sua volta contenere un ciclo o una istruzione condizionale.

Le istruzioni possono essere assenti.

Ciclo `while`

A volte, l'istruzione di inizializzazione e di incremento non servono.

In questo caso, so può usare il ciclo while

while(condizione)
  istruzione;

Esegue l'istruzione finchè la condizione è vera.

Unfolding del ciclo `while`

while(condizione)
  istruzione;

Equivale a fare:

if(condizione) {
  istruzione;
  if(condizione) {
    istruzione;
    ...
  }
}

Unfolding, con uscita

while(condizione)
  istruzione;

Quando la condizione è falsa, si smette di eseguire il ciclo

if(!condizione)
  passa all'istruzione che segue
istruzione;
if(!condizione)
  passa all'istruzione che segue
istruzione;
if(!condizione)
  passa all'istruzione che segue
istruzione;
...

Si controlla la condizione: se è vera, si esegue l'istruzione e si controlla la condizione, ecc.

Equivalenza `for`-`while`

Ogni ciclo for si può trasformare in while, e viceversa.

while(cond) istruzione;	=	for( ; cond; ) istruzione;
for(istr1;cond;istr2) istruzione;	=	istr1; while(cond) { istruzione; istr2; }

Perchè allora usare `for`?

Dà una struttura chiara al programma

Si sa in che punto guardare per cercare la inizializzazione e l'incremento del ciclo

Quando è meglio il `while`?

Due tipi di cicli.

cicli definiti:: si sa in partenza quante iterazioni vanno eseguite;
questo numero può non essere una costante: basta che sia noto quando si inizia ad eseguire il ciclo
cicli indefiniti:: il numero di iterazioni non si può sapere in partenza

Si consiglia di usare for per i cicli definiti e while per quelli indefiniti.

Un esempio di ciclo indefinito

Stampare i valori di f(x)=-x²+3x+4 per valori interi di x da 0 al primo valore per il quale la funzione diventa negativa.

Non sappiamo quando fermarci se non calcoliamo prima i valori della funzione.

Soluzione

Sappiamo da che valore di x partire, ma non quando fermarci.

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

    x=0;

    while(-x*x+3*x+4 >= 0 ) {
      System.out.println(-x*x+3*x+4);

      x=x+1;
    }
  }
}

Soluzione con il `for`

È quasi la stessa cosa.

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

    for(x=0; -x*x+3*x+4 >= 0; x=x+1)
      System.out.println(-x*x+3*x+4);
  }
}

Di solito si preferisce il while quando i cicli sono indefiniti, ma non è obbligatorio.

Metodo del risultato parziale

Si usa quando serve calcolare il risultato di un operatore associativo su un insieme di valori.

Caso particolare: il metodo dell'accumulatore serve per sommare i valori di una funzione per x che va da 10 a 20

Metodo del risultato parziale

Si considera un elemento per volta (si fa un ciclo).

Si usa una variabile per memorizzare il risultato parziale.

Inizialmente, ci si mette l'elemento identità dell'operatore.

Ad ogni passo, si modifica la variabile con un nuovo elemento.

Paragone: algoritmo per riempire di biglie un secchiello

Inizia con il secchiello vuoto

Per ogni biglia, prendila e mettila nel secchiello

Il secchiello contiene il risultato parziale corretto, ossia tutte le biglie considerate fino a questo momento.

Esempio: somma dei valori

Per sommare i valori della funzione, posso procedere in questo modo.

inizialmente, la somma parziale è zero
prendo il primo valore, e lo aggiungo alla somma parziale
prendo il secondo valore, e lo aggiungo alla somma parziale
...

Alla fine, la somma parziale sarà diventata la somma di tutti gli elementi

Nel caso della somma, si chiama anche metodo dell'accumulatore: la variabile accumula tutti gli interi considerati finora.

Somma di elementi: codice

Uso una variabile per memorizzare i valori della somma parziale.

Per ogni valore da considerare, lo prendo e lo sommo al contenuto della variabile.

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

    somma=0;

    for(x=10; x<=20; x=x+1) {
      f=-x*x+3*x+4;

      somma=somma+f;
    }

    System.out.println(somma);
  }
}

Accumulatore: funzionamento

Voglio sommare n valori interi a₁, ..., a_n

Uso la proprietà associativa:

∑_x=1,...,i a_x = ( ∑_x=1,...,i-1 a_x ) + a_i

Ossia:

a₁ + ... + a_i = (a₁ + ... + a_i-i ) + a_i

Il metodo è basato sul principio di induzione:

se funziona per sommare zero elementi,
se, assumendo che funzioni su i-1 elementi, allora funziona anche per i

... allora funziona per qualsiasi n.

La somma e il principio di induzione

Per sommare zero elementi, ho che la somma parziale mantiene il valore iniziale (zero) (quindi, funziona per zero elementi)

Se ho già sommato i-1 elementi, allora incrementando la somma parziale del valore i-esimo, ottengo la somma di i elementi (se vale per i-1 allora vale per i)

In base al principio di induzione, funziona

Induzione-Accumulatore

Confronto:

	Induzione	Accumulatore
Cosa fa	Dimostra che che un teorema è valido per ogni n	Calcola il risultato esatto per insiemi di n interi
Caso base	Dimostra che il teorema è vero per n=0	Calcola il risultato esatto per insiemi di zero elementi
Caso induttivo	Dimostra che il teorema, se è valido per n=i-1, allora è valido per n=i	A partire dal risultato parziale, che si assume corretto, della somma dei primi n=i-1 interi, calcola la somma dei primo n=i interi.
Conclusione	Il teorema è vero per ogni n	Il risultato è corretto per ogni insieme di n interi

Si può dire che il principio di induzione dimostra che il metodo dell'accumulatore è corretto.

Oppure: con il metodo dell'accumulatore, stiamo costruendo la dimostrazione che il risultato finale è effettivamente la somma.

Principio di induzione e accumulatore

Si tratta semplicemente di questo:

Ho un contenitore vuoto (una variabile con zero dentro)

Alla fine voglio che contenga tutti gli elementi sommati

Li sommo uno per volta

Anche se non avete capito...

Potete sempre pensare all'algoritmo per riempire di biglie un secchiello

Inizia con il secchiello vuoto
Per ogni biglia, prendila e mettila nel secchiello

Una persona prenderebbe le biglie a manciate.

Il calcolatore può soltanto sommare un numero costante di interi per volta
(prendere una singola biglia)

Per sommare più elementi, devo usare un algoritmo in cui ne sommo due per volta (o comunque un numero costante).

Sull'induzione ci torneremo quando faremo la ricorsione.

Variante: moltiplicazione

Stesso esercizio di prima, però questa volta con la moltiplicazione

∏_x=10...20 f(x)

Produttoria: soluzione

Variabile parz per memorizzare il prodotto parziale.

Se contiene il prodotto di n-1 elementi, allora per ottenere il prodotto di n basta moltiplicare l'ultimo.

Quindi, devo fare parz=parz*valore

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

    ...

    for(x=10; x<=20; x=x+1) {
      f=-x*x+3*x+4;

      parz=parz*f;
    }

    System.out.println(parz);
  }
}

Valore iniziale?

Il valore iniziale

È l'elemento neutro.

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

    parz=1;

    for(x=10; x<=20; x=x+1) {
      f=-x*x+3*x+4;

      parz=parz*f;
    }

    System.out.println(parz);
  }
}

Se mettevo parz=0 all'inizio?
(risposta ovvia)

Fattoriale

Calcolare il fattoriale di un numero letto da input

Calcolo del fattoriale

La lettura da input si fa come al solito

import javax.swing.*;

class Fatt {
  public static void main(String args[]) {
    String s;
    int n;

    s=JOptionPane.showInputDialog("Dammi un numero");
    n=Integer.parseInt(s);

    ...
  }
}

Ora, fare il calcolo del fattoriale.

Calcolo del fattoriale

Si tratta di moltiplicare i numeri interi da 1 ad n

Faccio il solito ciclo con accumulatore

import javax.swing.*;

class Fatt {
  public static void main(String args[]) {
    String s;
    int n;
    int f, i;


    s=JOptionPane.showInputDialog("Dammi un numero");
    n=Integer.parseInt(s);

    f=1;

    for(i=1; i<=n; i++)
      f=f*i;
      
    System.out.println(f);

    System.exit(0);
  }
}

Esercizio

Calcolare l'n-esimo elemento della serie di Fibonacci

f₁ = 1
f₂ = 1
f_i = f_i-2 + f_i-1

Assumere che n>2

Soluzione

Serve un ciclo definito

Devo memorizzare i due ultimi valori

primo valore =1
secondo valore =1
for ogni intero da 3 ad n
  fi=somma dei due precedenti

Unico problema: dove stanno i due ultimi valori?

Non sempre i cicli sono facili da scrivere.

In questo caso, il problema non è il for(...), ma capire come deve essere fatto il corpo del ciclo.

Correttezza dei cicli

Perchè questo programma non funziona?

class Fibo {
  public static void main(String args[]) {
    int f1, f2;
    int f, i, n=6;

    f1=1;
    f2=1;

    for(i=3; i<=n; i++)
      f=f1+f2;

    System.out.println(f);
  }
}

Correttezza: assunzioni

Se n vale 3, il risultato è corretto (viene eseguita una sola volta l'istruzione f=f1+f2;)

In tutti gli altri casi, viene eseguita più volte la stessa istruzione, ma il valore non cambia.

Nel primo caso, funziona perchè f1 ed f2 sono i valori di f_i-2 ed f_i-1 quando n vale 3.

Se n=6, devo sommare il quarto e il quinto valore della serie, non il primo o il secondo.

Correttezza: mantenere le assunzioni

Quando eseguo per la prima volta il corpo del ciclo, f1 ed f2 contengono gli ultimi due valori calcolati per la serie (il primo e il secondo).

Quando eseguo di nuovo il ciclo, gli ultimi due valori calcolati sono il secondo e il terzo.

Invece, in f1 ed f2 ci sono ancora il primo e il secondo.

Devo fare in modo che l'assunzione "in f1 ed f2 ci sono gli ultimi due valori calcolati della serie" sia valida in qualsiasi esecuzione del corpo del ciclo.

Programma corretto

Quando calcolo un valore, gli ultimi due valori calcolati sono f2 ed f, non f1 ed f2.

Devo modificare le variabili in modo che l'assunzione torni ad essere vera.

In f1 metto il valore di f2, e in f2 il valore di f

class Fibo {
  public static void main(String args[]) {
    int f1, f2;
    int f=0, i, n=6;

    f1=1;
    f2=1;

    for(i=3; i<=n; i++) {
      f=f1+f2;

      f1=f2;
      f2=f;
    }

    System.out.println(f);
  }
}

Verifica di correttezza dei cicli

La maggior parte dei cicli sono facili da scrivere.

A volte invece occorre verificare che le assunzioni che servono restino valide.

Notare che l'assunzione non è "f1 contiene il primo elemento" ma "f1 contiene il penultimo elemento calcolato".

L'assunzione dipende da cosa voglio calcolare.

Operazioni logiche su insiemi

Scrivere un programma che stampa "si" oppure "no" a seconda se la funzione f(x)=x²-10x+2 assume valori negativi per x intero da 0 a 10.

Soluzione

Devo fare un ciclo.

A ogni passo, verifico il valore della funzione.

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

    for(x=0; x<=10; x++) {
      f=x*x-10*x+2;

      if(f<0)
        System.out.println("si");
      else
        System.out.println("no");
    }
  }
}

Questa soluzione è sbagliata

L'errore

L'istruzione condizionale if/else sta dentro il ciclo.

Quindi, viene eseguita una volta per ogni valore di x

Viene stampato si o no per dieci volte.

Seconda soluzione

Faccio la stampa solo alla fine.

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

    for(x=0; x<=10; x++) {
      f=x*x-10*x+2;
    }

    if(f<0)
      System.out.println("si");
    else
      System.out.println("no");
  }
}

Sbagliato!

f viene calcolata fino all'ultimo valore.

La stringa stampata dipende solo dall'ultimo valore.

(f=0 serve perhè altrimenti il programma non compila: provare per credere; il problema è che f viene usato quando non è sicuro che ci sia stato messo dentro un valore)

Asimmetria

A volte, il fatto che un programma sia sbagliato è evidente dal tipo di problema.

Nel nostro caso, la stringa da stampare era:

si: se fra i valori c'è un numero negativo
no: se tutti i valori sono positivi

Invece, nei programmi di sopra potrei scambiare si-no e <-> e ottenere lo stesso risultato.

Quindi, non può funzionare

Terza soluzione

Esprimo il problema in termini formali:

Se esiste un valore di x per il quale f è negativa, stampa si, altrimenti no

Lo trasformo in un programma che usa il meccanismo del risultato parziale, e che quindi funziona per induzione.

Il principio di induzione

In programmazione, devo fare un passo per volta.

Uso una variabile che mi dice il risultato parziale, calcolato solo sugli elementi che ho guardato finora.

Il principio di induzione dice che il risultato è corretto se:

lo è il valore iniziale
a ogni passo, considero un nuovo elemento e modifico il risultato parziale in modo corretto

Induzione, per trovare valori negativi

Nel nostro caso: devo vedere se fra n interi c'è un valore negativo.

caso base:

ho zero numeri interi; ci sono valori negativi?

caso generico:

assumo di sapere se ci sono valori negativi nei primi i-1 elementi
vedo se ci sono sui primi i elementi

Il primo caso è facile (la risposta è no)

Nel secondo caso: so se ci sono negativi fra i primi n=i-1:

se l'i-esimo valore è negativo, allora ci sono valori negativi fra tutti gli i=n elementi (indipendentemente dai primi n=i-1).
se l'i-esimo valore è negativo, allora la presenza di valori negativi equivale alla presenza di valori negativi fra i primi n=i-1 valori.

Dall'induzione al programma

Serve una scansione (un ciclo for)

Viene considerato un intero per volta.

Uso una variabile presente che dice se ho trovato un valore negativo finora

all'inizio, non ho ancora trovato un valore negativo (presente="no")
quando guardo un valore, posso contare sul fatto che presente indica se il valore è stato trovato fra gli elementi precedenti (assunzione del ciclo)
se il valore è negativo, allora ho trovato un valore negativo: presente="si"
se il valore è positivo, allora la presenza di valori negativi dipende dalla presenza fra gli elementi precedenti

Nell'ultimo caso, l'assunzione del ciclo mi dice che la presenza è data dal valore attuale di presenza, che quindi non va modificato.

Il ciclo, in parole povere

La variabile mi dice se ho trovato il valore negativo, fino a questo momento.

Inizialmente, non l'ho trovato.

Quando guardo un elemento, se è negativo l'ho trovato.

Se l'elemento non è negativo, allora la condizione "l'ho trovato" non cambia.

Presenza: codice

Si tratta di implementare il meccanismo detto sopra.

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

    String presenza;
    presenza="no";

    for(x=0; x<=10; x++) {
      f=x*x-10*x+2;

      if(f<0)
        presenza="si";
    }

    System.out.println(presenza);
  }
}

Costruzione del ciclo

Devo partire dall'assunzione che la variabile presenza contenga il risultato parziale corretto.

Nel corpo del ciclo, considero un nuovo elemento.

Uscire dal ciclo prima della fine

Se trovo l'elemento negativo, non serve guardare gli elementi.

L'istruzione break permette di uscire dal ciclo in qualsiasi momento.

  for(....) {
    ...
    break;
    ...
  }

  istruzione dopo;

Quando si esegue break, il ciclo viene interrotto automaticamente:

Diagramma di flusso

Quando si esegue break, si passa immediatamente ad eseguire l'istruzione che segue il ciclo (se c'è)

Esempio sul programma di presenza

Se trovo un elemento negativo, non serve andare avanti.

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

    boolean presenza;
    presenza=false;

    for(x=0; x<=10; x++) {
      f=x*x-10*x+2;

      if(f<0) {
        presenza=true;
        break;
      }
    }

    if(presenza)
      System.out.println("si");
    else
      System.out.println("no");
  }
}

Uso del `break`

Va messo dentro un ciclo

Di norma, sta in un condizionale, altrimenti non ha senso:

  for(....) {
    istruzione1;
    break;
    istruzione2;
  }

In questo caso, viene eseguita istruzione1 una volta sola, e poi basta.

Di solito viene messo in un condizionale:

  for(....) {
    istruzione1;
    if(condizione)
      break;
    istruzione2;
  }

Quando la condizione è vera, si esce dal ciclo.

`break`=condizione di uscita?

Dire quale è la differenza fra questi pezzi di programma

  // primo pezzo

  while(x!=0) {
    istruzione1;
    if(y==0)
      x=0;
    istruzione2;
  }

  // secondo pezzo

  while(x!=0) {
    istruzione1;
    if(y==0)
      break;
    istruzione2;
  }

Risposta

break: si esce dal ciclo immediatamente, senza eseguire le istruzioni che seguono (istruzione2)
falsificare la condizione di uscita: si esce dal ciclo solo quando la condizione viene controllata, ossia alla fine dell'esecuzione del corpo; quindi, istruzione2 viene eseguita un'ultima volta.

Esempio della differenza

Da questo ciclo, non si esce mai:

  while(x!=0) {
    if(y==0)
      x=0;

    x=1;
  }

Infatti, x viene messo a zero (e quindi la condizione di uscita dal ciclo x!=0 viene falsificata).

Però poi x viene rimesso a 1: quando viene controllata la condizione del ciclo, risulta sempre vera.

Nel caso del break:

  while(x!=0) {
    if(y==0)
      break;

    x=1;
  }

Se y vale 0, si esegue break e si esce subito dal ciclo, senza eseguire più l'istruzione x=1.

Esercizio sul `while`

Chiedere all'utente di inserire valori interi da tastiera, e stampare la metà di ognuno di essi.

Fermarsi quando viene letto un valore negativo.

Il valore negativo non deve essere stampato.

Nota: questo non è soltanto un esercizio!

Vedremo dei cicli che si possono usare anche per leggere da file ecc.

Soluzione

Si tratta di ripetere la sequenza lettura-scrittura, fino a che la lettura non produce un risultato negativo.

Primo tentativo:

import javax.swing.*;

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

    while(x>=0) {
      s=JOptionPane.showInputDialog("Scrivi un numero");
      x=Integer.parseInt(s);

      System.out.println(x/2);
    }

    System.exit(0);
  }
}

Errore di compilazione: x potrebbe non essere stata inizializzata.

Correzione: int x=0;

Attenzione: non posso mettere un valore qualsiasi in x: se usavo x=-10 il ciclo non veniva mai eseguito.

Errore di progettazione

Il programma stampa anche il primo numero negativo trovato, mentre doveva stampare solo i positivi.

Soluzione1: se trovo un negativo, non lo stampo.

import javax.swing.*;

class CicloLeggi {
  public static void main(String args[]) {
    String s;
    int x=0;

    while(x>=0) {
      s=JOptionPane.showInputDialog("Scrivi un numero");
      x=Integer.parseInt(s);

      if(x>=0)
        System.out.println(x/2);
    }

    System.exit(0);
  }
}

Seconda soluzione

Leggo il primo elemento.

Se è positivo, lo stampo e leggo il prossimo. Ripeto.

import javax.swing.*;

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

    s=JOptionPane.showInputDialog("Scrivi un numero");
    x=Integer.parseInt(s);

    while(x>=0) {
      System.out.println(x/2);

      s=JOptionPane.showInputDialog("Scrivi un numero");
      x=Integer.parseInt(s);
    }

    System.exit(0);
  }
}

Soluzione con il `break`

Se faccio: while(true) ho un ciclo infinito, dato che la condizione è sempre vera.

Però posso mettere un break quando voglio uscire.

import javax.swing.*;

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

    while(true) {
      s=JOptionPane.showInputDialog("Scrivi un numero");
      x=Integer.parseInt(s);

      if(x<0)
        break;

      System.out.println(x/2);
    }

    System.exit(0);
  }

Quale è il migliore?

Non c'è un ciclo migliore di altri.

Vanno tutti bene (se funzionano).

Ciclo infinito con `break`

Schema generale:

while(true) {
  istruzioni;

  if(condizione)
    break;

  istruzioni;
}

Si usa quando il "punto di uscita" del ciclo si trova in mezzo alle istruzioni da eseguire.

Quando la condizione è vera si esce
(al contrario, quando la condizione del while diventa falsa si esce)

Tavola pitagorica

Proviamo a risolvere questo esercizio:

Stampare la tavola pitagorica

Usare il fatto che System.out.print (senza ln) stampa senza andare a capo.

Versione semplificata: stampare soltanto i multipli di un numero intero x

Stampare un riga

Dato x, devo stampare x, x*2, x*3, ecc.

Faccio un ciclo:

  per ogni y da 1 a 10
    stampa x*y
  vai a capo

Il codice è immediato:

class Riga {
  public static void main(String args[]) {
    int x=5;

    int y;

    for(y=1; y<=10; y++) {
      System.out.print(x*y);
      System.out.print(" ");
    }

    System.out.println();
  }
}

Ora: fare il programma che stampa tutta la tavola pitagorica.

Algoritmo

So come stampare una riga.

Quello che devo fare è:

  per ogni x da 1 a 10
    stampa i multipli di x

Ora so come si fa a stampare i multipli di x!

Programma

La parte per ogni x diventa un ciclo

La parte stampa i multipli di x la risolvo come ho fatto prima,
ossia uso lo stesso identico blocco di prima.

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

    for(x=1; x<=10; x++) {
      int y;

      for(y=1; y<=10; y++) {
        System.out.print(x*y);
        System.out.print(" ");
      }

      System.out.println();
    }
  }
}

Nidificazione e allineamento

Ogni volta che inizio un blocco, oppure scrivo una istruzione all'interno di una istruzione composta, vado avanti di due spazi.

if(cond)
..istruzione;
else {
..istruzione;
..while(cond) {
....istruzione;
....istruzione;
..}
}

Rende più facile da capire il programma.

Attenzione! Non ha importanza per il compilatore:

if(condizione)
  istruzione;
  istruzione;

Equivale a:

if(condizione) {
  istruzione;
}

istruzione;

L'allineamento può trarre in inganno.

I cicli

Perchè servono i cicli?

La soluzione dello scriba

Soluzione con ciclo

Forma semplificata di ciclo

Cosa succede quando si esegue

Unfolding del ciclo

Non devo parlare in aula

Esercizio

Cento interi

Cento Pari

Soluzione con la moltiplicazione

Soluzione con if

Cicli dipendenti dai dati

Soluzione

Cicli: se m<n?

Forma generale del ciclo for

Parti di un ciclo

Unfolding del ciclo: caso generale

Unfolding, con salto

Ciclo: decremento

Decremento: soluzione

Corpo del ciclo

Inizializzazione, e incremento

Condizione di uscita

Perchè > invece di <?

Uso di <= invece di <

Esercizio sui cicli

Soluzione

Soluzione alternativa, con <=

Esercizio sui cicli

Stampa della funzione: soluzione

Inizializzazione ed incremento

Stampa dei valori positivi

Valori positivi: codice

Parentesi graffe

Risposta: si segue la sintassi dei cicli

Costruzione dei cicli

Sintassi del ciclo for

Ciclo while

Unfolding del ciclo while

Unfolding, con uscita

Equivalenza for-while

Perchè allora usare for?

Quando è meglio il while?

Un esempio di ciclo indefinito

Soluzione

Soluzione con il for

Metodo del risultato parziale

Metodo del risultato parziale

Paragone: algoritmo per riempire di biglie un secchiello

Esempio: somma dei valori

Somma di elementi: codice

Accumulatore: funzionamento

La somma e il principio di induzione

Induzione-Accumulatore

Principio di induzione e accumulatore

Anche se non avete capito...

Variante: moltiplicazione

Produttoria: soluzione

Il valore iniziale

Fattoriale

Calcolo del fattoriale

Calcolo del fattoriale

Esercizio

Soluzione

Correttezza dei cicli

Correttezza: assunzioni

Correttezza: mantenere le assunzioni

Programma corretto

Verifica di correttezza dei cicli

Operazioni logiche su insiemi

Soluzione

L'errore

Seconda soluzione

Asimmetria

Terza soluzione

Il principio di induzione

Induzione, per trovare valori negativi

Dall'induzione al programma

Soluzione con `if`

Cicli: se `m<n`?

Forma generale del ciclo `for`

Perchè `>` invece di `<`?

Uso di `<=` invece di `<`

Soluzione alternativa, con `<=`

Sintassi del ciclo `for`

Ciclo `while`

Unfolding del ciclo `while`

Equivalenza `for`-`while`

Perchè allora usare `for`?

Quando è meglio il `while`?

Soluzione con il `for`

Uso del `break`

`break`=condizione di uscita?

Esercizio sul `while`

Soluzione con il `break`

Ciclo infinito con `break`