Array

• sono oggetti
• ci posso memorizzare insiemi di dati
• i dati devono essere tutti dello stesso tipo
• ogni array ha un numero prefissato di elementi

Dichiarazione

int v[];

Significa: v è un vettore di interi

È un oggetto che può contenere zero, uno o più interi.

Creazione

int v[];

v=new int[100];

Crea un oggetto vettore

È un contenitore per cento interi

Equivale a dichiarare cento variabili intere

Accesso alle variabili

Per gli array, non si usa la notazione oggetto.componente

Le componenti sono v[0], ..., v[99]

Array=insieme di variabili (quasi)

Dopo aver fatto:

int v[];
v=new int[100];

È come se esistessero cento variabili:

v[0]
v[1]
...
v[99]

Attenzione: se ho cento elementi, vanno da 0 a 99!

Rappresentazione grafica

È un oggetto:

Le componenti sono v[0], v[1], v[2],..., v[99] ecc.

Nella variabile c'è comunque il suo indirizzo

Perchè usare un vettore?

Quale vantaggio ho a usare un vettore (invece di cento variabili)?

• una sola dichiarazione
• posso fare dei cicli per accedere al valore di tutte le variabili

Esempio: mettere il valore 0 in tutte le variabili:

for(i=0; i<100; i++)
  v[i]=0;

Terminologia

Elemento del vettore=una delle variabili che ne fanno parte.

v=new int[100]

crea un vettore di cento elementi (=crea cento variabili)

v[9]

elemento del vettore v di indice 9

Accesso attraverso indici

Si può leggere/scrivere un elemento di un vettore come fosse una qualsiasi altra variabile.

Fra quadre (=come indice) posso mettere:

• un intero costante (es. 9)
• una espressione che ritorna un intero (es. i+2, oppure Integer.parseInt(s), ecc)

Vantaggio: si possono fare cicli per fare la stessa cosa su tutti gli elementi di un array

Attenzione: l'indice

• deve essere un intero (es. v[10.1] non funziona)
• deve essere compreso fra 0 e il numero di elementi del vettore meno uno (v[100] non funziona se il vettore ha cento elementi)

Esercizio

Creare un vettore di ventiquattro elementi interi,
memorizzare 10 in tutti, e stamparli.

Nota: println non funziona sui vettori
(stampa qualcosa, ma non le componenti)

Soluzione

La creazione del vettore è come al solito.

Per riempire il vettore di 10, faccio un ciclo.

Per stampare, faccio un altro ciclo

class Cento {
  public static void main(String args[]) {
    int v[];
    v=new int[24];
    int i;

    for(i=0; i<24; i++)
      v[i]=10;

    for(i=0; i<24; i++)
      System.out.println(v[i]);
  }
}

Vettori di oggetti

Il tipo degli elementi può essere qualsiasi.

Si possono fare anche vettori di oggetti.

Esercizio

Creare un vettore di venti punti.

Memorizzare i punti di coordinate (0,0), ..., (19,19).

Creazione array

Questo si fa come al solito, con Point al posto di int

import java.awt.*;

class Punti {
  public static void main(String args[]) {
    Point vp[];
    vp=new Point[20];

    // memorizzazione

    // stampa
  }
}

Mettere dati nell'array

I punti sono oggetti.

Quindi, una variabile contiene il suo riferimento.

Quindi, in vp[i] ci va l'indirizzo di un punto

Il punto va creato!

    int i;
    for(i=0; i<20; i++) 
      vp[i]=new Point(i,i);

vp[i] è una variabile oggetto

Può solo contenere l'indirizzo dell'oggetto.

Altro modo:

    int i;
    for(i=0; i<20; i++) {
      vp[i]=new Point();
      vp[i].move(i,i);
    }

Altro modo ancora:

    int i;
    for(i=0; i<20; i++) {
      vp[i]=new Point();
      vp[i].x=i;
      vp[i].y=i;
    }

Dato che vp[i] contiene un riferimento a un oggetto Point, posso usare i metodi e le componenti.

In memoria

È come quando ho un oggetto che contiene il riferimento ad altri oggetti (es. le classi Segmento e Studente)

Il programma completo

Basta aggiungere un ciclo di scrittura.

import java.awt.*;

class Punti {
  public static void main(String args[]) {
    Point vp[];
    vp=new Point[20];

    int i;
    for(i=0; i<20; i++) 
      vp[i]=new Point(i,i);

    for(i=0; i<20; i++)
      System.out.println(vp[i]);
  }
}

Esercizio

Stampare le prime duecento linee di un file in ordine inverso.

Assumere che il file contenga almeno duecento linee

Soluzione

Primo esempio significativo di uso dei vettori!

senza vettori:

apro il file, leggo duecento righe, stampo la duecentesima, riapro di nuovo il file, leggo 199 linee...

con i vettori:

leggo il file una sola volta, memorizzando le prime duecento linee in un vettore; poi le stampo in ordine inverso

Soluzione

• creo un vettore di duecento stringhe
• apro il file
• leggo duecento stringhe da file e le metto nel vettore
• stampo le stringhe del vettore in ordine inverso

Il codice

import java.io.*;

class InvertiFile {
  public static void main(String args[])
  throws IOException {

    String linee[];
    linee=new String[200];
    int i;


		// legge il file

    FileReader r=new FileReader("pur.txt");
    BufferedReader br=new BufferedReader(r);

    for(i=0; i<200; i++)
      linee[i]=br.readLine();


		// stampa a partire dall'ultima

    for(i=199; i>=0; i--)
      System.out.println(linee[i]);
  }
}

Gli oggetti stringa vengono creati da br.readLine()

Questo metodo restituisce l'indirizzo dell'oggetto creato, che viene poi memorizzato in linee[i]

Passaggio di vettori

I vettori sono oggetti

Si può passare a un metodo sia il singolo elemento che l'intero vettore

singolo elemento

si passa come un qualsiasi elemento del tipo

intero array

si specifica il tipo nella dichiarazione del metodo

In ogni caso, viene passato un valore
(nel secondo caso, è un indirizzo)

Esempio

Metodo che stampa i primi dieci elementi di un vettore

  static void stampaPrimi(int v[]) {
    int i;

    for(i=0; i<10; i++)
      System.out.println(v[i]);
  }

Esempio di programma:

  public static void main(String args[]) {
    int casuali[];
    casuali=new int[20];

    int i;
    for(i=0; i<20; i++)
      casuali[i]=(int) (Math.random()*101-50);

    stampaPrimi(casuali);
  }

Cosa succede in memoria?

Stessa cosa degli altri oggetti.

Prima dell'invocazione:

Durante l'esecuzione del metodo

Il valore di causali è stato copiato in v

Il valore di causali è quello che c'è scritto nella casellina (l'indirizzo dell'oggetto array)

Ora v[5] e causali[5] sono la stessa variabile.

È la stessa cosa che succede quando si passa un oggetto

Esercizio

Scrivere un metodo che mette nei primi dieci elementi di un vettore di interi i valori della funzione f(x)=x²+3x-2 per x=0,1,2,...,9

Il vettore viene passato come parametro.

Esempio di programma di prova:

class Funzione {
  // inserire qui il metodo

  static void stampaPrimi(int v[]) {
    int i;

    for(i=0; i<10; i++)
      System.out.println(v[i]);
  }

  public static void main(String args[]) {
    int f[];
    f=new int[20];

    funzione(f);
    stampaPrimi(f);
  }
}

Soluzione

Serve un ciclo

Per ogni intero, calcolo il valore della funzione e lo metto nel vettore.

  static void funzione(int v[]) {
    int x;

    for(x=0; x<10; x++)
      v[x]=x*x+3*x-2;
  }

Nota

Scrivere f[x]=... nel metodo è sbagliato.

Nella funzione, non si vede f

Le modifiche fatte dal metodo sono visibili nel programma perchè v[0] ecc e f[0] ecc sono la stessa variabile

Passare un elemento

Quello che si passa è il valore dell'elemento

class PassaElem {
  static void azzera(int x) {
    x=0;
  }

  public static void main(String args[]) {
    int v[];
    v=new int[10];

    int i;
    for(i=0; i<10; i++)
      v[i]=12;

    azzera(v[2]);

    System.out.println(v[2]);
  }
}

È il valore di v[2] che viene passato.

La variabile di partenza non viene modificata.

Si stampa 12

Lunghezza di un vettore

Se v è un vettore, allora:

  v.length

è il numero dei suoi elementi.

Nota: non è un metodo!

Non ci vanno le parentesi!

È come una componente dell'oggetto.

A che serve?

Un metodo può ricevere un vettore di lunghezza generica.

Per esempio, al metodo stampa posso passare un vettore di lunghezza 10, ma anche 2, 34, ecc.

v.length permette di vedere quanto è grande il vettore passato

Esercizio

Modificare il metodo stampa in modo che stampi tutti gli elementi del vettore

Deve funzionare con vettori di lunghezza arbitraria

Esempio di programma:

  public static void main(String args[]) {
    int x[];
    x=new int[100];

    int y[];
    y=new int[1030];

    // metti valori nei vettori

    stampa(x);
    stampa(y);
  }

Soluzione

Il ciclo va da 0 a v.length-1:

  public static void stampa(int v[]) {
    int i;

    for(i=0; i<v.length; i++)
      System.out.println(v[i]);
  }

uso length per sapere quanti elementi ha il vettore.

In questo modo, posso passare array di lunghezza diversa

Leggere array di interi da file

Si leggono stringhe, e si convertono in interi.

    int v[];
    v=new int[10];

    int i;

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);
    String s;

    for(i=0; i<10; i++) {
      s=br.readLine();
      v[i]=Integer.parseInt(s);
    }

Si poteva anche fare:
v[i]=Integer.parseInt(br.readLine());

Esercizio

Leggere dieci interi da file; per ognuno stampare la differenza dalla media.

Soluzione: algoritmo

• leggi gli interi in un vettore
• calcola la media
• per ogni elemento del vettore, stampa la differenza

Soluzione: implementazione

Primo: lettura del vettore da file

import java.io.*;

class DiffMedia {
  public static void main(String args[])
  throws IOException {

    int v[];
    v=new int[10];

    int i;

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);
    for(i=0; i<10; i++) 
      v[i]=Integer.parseInt(br.readLine());

Soluzione

Secondo: calcolo della media

    int somma=0;
    for(i=0; i<10; i++)
      somma=somma+v[i];

    double media=((double) somma)/10;

Soluzione

Terzo: stampa la differenza fra gli elementi e la media

    for(i=0; i<10; i++)
      System.out.println(v[i]-media);

Esercizio: massimo e posizione

Leggere un array di dieci interi da file. Trovare il suo elemento massimo, e la posizione in cui si trova.

Soluzione

Primo algoritmo:

1. leggi il vettore
2. trova massimo e posizione
3. stampa il massimo e la posizione

Il primo punto l'abbiamo già visto.

Il terzo punto è facile.

Passo 1: leggere il vettore

Come al solito

import java.io.*;

class Massimo {
  public static void main(String args[])
  throws IOException {
    int v[]=new int[10];
    int i;

		// lettura da file

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);
 
    for(i=0; i<10; i++) 
      v[i]=Integer.parseInt(br.readLine());

Questa parte di programma è stata già vista.

Ricerca del massimo

La ricerca del massimo l'abbiamo già vista:

• assumo che il massimo sia il primo
• per ogni elemento, vedo se è maggiore del massimo parziale

Serve una variante in cui trovo anche la posizione del massimo.

Ricerca di massimo e posizione

Uso un meccanismo simile (metodo della soluzione parziale).

Oltre a memorizzare il massimo valore trovato finora, memorizzo anche la sua posizione.

1. assumo che il massimo sia il primo
2. per ogni altro elemento del vettore, verifico se è maggiore del massimo

È lo stesso algoritmo di prima, in cui memorizzo anche la posizione del massimo.

    m=v[0];
    posm=0;

    for(i=1; i<10; i++)
      if(v[i]>m) {
        m=v[i];
        posm=i;
      }

La variabile m contiene il massimo trovato finora

La variabile posm contiene la sua posizione nel vettore

Algoritmo alternativo

Memorizzo solo la posizione del massimo trovato finora:

1. inizio: il massimo elemento è quello in prima posizione
2. per ogni nuova posizione, confronto

Dato che non ho memorizzato il massimo attuale ma la sua posizione, il confronto è fra v[i] (elemento attuale) e v[posm] (massimo finora):

    posm=0;

    for(i=1; i<10; i++)
      if(v[i]>v[posm]) 
        posm=i;

Array di oggetti

Un vettore può anche contenere oggetti

Se NomeClasse è una classe, si può fare:

  NomeClasse vett[];
  vett=new NomeClasse[100];

vett è un oggetto che contiene 100 variabili

Ogni variabile può contenere null oppure un riferimento a un oggetto di tipo NomeClasse (una istanza)

Esercizio: vettore di punti

Leggere da file un array di cinque punti da file, trovare quello più lontano dall'origine.

Per ogni punto, il file contiene due linee, una per ogni coordinata

Esempio di file:

4
-10
2
3
4
0
-2
1

Contiene i punti di coordinate (4,-10), (2,3), (4,0), (-2,1)

Soluzione: algoritmo

• si leggono i punti da file
• si trova il punto di distanza massima

Metodo distance della classe Point: ha come argomento il punto da cui calcolare la distanza.

Lettura punti da file

Per ogni punto ho la coordinata x e la coordinata y

Per ogni punto da leggere, leggo due interi e creo il punto.

import java.io.*;
import java.awt.*;

class LeggiPunti {
  public static void main(String args[])
  throws IOException {

    Point l[];
    l=new Point[5];

    int i;
    int x, y;

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);

    for(i=0; i<5; i++) {
      x=Integer.parseInt(br.readLine());
      y=Integer.parseInt(br.readLine());

      l[i]=new Point(x,y);
    }

Attenzione! Gli oggetti vanno creati!

La creazione del vettore non crea gli oggetti.

Punto più distante

Algoritmo:

1. assumo che il primo punto sia il più distante
2. per ogni altro punto, controllo se è più distante
3. se lo è, cambio le variabili che mi dicono il punto più distante e la sua distanza

È il solito algoritmo del risultato parziale.

    double maxdist;
    Point puntodist;
    Point origine=new Point(0,0);

    maxdist=l[0].distance(origine);
    puntodist=l[0];

    for(i=1; i<5; i++)
      if(l[i].distance(origine)>maxdist) {
        maxdist=l[i].distance(origine);
        puntodist=l[i];
      }

Stampo il risultato

    System.out.print("Il punto piu' distante e' ");
    System.out.println(puntodist);
    System.out.print("Si trova a distanza ");
    System.out.println(puntodist.distance(origine));

Array: tipi

Un array non è soltanto un insieme di elementi.

• tutti gli elementi dell'array devono essere dello stesso tipo
• nell'array posso mettere due volte lo stesso elemento (in posizioni diverse)
• l'array ha un numero specificato di elementi
• gli elementi vanno messi in posizioni specifiche

Array bidimensionali

Rappresentano le matrici.

int mat[][];
mat=new int[100][100];

Definisce le variabili mat[0][0], mat[0][1] ... mat[99][99]

Esercizio: tavola pitagorica

Memorizzare la tavola pitagorica in una matrice, e poi stampare la matrice.

Nella matrice ci vanno i numeri:

1 2 3 ...
2 4 6 ...
3 6 9 ...

Soluzione: stampare un riga

Per stampare la prima riga:

      for(j=0; j<10; j++)
        mat[0][j]=(1)*(j+1);

Notare il j+1

Gli indici vanno da 0 a 9,
i valori nella matrice da 1 a 10

Alternativa: ciclo da 1 a 10 e usare mat[0][j-1]

Per stampare la riga i:

     for(j=0; j<10; j++)
        mat[i][j]=(i+1)*(j+1);

Soluzione completa

Stampo la riga i per i che va da 0 a 9

class Matrice {
  public static void main(String args[]) {
    int mat[][];
    mat=new int[10][10];
    int i, j;
    
    for(i=0; i<10; i++)
      for(j=0; j<10; j++)
        mat[i][j]=(i+1)*(j+1);

    for(i=0; i<10; i++) {
      for(j=0; j<10; j++)
        System.out.print(mat[i][j]+" ");
      System.out.println();
    }
  }
}

Notare i+1 e j+1

L'alternativa era fare cicli da 1 a 10 e usare mat[i-1][j-1]

Il mistero svelato

Perchè devo fare:

class Esempio {
  public static void main(String args[]) {
    ...
  }
}

Cosa significa?

Risposta:

• in Java, posso scrivere istruzioni solo dentro i metodi
• i metodi li posso scrivere solo dentro le classi

Per scrivere un programma, faccio una classe con un metodo main dentro

In altri linguaggi, posso fare un programma scrivendo direttamente le istruzioni in un file, ma in Java non si può

Significato delle parti

class Esempio {
  public static void main(String args[]) {
    ...
  }
}

class Esempio

nome della classe

public

modificatore di accesso

static

si tratta di un metodo statico

void

è un metodo che non ritorna nessun valore

main

nome del metodo

(String args[])

argomento: un vettore di stringhe

Cosa c'è nel vettore?

L'argomento del metodo main è un vettore di stringhe

Quando si lancia il programma, si possono mettere dei dati:

java nomeclasse primastringa secondastringa terzastringa

Cosa succede quando un programma viene eseguito

java nomeclasse primastringa secondastringa terzastringa

• viene creato un array di stringhe, in cui vengono messi:
  • "primastringa" viene messo in posizione 0
  • "secondastringa" va in posizione 1
  • "terzastringa" va in posizione 2
  • ecc.
• se c'è un metodo statico main nella classe, viene invocato
• al metodo viene passato, come argomento, il vettore.

È come se il metodo main venisse invocato passando un vettore di stringhe composto dalle parole della linea di comando.

Quando main inizia

java nomeclasse primastringa secondastringa terzastringa

In questo caso, quando si esegue il corpo del metodo main:

• args[0] contiene "primastringa"
• args[1] contiene "secondastringa"
• args[2] contiene "terzastringa"

Il numero di stringhe passate è dato dalla dimensione del vettore.

Quindi, sta in in args.length

Esempio

Stampare il numero di parole che seguono il nome del programma nella invocazione, e poi le parole stesse.

Soluzione

Primo: il metodo main deve avere come argomento un vettore di stringhe (come al solito).

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

Al posto di args posso usare un nome qualsiasi (v, argomenti, pippo, ecc)

Quello che conta è la firma di main:

  public static void main(String[])

Soluzione

Il vettore args contiene le stringhe passate da linea di comando.

La sua lunghezza è il numero di parole

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

    System.out.print("Numero di parole passate: ");
    System.out.println(args.length);

Soluzione

Per stampare le parole, basta una scansione del vettore

    int i;

    for(i=0; i<args.length; i++)
      System.out.println(args[i]);
  }
}

Cosa succede quando si lancia il programma

Esempio di linea di comando:

java Argom abcd efgh 123

Le stringhe abcd efgh e 123 vengono messe nel vettore che viene passato a main

Quindi main riceve un vettore di tre stringhe.

Viene stampato:

Numero di parole passate: 3
abcd
efgh
123

Uso tipico degli argomenti

Programmi che usano i file hanno bisogno del nome

  FileReader r=new FileReader("lista.txt");

Al costruttore FileReader posso passare una stringa qualsiasi

  String s;
  s="lis".concat("ta.txt");

  FileReader r=new FileReader(s);

Nome file letto da tastiera

Posso fare new FileReader(s), e questo legge dal file il cui nome è la stringa memorizzata in s

Nella variabile s posso anche mettere una stringa letta da tastiera

  String s;
  s=JOptionPane.showInputDialog("Dammi il nome del file");

  FileReader r=new FileReader(s);

Nome file come parametro del programma

FileReader r=new FileReader(args[0]);

Quando si invoca il programma, bisogna fare

java NomeProgramma lista.txt

Dato che "lista.txt" va in args[0], questo è il file che viene letto

Vantaggio: posso usare lo stesso programma per fare le stesse operazioni su più file, senza dover cambiare il sorgente e ricompilare.

Numero di argomenti

L'utente potrebbe inserire il numero sbagliato di argomenti (per errore)

Controllare che l'utente abbia inserito il numero giusto di argomenti!

  if(args.length < 1) {
    System.out.println("Devi darmi il nome del file");
    return;
  }

Esercizio

Realizzare un programma di somma

Quando l'utente inserisce:

java Somma 12 43 -23 1 32

Il programma deve stampare la somma di questi elementi

Soluzione sbagliata

In args non ci sono interi, ma stringhe

Non posso fare somma=somma+args[i]

Soluzione

Gli elementi da sommare stanno in args[0],...,args[args.length-1]

Però sono stringhe: vanno prima convertite in interi

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

    somma=0;

    for(i=0; i<args.length; i++)
      somma=somma+
            Integer.parseInt(args[i]);

    System.out.println(somma);
  }

Leggere tutte le linee di un file

Finora ho sempre letto un numero prefissato di linee da file.

Ora, leggiamo tutte le linee del file.

Creazione del vettore

Per creare il vettore, devo sapere quanti elementi deve contenere.

Deve contenere un elemento per ogni linea del file.

Quindi, devo contare le linee del file

Conteggio linee del file

Leggo tutto il file, incrementando il contatore di uno ad ogni passo.

import java.io.*;

class LeggiTutti {
  public static void main(String args[])
  throws IOException {

		// conta le linee

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);
 
    int numero=0;
    String linea=br.readLine();
    while(linea!=null) {
      numero++;
      linea=br.readLine();
    }

Creazione del vettore e lettura

Ora so quanti elementi devo leggere.

È tutto uguale a prima.

Attenzione! Ora il BufferedReader sta alla fine del file.

Devo rileggere da capo, quindi riapro il file.

Lettura del vettore

		// crea il vettore

    String v[];
    v=new String[numero];

		// legge le linee

    r=new FileReader("lista.txt");
    br=new BufferedReader(r);
    int i;

    for(i=0; i<numero; i++) 
      v[i]=br.readLine();

Stampa del vettore

Come al solito:

		// stampa il vettore

    for(i=0; i<numero; i++)
      System.out.println(v[i]);

Variante

Modificare il programma in modo che il nome del file da aprire venga passato al programma

Soluzione

• controllo se effettivamente l'utente ha immesso una stringa come argomento
• uso args[0] come nome di file

import java.io.*;

class LeggiTuttiArg {
  public static void main(String args[])
  throws IOException {

		// controllo argomenti

    if(args.length<1) {
      System.out.println("Manca il nome del file");
      System.exit(0);
    }

		// conta le linee

    FileReader r=new FileReader(args[0]);
    BufferedReader br=new BufferedReader(r);
    ...

		// crea il vettore
		// legge le linee

    r=new FileReader(args[0]);
    br=new BufferedReader(r);
    ...
		// stampa il vettore
  }
}

Ricerca in vettore ordinato

Problema: decidere se un vettore contiene o no un certo elemento.

Suppongo che gli elementi del vettore siano in un certo ordine:

0
1
2
3
4
12
15
40
59
102

Soluzione per vettori non ordinati

Posso anche usare lo stesso algoritmo dei vettori non ordinati:

scansione del vettore; se trovo l'elemento ritorno true, altrimenti false.

Realizzo un metodo statico, a cui passo il vettore e l'elemento da cercare.

  public static boolean
  presente(int v[], int e) {
    int i;

    for(i=0; i<v.length; i++)
      if(v[i]==e)
        return true;

    return false;
  }

Si può anche fare con una variabile booleana e il break

Esempio di programma

  public static void main(String args[])
  throws IOException {

    int letti[];
    letti=new int[10];

                // lettura da file

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);

    int i;
    for(i=0; i<10; i++) 
      letti[i]=Integer.parseInt(br.readLine());

                // vede se il 14 e il 40 ci sono

    System.out.println(presente(letti, 14));
    System.out.println(presente(letti, 40));
  }

Ordinamento del vettore

La soluzione precedente funziona.

Non sfrutta il fatto che il vettore è ordinato:

0
1
2
3
4
12
15
40
59
102

Se cerco il 14, quando arrivo a 15 so che l'elemento non c'è

Ricerca per vettori ordinati

Quasi uguale a quello di prima.

Quando trovo un elemento maggiore di quello da cercare, mi fermo (so che l'elemento non c'è)

1. per ogni elemento del vettore:
   1. se ho trovato l'elemento, ritorno true
   2. se sono passato oltre, ritorno false
2. se ha fatto tutta la scansione senza trovare l'elemento, ritorno false

Implementazione dell'algoritmo

Rispetto a prima: esco se trovo un elemento maggiore di quello da cercare.

class Ricerca {
  public static boolean presente(int v[], int e) {
    int i;

    for(i=0; i<v.length; i++) {
      if(v[i]==e)
        return true;

      if(v[i]>e)
        return false;
    }

    return false;
  }

Domanda: in quale situazione si esegue l'ultimo return false;?

Risposta

Se tutti gli elementi del vettore sono minori di quello da cercare

In questo caso, si fa la scansione di tutto il vettore senza mai eseguire uno dei due return del corpo del ciclo

Si esce dal ciclo e si esegue l'ultimo return

Esempio di programma

  public static void main(String args[])
  throws IOException {

    int letti[];
    letti=new int[10];

                // lettura da file

    FileReader r=new FileReader("lista.txt");
    BufferedReader br=new BufferedReader(r);

    int i;
    for(i=0; i<10; i++)
      letti[i]=Integer.parseInt(br.readLine());

                // vede se il 14 e il 40 ci sono

    System.out.println(presente(letti, 14));
    System.out.println(presente(letti, 40));
  }

È lo stesso programma di prima.

Vantaggio dei metodi: posso cambiare il modo di fare una cosa (es. cercare in un vettore) senza dover cambiare il programma.

Esercizio

Controllare se sul file punord.txt c'è il punto (12,0)

Nel file ci sono dieci punti:
per ognuno, ho una linea per ogni coordinata

I punti sono memorizzati in ordine di distanza crescente dall'origine

Scrivere un metodo che usa questo fatto:

  static boolean cercaPunto(Point v[], Point p) {
    ...
  }

Dopo, scrivere il programma

Soluzione

Faccio la solita ricerca:

  static boolean cercaPunto(Point v[], Point p) {
    int i;

    for(i=0; i<v.length; i++) {
      if(p.equals(v[i]))
        return true;
    }

    return false;
  }

Il confronto si può anche fare:

if(v[i].equals(p)) 
if( (v[i].x==p.x) && (v[i].y==p.y) )
if( (p.x==v[i].x) && (p.y==v[i].y) )

Non si può fare v[i]==p, perchè sono oggetti

Non ho usato l'ordinamento.

Usare l'ordinamento

Creo un punto con coordinate (0,0)

Quando trovo un punto di distanza maggiore di quello cercato, mi fermo.

  static boolean cercaPunto(Point v[], Point p) {
    Point o=new Point(0,0);
    int i;

    for(i=0; i<v.length; i++) {
      if(p.equals(v[i]))
        return true;

      if(p.distance(o)>v[i].distance(o))
        return false;
    }

    return false;
  }

Se v[i] contiene l'indirizzo di un oggetto Point, posso usare v[i].x oppure v[i].distance(o) ecc.

Il programma

Leggo i punti da file.

Per ogni punto, leggo due interi.

  public static void main(String args[]) 
  throws IOException {
    Point p[];
    p=new Point[20];

    FileReader r=new FileReader("punord.txt");
    BufferedReader br=new BufferedReader(r);
    int i;
    for(i=0; i<10; i++) {
      String s;
      int x, y;

      s=br.readLine();
      x=Integer.parseInt(s);

      s=br.readLine();
      y=Integer.parseInt(s);

      p[i]=new Point(x, y);
    }

    Point c=new Point(12,0);

    System.out.println(cercaPunto(p, c));
  }
}

Array: creazione statica

La creazione di array vista finora avviene in due passi:

  int v[];	// crea la variabile
  v=new int[10];// crea l'array

È possibile creare un array direttamente con dei valori dentro:

  int v[]={-2, -3, 0, -4, 9};

Attenzione! Non si può fare in due passi:

  // non compila
  int v[];
  v={-2, -3, 0, -4, 9};

La creazione statica non ci interessa

Errore comune n. 1

Usare l'array senza averlo creato

  int v[];

  v[0]=12;

Gli array in Java sono oggetti

Quando creo la variabile, ho solo creato lo spazio per un indirizzo, non ho creato l'oggetto.

Errore comune n. 2

Attenzione alle parentesi!

  int x, y;
  int v[];
  String s[];

  x=v.length;
  y=s.length();

Le parentesi si mettono per le stringhe, non si mettono per gli array.

Principio: negli array, è una componente, nelle stringhe un metodo.

Errore comune n. 3

Per copiare un vettore:

    int v[]={-2, -3, 0, -4, 9};
    int k[];

    k=v;

Come per gli oggetti: l'oggetto è sempre quello!

Se cambio k[2], cambia anche v[2], dato che k e v puntano allo stesso oggetto array.

Modo giusto: creare un nuovo vettore e fare la copia con un ciclo.

Vedremo poi un modo semplice per fare la copia

Esercizio: salvare valori di una funzione

Sia dato un metodo statico funzione(int) che calcola i valori di una funzione:

class Salva {
     // esempio di funzione
  static int funzione(int x) {
    return x*x-3*x+2;
  }

  // scrivere qui il main
}

Memorizzare i valori della funzione, per x intero da -10 a 10, in un vettore.

Determinare il minimo della funzione per x intero da -5 a 5, la somma da -20 a 5, e verificare l'esistenza di valori negativi da 0 a 15.

Usare il vettore per i valori già calcolati

Creazione del vettore

Fra -10 e 10 ci sono ventuno elementi:

  public static void main(String args[]) {
    int f[];
    f=new int[21];

    // memorizza
    // calcola il minimo
    // calcola la somma
    // verifica valori negativi
  }

Memorizzazione

Devo tenere presente che i valori di x vanno da -10 a 10, mentre gli indici del vettore vanno da 0 a 20

Si tratta di una relazione lineare:

Si tratta di una relazione lineare:
dato x, l'indice del vettore in cui sta f(x) è x+10

Controllare che funzioni anche per l'ultimo indice:
per x=10 risulta x+10=20, che è l'ultimo indice del vettore

  public static void main(String args[]) {
    int f[];
    f=new int[21];

    int x;
    for(x=-10; x<=10; x++)
      f[x+10]=funzione(x);

    // calcola il minimo
    // calcola la somma
    // verifica valori negativi
  }

Usare il vettore

Per il calcolo del minimo, vado a guardare il vettore invece di calcolare la funzione:

    x=-5;
    int minimo=f[x+10];
    for(x=-5; x<=5; x++)
      if(f[x+10]<minimo)
        minimo=f[x+10];
    System.out.println(minimo);

Questo era facile...

Calcolo della somma

La somma va fatta da -20 a 5, quindi ci sono valori che non si trovano nel vettore.

La somma normalmente sarebbe:

    int somma;
    somma=0;
    for(x=-20; x<=5; x++)
      somma=somma+funzione(x);
    System.out.println(somma);

Ogni volta che compare funzione(x), verifico se x sta fra -10 e 10.

In questo caso, uso il vettore invece del metodo.

Calcolo della somma, con il vettore

Al posto di funzione(x), uso f[x+10] se x è compreso fra -10 e 10:

    somma=0;
    for(x=-20; x<=5; x++)
      if((x>=-10) && (x<=10))
        somma=somma+f[x+10];
      else
        somma=somma+funzione(x);
    System.out.println(somma);

Esistenza valori negativi

Anche qui, servono alcuni valori della funzione che non sono memorizzati nell'array

Per il resto, è la solita verifica:

    boolean negativi;
    negativi=false;
    for(x=0; x<=15; x++)
      if(funzione(x)<0)
         negativi=true;
    System.out.println(negativi);

Verifica valori negativi

Posso memorizzare il valore della funzione in una variabile val e poi usarlo:

    int val;
    negativi=false;
    for(x=0; x<=15; x++) {
      if((x>=-10) && (x<=10))
         val=f[x+10];
      else
         val=funzione(x);

      if(val<0)
            negativi=true;
    }
    System.out.println(negativi);

Alternativa: doppio if (prox pag)

Soluzione con due if

Uso f[x+10] oppure funzione(x) a seconda dei valori di x:

    negativi=false;
    for(x=0; x<=15; x++)
      if((x>=-10) && (x<=10))
        if(f[x+10]<0)
          negativi=true;
      else
        if(funzione(x)<0)
          negativi=true;
    System.out.println(negativi);

Trovare l'errore

Errore: ambiguità dell'if

L'else si attacca all'ultimo if

Soluzione corretta:

    negativi=false;
    for(x=0; x<=15; x++)
      if((x>=-10) && (x<=10)) {
        if(f[x+10]<0)
          negativi=true;
      }
      else {
        if(funzione(x)<0)
          negativi=true;
      }
    System.out.println(negativi);