Problema:Scrivere un programma Java 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:
int a,b; // i numeri letto da terminale int somma; // il numero da stampare su terminaleUn 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
int i; // indice sull'intervallo a..b+1e 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.
public class Somma { public static void main(String[] args) { int a,b; // i numeri letti da terminale int somma=0; // il numero da stampare su terminale a=AConsoleReader.readInt("Digita un numero intero:"); b=AConsoleReader.readInt("Digita un altro numero intero:"); if (b>=a) { int i=a; // indice sull'intervallo a..b+1 // a<=i<=b+1 AND somma="somma dei numeri nell'intervallo a..i-1" while (i<=b) { somma+=i; i++; } } // somma="somma dei numeri nell'intervallo a..b" System.out.println("La somma dei numeri nell'intervallo "+ a+".."+b+" e' "+somma); } }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
public class Somma { public static void main(String[] args) { int a,b; // i numeri letti da terminale int somma=0; // il numero da stampare su terminale int i; // indice sull'intervallo a..b+1 a=AConsoleReader.readInt("Digita un numero intero:"); b=AConsoleReader.readInt("Digita un altro numero intero:"); i=a; // a<=i<=max(b+1,a) AND somma="somma dei numeri nell'intervallo a..i-1" while (i<=n) { somma+=i; i++; } // somma="somma dei numeri nell'intervallo a..b" System.out.println("La somma dei numeri nell'intervallo "+ a+".."+b+" e' "+somma); } }
public class Somma { public static void main(String[] args) { int a,b; // i numeri letti da terminale int somma=0; // il numero da stampare su terminale a=AConsoleReader.readInt("Digita un numero intero:"); b=AConsoleReader.readInt("Digita un altro numero intero:"); // a<=i<=max(b+1,a) AND somma="somma dei numeri nell'intervallo a..i-1" for (int i=a; i<=b; i++) somma+=i; // somma="somma dei numeri nell'intervallo a..b" System.out.println("La somma dei numeri nell'intervallo "+ a+".."+b+" e' "+somma); } }
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":
{ int a,b; int i; // indice sull'intervallo a..b // eventuali altre dichiarazioni di variabili // a<=i<=max(b+1,a) AND "compito eseguito per l'intervallo a..i-1" while (i<=b) { // azione che fa passare da "compito eseguito per a..i-1" // a "compito eseguito per a..i" i++; } // compito eseguito per a..bUna versione equivalente dello "schema di programma" e' la seguente
{ int a,b; // eventuali altre dichiarazioni di variabili // a<=i<=max(b+1,a) AND "compito eseguito per l'intervallo a..i-1" for (int i=a; i<=b; i++) { // azione che fa passare da "compito eseguito per a..i-1" // a "compito eseguito per a..i" } // compito eseguito per a..b
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:
public class SommaDa0 { public static void main(String[] args) { int n; // il numero letto da terminale int somma=0; // il numero da stampare su terminale n=AConsoleReader.readInt("Digita un numero intero:"); // 0<=i<=max(n+1,0) AND somma="somma dei numeri nell'intervallo 0..i-1" for (int i=0; i<=n; i++) somma+=i; // somma="somma dei numeri nell'intervallo 0..n" System.out.println("La somma dei numeri nell'intervallo 0.."+ n+" e' "+somma); } }
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)+nOvvero:
S = 1+2+3+ ...+(n-2)+(n-1)+nProviamo 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):
public class SommaGauss { public static void main(String[] args) { int n; // il numero letto da terminale int somma=0; // il numero da stampare su terminale n=AConsoleReader.readInt("Digita un numero intero:"); if (n>0) somma=(n*(n+1))/2 // formula di Gauss // somma="somma dei numeri nell'intervallo 0..n" System.out.println("La somma dei numeri nell'intervallo 0.."+ n+" e' "+somma); } }