|
|
|
|
Molt més
quant a vectors: el garbell d'Eratòstenes |
|
|
|
|
 |
Obre el projecte Vectors
i, en ell, crea una nova classe Eratostenes (perquè
en acabar aquesta pràctica hauràs programat el garbell
d'Eratòstenes) amb aquest codi: |
|
|
|
|
|
import java.util.*;
/**
* La classe Eratostenes porta a terme el mètode del
"garbell
* d'Eratòstenes" per seleccionar els nombres primers
que hi ha
* en una llista de nombres enters consecutius que comença
per 2.
*
* @author Carles Romero
* @version 2004/02/14
*/
public class Eratostenes {
/**
* Un Vector que contindrà objectes
de la classe Integer.
*/
Vector vectorEnters;
/**
* Mètode constructor per a
objectes de la classe Eratostenes.
* Inicializa el vector vectorEnters
amb n objectes Integer de
* valors respectius 2, 3, ..., n,
n+1.
* @param n el nombre d'objectes Integer
de valors respectius
* 2, 3, ..., n, n+1 amb que omplim
el vector vectorEnters
*/
public Eratostenes (int n) { //
constructor
vectorEnters=new
Vector();
posaValorsInicials(n);
}
/**
* Mètode que posa un objecte
Integer de valor 2 al primer lloc
* del Vector vectorEnters (índex
0), un objecte Integer de
* valor 3 al segon lloc (índex
1), un Integer de valor 4 al
* tercer lloc (índex 2), etc.
* @param n el nombre de components
que cal omplir. L'últim
* conté l'objecte Integer de
valor n+1;
*/
public void posaValorsInicials (int n) {
if
(vectorEnters==null) {
return;
}
vectorEnters.removeAllElements();
for
(int i=0;i<n;i++) {
vectorEnters.add(new
Integer(i+2));
}
}
}
|
|
|
|
|
|
|
Com sempre, abans
de compilar, convé entendre què hi ha escrit: |
|
|
|
|
|
- Les primeres línies de codi ja les coneixes:
- La primera línia importa el paquet java.util,
del SDK de Java
que cal importar per tenir al nostre abast la classe
Vector.
- La segona línia Vector vectorEnters;
declara el nostre vector com a variable d'instància.
(Vegeu que li hem donat el mateix
nom que en la classe FaDivisors,
però això no és cap problema,
perquè les variables d'una classe són invisibles
per a les altres classes)
|
|
|
|
|
|
- Tot seguit ve el mètode constructor.
- Primer es construeix el Vector vectorEnters
vectorEnters=new
Vector(); |
- Després (a diferència del que hem vist en els exemples
anteriors en què el mètode constructor només
creava la "carcassa" del vector però sense posar-hi
cap objecte) ar s'omple el vector tot demanant el mètode
public void posaValorsInicials (int n)
que es descriu seguidament
|
|
|
|
|
|
- Ja hem explicat abans la conveniència que a l'hora d'aplicar
un mètode al Vector vectorEnters es
comprovi si ja ha estat prèviament construït.
- Aquesta és la primera cosa que fa el mètode public
void posaValorsInicials (int n)
if
(vectorEnters==null) {
return;
}
|
Observa que, en cas que no estigui realment creat, la sentència
return fa que se surti del mètode.
Potser pensaràs que, si en la nostra classe, només
cridem el mètode posaValorsInicials
just des del constructor, segur que el vector estarà ja
construït. Però la comprovació que ara recomanem
és de caràcter general perquè... i si llavors
afegim nous mètodes a la classe que també cridin
posaValorsInicials?
- Després de la comprovació, si el vector Vector
vectorEnters existeix efectivament, el mètode el buida
completament
vectorEnters.removeAllElements(); |
|
|
|
- Ara s'omple amb n objectes (el paràmetre int
n del mètode!):
for
(int i=0;i<n;i++) {
vectorEnters.add(new
Integer(i+2));
} |
amb una estructura for
() {...}. Com ja saps, els elements s'afegeixen a vectorEnters
amb el mètode add (exactament public
boolean add(Object objecte)de la classe java.util.Vector.
Adoneu-vos que, com que es van afegint correlativament
i l'estructura for funciona
per i
de 0
a n-1
i per cada i
s'afegeix l'objecte Integer (i+2)
efectivament, com diuen les línies
de comentaris de la classe, tindrem el número 2 (com a objecte
Integer) al primer
lloc del Vector
vectorEnters (índex 0); un objecte
Integer
de valor 3 al segon lloc (índex 1);...
i així successivament fins al número n+1
com a objecte Integer
al lloc n-1 del vector, que en total té n objectes de la classe
Integer.
|
|
|
|
|
|
- És important de recordar per què no hi ha escrit el
codi (erroni)
per anar afegint els nombres a les successives posicions del vector.
Perquè no hem d'afegir nombres sinó objectes d'una classe
i, en aquest cas, ho fem de la classe Integer.
És a dir, estrictament no afegim el nombre i+2
sinó un nou objecte: new Integer (i+2).
|
|
|
|
|
|
Després d'aquestes
reflexions ja pots compilar. Després, crea un objecte d'aquesta classe,
amb 5 com a paràmetre del mètode
constructor, i l'inspecciones: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Com ja hem comentat abans, estàs
veient "per dintre" el Vector vectorEnters:
en realitat, protected Object[] elementData és
la matriu que conté els objectes que hi has posat i protected
int elementCount n'és el nombre. Aquest nombre és el
que s'obté amb el mètode public int size(). |
|
|
|
|
|
Segueix la inspecció:
mira ara protected Object[] elementData: |
|
|
|
|
|
|
|
|
|
|
|
La matriu protected
Object[] elementData té longitud 10: els cinc primers forats
estan ocupats per objectes, mentre que els altres cinc no tenen res a dintre.
Ara mira el segon objecte, a veure què és: |
|
|
|
|
|
|
|
|
|
|
|
És, com ja podies suposar,
un objecte Integer, que representa el nombre enter
3. Aquest valor és el que retorna el mètode
de la classe Integer, int intValue(). |
|
|
|
|
|
Per què és un 3?
Recorda que a l'index i hi has posat l'objecte
Integer que representa el valor int
i+2. Així doncs a la posició 1 "toca" el
3, oi que sí? |
|
|
|
|
|
Tot imprimint... |
|
|
|
|
|
|
Cal reconèixer que aquesta
és una manera una mica incòmoda de veure els nombres que hi
ha al Vector vectorEnters. Amb aquest nou mètode
(que cal que incorporis a la classe Eratostenes)
, |
|
|
|
|
|
< ... codi
anterior ... >
for
(int i=0;i<n;i++) {
vectorEnters.add(new
Integer(i+2));
}
}
}
|
/*
* Mètode per imprimir els valors
dels objectes Integer
* continguts en el vector vectorEnters
a la sortida estàndar
* del sistema.
*/
public void imprimeixVector () {
int quants=vectorEnters.size();
System.out.println("Hi
ha "+quants+" nombres:");
for
(int i=0;i<quants;i++) {
Object
objecte=vectorEnters.elementAt(i);
Integer
enter=(Integer)objecte; // casting
System.out.println(enter.intValue());
}
} |
|
|
|
|
|
|
aconsegueixes la llista de nombres
a la sortida estàndar del sistema (la pantalla). Analitzem-lo, que
hi ha una altra cosa importantíssima a aprendre:
|
|
|
|
|
|
- El mètode comença per preguntar-se
quants objectes hi ha al Vector vectorEnters
int
quants=vectorEnters.size(); |
|
|
|
|
|
|
- Després ens ho ensenya tot imprimint-ho: 
System.out.println("Hi
ha "+quants+" nombres:"); |
|
|
|
|
|
|
- Ara, amb una estructura
for (...) {...}, ens retorna l'objecte
(que hem designat amb el nom objecte), que
hi ha cadascun dels forats del Vector vectorEnters:
(No confonguis la classe Object
amb el nom de la variable que representa els nostres objectes que, per
fer-ho més entenedor hem designat com objecte.)
for
(int i=0;i<quants;i++) {
Object
objecte=vectorEnters.elementAt(i);
//
unes línies que expliquem després
} |
|
|
|
|
|
|
- Però, atenció! l'element
a la posició d'index i l'ha retornat
com a Object, encara que objecte
és,en realitat, un objecte de la classe Integer
(filla d'altra banda, com totes les classes a Java,
de la classe Object). En aquestes condicions,
la Màquina
Virtual no és capaç de reconèixer objecte
com a Integer, sinó que ho fa com a
simple Object! Per això, el següent
codi és incorrecte:
Integer
objecte=vectorEnters.elementAt(i); |
i aquest també:
Object
objecte=vectorEnters.elementAt(i); |
int
valor=objecte.intValue(); |
|
|
|
|
|
|
- La solució és fer la conversió
("casting" en anglès) d'Object a Integer. Aquesta
és la funció de la segona línia de codi dintre
de l'estructura for (...) inclosa al mètode
per imprimir:
Integer
enter=(Integer)objecte; // casting |
Naturalment, el casting
només funciona si objecte és
realment un objecte de la classe Integer!
Fixeu-vos en la sintaxi d'aquest casting que transforma cada
alobjecte que teníem emmagatzemat en
el vector en un objecte Integer (al que li
hem dit enter per donar a entendre que ja
es podrà interpretar com a tal.)
|
|
|
|
|
|
- Ara sí: ja es pot demanar a l'objecte
Integer quin valor int
representa i imprimir-lo com a nombre enter. La sintaxi és la
següent:
System.out.println(enter.intValue()); |
|
|
|
|
|
|
Aclarim això del casting
(conversió) |
|
|
|
|
|
 |
La conversió (casting)
és una de les necessitats més freqüents en qualsevol
entorn de programació i cada llenguatge resol aquest problema d'una
forma diferent. Hi ha llenguatges laxament tipificats, com Perl
o, en certa mesura javaScript
(bruts, en llengua col·loquial) que són molt elàstics
en la conversió entre tipus: una variable de cadena pot convertir-se
en un nombre enter i aquest en un nombre amb decimals en el moment en
què es vulgui: el compilador no es queixa, però és
responsabilitat seva que les conversions entre tipus siguin coherents.
|
|
|
|
|
|
Java
no permet aquests moviments ja que és un llenguatge fortament
tipificat: cada variable pertany estrictament al tipus en què
es va crear o al que n'ha resultat després d'enmagatzemar-la. Si
necessitem fer una conversió hem de crear una variable de destinació,
la qual contindrà el nou valor i només després podrem
fer la conversió, explícitament o implícita. |
|
|
|
|
|
En el nostre cas,
els objectes de la classe Integer han estat enmagatzemats
en el vector vectorEnters:
vectorEnters.add(new
Integer(i+2)); |
|
|
|
|
|
|
Però els vectors
enmagatzemen els objectes com a instàncies d'Object,
la classe mare de totes les classes i, a partir d'aquest moment, el fet
de ser instàncies de Integer queda com
ocult... i, per tal que, en recuperar-los,
Object
objecte=vectorEnters.elementAt(i); |
|
|
|
|
|
|
n'obtinguem l'Integer
que volem calen dues passes:
- Recuperar l'objecte, que, inevitablement, surt del vector
com a Object:
Object
objecte=vectorEnters.elementAt(i); |
- Fer-ne la conversió (casting) per tal de
restituir-li la condició de membre de la classe Integer:
Integer
enter=(Integer)objecte; // casting |
|
|
|
|
|
|
Podem observar, doncs, que la conversió (casting)
explícita es fa seguint aquesta sintaxi:
<Tipus
Nou> variable_nova=(<Tipus Nou>)variable_vella;
|
Posem entre parèntesis
i davant de la variable a convertir el nou tipus que pretenem
|
|
|
|
|
|
Ara compila i executa el mètode
public void imprimeixVector(): |
|
|
|
|
|
|
|
|
|
|
|
Voilà! |
|
|
|
|
|
Anem pel garbell d'Eratòstenes:
Eliminem tots els nombres no primers (compostos) |
|
|
|
|
|
|
El mètode del garbell d'Eratòstenes per seleccionar
els nombres primers que hi ha en una llista de nombres enters consecutius
que comença per 2 consisteix en:
- mantenir el 2 i barrar de dos en dos els altres nombres (que són
els múltiples de 2, és clar)
- anar al següent nombre no barrat (que serà el 3), mantenir-lo
i barrar de tres en tres els altres nombres ja barrats o no (que són
el múltiples de 3)
- ...
- anar al següent nombre no barrat, n, mantenir-lo i barrar
de n en n els altres nombres ja barrats o no (que són
els múltiples de n...)
Si ho fem així, al final només queden no barrats aquells
nombres que no són múltiples de cap altre nombre, és
a dir, els nombres primers.
|
|
|
|
|
|
El següent mètode fa, precisament, això i, en lloc
de barrar nombres, els canvia per
-1, cosa que permet identificar-los per tal
que siguin eliminats després:
|
|
|
|
|
|
<
... codi anterior ... >
Integer
enter=(Integer)objecte; // casting
System.out.println(enter.intValue());
}
} |
/**
* Métode que porta a terme el
garbell d'Eratòstenes.
*/
public
void eratostenes () {
if
(vectorEnters==null) {
return;
}
int quants=vectorEnters.size();
for
(int i=0;i<quants;i++) {
Object
objecte=vectorEnters.elementAt(i);
Integer
integer=(Integer)objecte;
int
nombre=integer.intValue();
boolean
estaBarrat=(nombre==-1);
if
(!estaBarrat) {
for
(int j=i+nombre;j<quants;
j=j+nombre) {
vectorEnters.setElementAt(
new
Integer("-1"),j);
}
}
}
for
(int i=quants;i>0;i--) {
Object
objecte=vectorEnters.elementAt(i-1);
Integer
integer=(Integer)objecte;
int
nombre=integer.intValue();
boolean
estaBarrat=(nombre==-1);
if
(estaBarrat) {
vectorEnters.remove(i-1);
}
}
} |
} |
|
|
|
|
|
|
Vegem-ne el funcionament: |
|
|
- El mètode comença preguntant-se si el Vector
vectorEnters existeix realment com a objecte i, en cas negatiu,
acaba:
if
(vectorEnters==null) { return;
// Per acabar qualsevol mètode!
}
|
|
|
|
- En en cas afirmatiu, si el vector vectorEnters existeix realment,
es continua l'execució del mètode tot demanant-ne el nombre
d'Objects que conté:
int
quants=vectorEnters.size(); |
|
|
|
|
|
|
- Ara, com sempre, amb una estructura for (...) {...},
va repassant-ne els objectes. Si l'objecte que troba no és un
nombre "barrat", és a dir, si no és -1,
actuarà, si no, no farà res i seguirà amb el següent
objecte:
for
(int i=0;i<quants;i++) {
Object
objecte=vectorEnters.elementAt(i);
Integer
integer=(Integer)objecte; //
casting
int
nombre=integer.intValue();
boolean
estaBarrat=(nombre==-1);
if
(!estaBarrat) {
//accions
que s'expliquen al
//
paràgraf següent
}
|
|
|
|
Ara, quan successivament anem trobant elements no barrats, cal
"barrar" tots els altres elements múltiples d'aquest
és a dir, els que trobem de nombre
en nombre. Per fer això, amb una altra
estructura for (...) {...}, que comença
a la posició actual més nombre
(j=i+nombre, si no, barraríem també
el nombre que ara tenim!), va posant un objecte Integer
de valor -1 a les posicions adequades: aquesta
és la manera de "barrar" els nombres múltiples
de nombre.
for
(int j=i+nombre;j<quants;j=j+nombre) {
vectorEnters.setElementAt(new
Integer("-1"),j);
} |
|
|
|
|
|
|
Ja hi ha tots els nombres no primers "barrats". Ja només
cal mirar quins elements estan "barrats" (tenen el valor -1)
i suprimir-los. Això cal fer-ho del final cap al principi! (què
passaria si no?). La manera de suprimir-los és l'execució
del mètode de la classe java.util.Vector,
public Object remove(int index) pels elements
que tinguin el valor -1:
for
(int i=quants;i>0;i--) {
Object
objecte=vectorEnters.elementAt(i-1);
Integer
integer=(Integer)objecte;
int
nombre=integer.intValue();
boolean
estaBarrat=(nombre==-1);
if
(estaBarrat) {
vectorEnters.remove(i-1);
}
} |
|
|
|
|
|
|
Compila, executa aquest nou mètode public void
eratostenes() i, amb l'inspector d'objectes, comprova que el Vector
vectorEnters (que abans havies construït amb 5 elements) s'ha
escurçat!
|
|
|
|
|
|
Tot seguit et proposem una nova experimentació.
Comença per construir l'objecte de la classe Eratostenes
però amb 60 nombres. |
|
|
|
|
|
|
|
|
|
|
|
i la inspecció del Vector
vectorEnters |
|
|
|
|
|
|
|
|
|
|
|
dóna 60 elements. Ara, sobre
aquesta instància de la classe que acabes de crear, executa el mètode
public void eratostenes(): |
|
|
|
|
|
|
|
|
|
|
|
i el Vector vectorEnters
s'ha escursat i només hi queden 18 elements! |
|
|
|
|
|
|
|
|
|
|
|
Aquests nombres que han
quedat al vector vectorEnters són els nombres
primers que hi ha entre 2 i 61. Mira-tel's amb l'inspector o bé imprimeix-los
amb el mètode void imprimeixVector(): |
|
|
|
|
|
|
|
|
|
|
|
I
ara un exercici: |
|
|
|
|
|
|
A la classe FaDivisors
de la pràctica anterior afegeix-li un mètode public
void imprimeixVector () (molt semblant al d'aquesta pràctica,
però no igual, perquè demanem una primera línia
que infomi de quin és el nombre del qual n'hem calculat els divisors),
que imprimeixi la llista dels divisors del nombre introduït en algun
deñls dos mètodes public void posaDivisors
(int n) o public void treuNoDivisors (int n).
La llista obtinguda ha de tenir aquest aspecte: |
|
|
|
|