1.- Enunciat:
La Federació Interplanetària del Sistema Solar Alpha-112 ha definit una normativa d'associació entre els seus membres i vol informatitzar el procés d'altes i baixes i el disseny de la xarxa de comunicacions.Considerarem en tot moment que hi haurà M planetes en el sistema, amb identificadors numèrics naturals no acotats. En tot moment hi haurà una associació que pot estar buida, contenir tots els planetes o qualsevol situació intermèdia.Cada planeta del sistema, pertanyi o no a l'associació, és avaluat periòdicament segons N criteris (geogràfics, econòmics, socials ...) de manera que per a cada criteri el planeta rep una puntuació numèrica natural. Els criteris s'identifiquen mitjançant els valors de l'interval 1..N. Finalment, es considera com criteri addicional que el planeta tingui aigua. Paral·lelament, l'associació estableix un valor mínim per a cadascun dels N criteris anteriorment esmentats, que han ésser arribats pels planetes que desitgin entrar en l'associació. Els llindars mínims establerts per l'associació són actualitzables.
1.1.- Xarxa de comunicacions:
Tots els missatges de l'associació parteixen d'un planeta especial de la mateixa, cridat "emissor" que s'encarrega de transmetre'ls a la resta dels planetes membres, per mitjà de la xarxa de l'associació.La xarxa de l'associació funciona de la següent manera: si un missatge arriba a un planeta P qualsevol, aquest pot enviar-se'l a un màxim de dos planetes predeterminats, cridats els "continuadors" del planeta P. D'aquesta manera, l'emissor envia els missatges als seus continuadors, aquests als seus i així successivament fins que la informació arribi a tots els planetes de l'associació. Si un planeta té dos continuadors, ha d'haver una manera de distingir entre el primer continuador i el segon.La xarxa de l'associació ha de complir que tots els seus membres estiguin connectats de la manera descrita (tots els planetes, excepte l'emissor, són continuadors d'algun altre, així no haurà cap planeta al que no arribi la informació). Òbviament, en el cas d'una associació uniplanetaria, l'emissor és l'únic planeta que hi ha. Per altra banda, un planeta no pot ser continuador de si mateix, ni dels seus continuadors, ni dels continuadors d'aquests, etc. Finalment, la xarxa de comunicacions de l'associació només pot canviar en cas d'altes o baixes de planetes.
1.2.- Altes i baixes:
Alta normal:Quan un planeta demana ingressar en l'associació, es comprova si per a tots els criteris, la seva puntuació és igual o major que la demanada per l'associació. En cas afirmatiu, el planeta es converteix en continuador del planeta més proper a l'emissor de l'associació que tingui menys de dos continuadors (de moment, els casos d'empat es poden resoldre de qualsevol manera, però es publicarà un criteri precís més endavant). Si aquest planeta no té continuadors, el nou pansa a ser el seu primer continuador i, en cas contrari, passarà a ser el segon.La distància entre l'emissor i un planeta qualsevol es defineix com el nombre de planetes pels quals ha de passar un missatge per a arribar de l'u a l'altre. La distància de l'emissor a si mateix és 0. La de l'emissor als seus continuadors és 1 i així successivament.
Alta per compensació (només s'aplica si falla l'anterior):En cas que el mètode anterior doni un resultat negatiu, un planeta P encara pot entrar en l'associació amb l'ajuda d'altre planeta Q que ja sigui membre de la mateixa, si es compleixen la següents condicions al mateix temps:
- Q no té aigua i P si,
- està lliure l'altra posició de continuador del mateix planeta del que Q és continuador,
- per a cada criteri tal que la puntuació de P no arribi al valor mínim comanda per l'associació, la suma de la puntuació de P més la puntuació que li sobri a Q en aquest criteri (la diferència entre la seva puntuació i el mínim), iguala o supera el valor mínim definit per l'associació.
Si es donen les tres condicions esmentades, el planeta P es col·loca com continuador del mateix planeta que Q, que té una plaça lliure per la condició b). En cas que faig diverses opcions que permetin entrar a P d'aquesta manera, es tria la qual ho col·loqui més prop de l'emissor, com en el cas anterior.
Baixa:Un planeta pot donar-se de baixa de l'associació només si no té continuadors. Els requisits d'entrada no s'apliquen retroactivament, és a dir, si un planeta ja està en l'associació no li pot expulsar, encara que baixin les seves puntuacions o pugin els requisits de l'associació.
1.3.- Exemples
Resolució d'empats: com en els exemples b) i c), si hi ha més d'una possibilitat on penjar el planeta nou, es tria la de més a l'esquerra possible. Suposem que el primer continuador d'un planeta se situa a la seva esquerra i el segon a la seva dreta.
Situació resultant si el 6 no es compensat pel 3, però sí per l'1 (noti's que si ni el 1 ni el 3 compensessin al 6, aquest no podria entrar).
Resolució d'empats: igual que en el cas anterior, però tenint en compte que el nou planeta ha de penjar-se d'un altre que ja tingui un continuador. Aquest ha de compensar els valors deficitaris del nou.
Baixes
Es poden esborrar: el 4, el 7, l'1, el 8 i el 2. Si demanem esborrar el 8.
1.4.- Es demana
Fer un programa modular i eficient, amb especificació, implementació i derivació informal (excepte de les classes d'entrada/sortida) i després codificar-ho en JAVA, utilitzant si cal les classes que hem estudiat durant el curs (Pila, InOut, Arbre, Rentadora, Estudiant, ...).
- Afegir un planeta a l'associació. Informar de si s'ha pogut realitzar o no.
- Treure un planeta de l'associació. Informar de si s'ha pogut realitzar o no.
- Escriure els identificadors dels planetes de l'associació en ordre creixent.
- Escriure els identificadors dels planetes de l'associació, reflexant l'estructura de la xarxa de comunicacions.
- Obtenir quin es el millor planeta per un criteri concret, d'entre els que no pertanyen a l'associació.
- Modificar les puntuacions d'un planeta qualsevol.
- Modificar els valor del requisits mínims establerts per l'associació.
2.- Descripció general
Un cop hem llegit tots els planetes que pertanyen al sistema solar els processos més importants seran els de altes i baixes dels planetes. Tot i això es poden realitzar diverses més operacions però les anteriorment mencionades són les d'una complexitat més gran així com les que més cops es faran servir en el programa. Aquest darrer punt fa que sigui important tenir en compte l'eficiència de les citades rutines ja que l'ús intensiu que s'en farà serà un factor determinant en l'eficiència del programa en general i en la velocitat de poder generar la sortida. Les classes que utilitzarem en aquest programa seran;
- Planeta:on es desarà la informació respecte un planeta com el seu identificador, els criteris, si pertany a l'associació de planetes i si és un planeta que conté aigua.
- Associació: arbre d'enters on es desa l'estructura dels planetes identificant-los pel seu identificador. També es desen els requisits de l'associació en un veco d'enters.
- Sistema Solar: vector que conté els planetes del sistema solar, també té un enter que indica el número de planetes.
Més informació:
Joc de proves públic
(a la universitat només ens ho van donar en espanyol)
PRÁCTICA DE PRAP - JUEGO DE PRUEBAS PÚBLICO
Esquema del documento:
0. Observaciones previas.
1. Composición de los juegos de pruebas.
2. Entrada y salida de las operaciones.
3. Juego de pruebas público.
--------------------------------------------------
0. OBSERVACIONES PREVIAS
--------------------------------------------------
* El número de planetas será M = 10. De todas formas, el programa debería
funcionar (con juegos de pruebas convenientemente adaptados) si M fuera
cualquier otro valor mayor que cero. El número de criterios será N = 8. Los
identificadores de planetas son números naturales entre 1 y el mayor valor
permitido por java para el tipo int. Los identificadores de criterios son los
valores 1..N.
* Salvo excepciones, los datos de operaciones diferentes se leerán en líneas
diferentes y los resultados de operaciones diferentes se escribirán en líneas
diferentes.
* Los ficheros de entrada de los juegos de pruebas tendrán líneas de menos de
80 caracteres.
-------------------------------------------------------------------------------
1. COMPOSICIÓN DE LOS JUEGOS DE PRUEBAS
-------------------------------------------------------------------------------
La primera acción es leer un conjunto de M planetas del siguiente modo: por
cada planeta, se lee su id, luego sus N criterios empezando por el primero
hasta el octavo y, por último, un booleano que indica si contiene agua.
Seguidamente viene la lectura de los miembros de la asociación. Por último, la
lectura de los N criterios mínimos de la asociación, en forma de pares
<id_criterio, valor>.
La asociación se presenta como un árbol binario de enteros (identificadores)
recorrido en PREORDEN: primero el emisor, después los continuadores por la
izquierda, también en preorden y, por último, los continuadores por la derecha,
asimismo en preorden. Notad que identificamos el primer continuador de un
planeta con la raíz del subárbol izquierdo que cuelga de él y el segundo
continuador con la raíz del subárbol derecho que cuelga de él.
Cuando se pida escribir los miembros de la asociación, reflejando la estructura
de la red, se hará en INORDEN: primero los continuadores por la izquierda del
emisor, también en inorden, después el emisor y, por último, los continuadores
por la derecha del emisor, también en inorden. Para más información, consultad
el módulo ArbInOutint de la sesión 6 de laboratorio.
-------------------------------------------------------------------------------
2. ENTRADA Y SALIDA DE LAS OPERACIONES
-------------------------------------------------------------------------------
Cada operación se identifica mediante un código numérico, que será un entero
negativo entre -1 y -8 (esto se ha elegido simplemente para favorecer la
legibilidad de los juegos de pruebas). Cada operación comenzará con su código y
a éste le seguirán los datos de la misma, si es que necesita alguno.
A continuación, detallamos las diferentes operaciones. Para ver ejemplos
concretos de la sintaxis de sus entradas y salidas, ir al apartado 3.
* AÑADIR UN PLANETA A LA ASOCIACIÓN
Identificación: -1
Datos: el id de un planeta del sistema. Se garantiza que el planeta *NO* está
en la asociación.
Salida: 0 si no se puede añadir, 1 si se añade por el primer método y 2 si es
por el segundo.
Efectos secundarios: se añade el planeta a la asociación, si se cumplen las
condiciones para ello.
* QUITAR UN PLANETA DE LA ASOCIACIÓN
Identificación: -2
Datos: el id de un planeta del sistema. No se garantiza que el planeta esté en
la asociación.
Salida: 1 si se puede eliminar, 0 en caso contrario.
Efectos secundarios: se elimina el planeta de la asociación, si está en ella y
no tiene continuadores.
* ESCRIBIR LOS ID'S DE LOS PLANETAS DE LA ASOCIACIÓN EN ORDEN CRECIENTE
Identificación: -3
Datos: no tiene
Salida: los id's de los planetas de la asociación en orden ascendente.
Si la asociación está vacía, no hay salida.
Efectos secundarios: no tiene.
* ESCRIBIR LOS ID'S DE LOS PLANETAS DE LA ASOCIACIÓN REFLEJANDO LA RED DE
COMUNICACIONES DE LA ASOCIACIÓN.
Identificación: -4
Datos: no tiene.
Salida: los id's de los planetas de la asociación en INORDEN. Si la asociación
está vacía, no hay salida.
Efectos secundarios: no tiene.
* BUSCAR EL MEJOR PLANETA, QUE NO ESTE EN LA ASOCIACIÓN, PARA UN CRITERIO
Identificación: -5
Datos: el id del criterio (un valor entre 1 y N).
Salida: el id del planeta con mejor puntuación en el criterio dado que no
pertenezca a la asociación o 0 si no hay ningún planeta que no esté en la
asociación. Si la mejor puntuación es compartida por más de un planeta,
se devolverá el que tenga el identificador más pequeño.
Efectos secundarios: no tiene.
* MODIFICAR LAS PUNTUACIONES DE UN PLANETA CUALQUIERA
Identificación: -6
Datos: el id de un planeta del sistema, el número de criterios que se van a
leer (un valor entre 1 y N) y, por cada uno de estos, un par <id_criterio,
valor>
Salida: no tiene.
Efectos secundarios: cambian los valores de los criterios leídos del planeta
correspondiente.
* MODIFICAR LOS REQUISITOS MÍNIMOS DE LA ASOCIACIÓN
Identificación: -7
Datos: el número de criterios que se van a modificar (un valor entre 1 y N) y,
por cada uno de estos, un par <id_criterio, valor>
Salida: no tiene
Efectos secundarios: cambian los valores de los requisitos leídos de la
asociación.
* SALIR DEL PROGRAMA:
Identificación: -8
------------------------------------------------------
3. JUEGO DE PRUEBAS PÚBLICO
------------------------------------------------------
Entrada comentada:
------------------
10 2 4 5 6 7 5 3 7 false // Datos de los M planetas:
23 3 4 6 3 2 6 7 4 true // para cada planeta se lee el id,
54 6 6 3 6 9 8 6 7 false // seguido de los N criterios y por último
89 1 3 4 5 3 2 5 6 true // un booleano que indica si tiene agua
79 2 4 2 5 2 7 5 3 true
11 2 4 5 2 2 7 4 3 true
91 4 2 1 5 1 3 6 7 false
51 4 8 6 5 1 2 4 6 true
45 1 5 2 2 4 6 5 5 true
73 6 5 8 7 6 6 5 5 false
23 79 10 0 0 91 0 0 89 54 0 0 0 // Planetas de la asoc. en preorden
1 5 // Requisitos mínimos de la asoc.:
2 5 // el ident. de cada requisito
3 5 // seguido de su valor, en este ejemplo
4 5 // todos los valores son 5
5 5
7 5
6 5
8 5
-4 // escribe la red en inorden
-1 // añade un planeta
45 // el id del nuevo planeta es 45
-4 // escribe la red en inorden
-1 // añade un planeta
51 // el id del nuevo planeta es 51
-4 // escribe la red en inorden
-1 // añade un planeta
73 // el id del nuevo planeta es 73
-4 // escribe la red en inorden
-6 // modifica las puntuaciones de un planeta
73 // id del planeta
4 // total de criterios a alterar
5 0 // pares <id_criterio, valor>
2 0
7 0
1 0
-7 // modifica los requisitos mínimos
2 // total de requisitos a modificar
2 1 // id de cada requisito seguido de su valor
6 1
-2 // elimina un planeta de la asoc.
73 // id del planeta a eliminar
-4 // escribe la red en inorden
-5 // busca el mejor planeta para un criterio
1 // criterio 1
-3 // escribe los ids de los planetas de la asoc.
-8 // fin del programa
Salida comentada:
-----------------
10 79 91 23 54 89 // red de comunicaciones
0 // el planeta no se puede añadir a la asoc.
10 79 91 23 54 89 // red de comunicaciones
2 // el nuevo planeta se añade por compensación
10 79 91 23 54 89 51 // red de comunicaciones
1 // el nuevo planeta se añade por alta normal
73 10 79 91 23 54 89 51 // red de comunicaciones
1 // el planeta se ha podido quitar
10 79 91 23 54 89 51 // red de comunicaciones
11 // mejor planeta para el criterio 1 que no pertenece a la asoc.
10 23 51 54 79 89 91 // ids de los planetas de la asoc. en orden asc.
Al final puede haber una línea en blanco o más.
-------------------------------------------------------------------------------
Entrada sin comentar: cortadla y pegadla en un fichero para usarla como entrada
a vuestro programa mediante la redirección <.
-------------------------------------------------------------------------------
10 2 4 5 6 7 5 3 7 false
23 3 4 6 3 2 6 7 4 true
54 6 6 3 6 9 8 6 7 false
89 1 3 4 5 3 2 5 6 true
79 2 4 2 5 2 7 5 3 true
11 2 4 5 2 2 7 4 3 true
91 4 2 1 5 1 3 6 7 false
51 4 8 6 5 1 2 4 6 true
45 1 5 2 2 4 6 5 5 true
73 6 5 8 7 6 6 5 5 false
23 79 10 0 0 91 0 0 89 54 0 0 0
1 5
2 5
3 5
4 5
5 5
7 5
6 5
8 5
-4
-1
45
-4
-1
51
-4
-1
73
-4
-6
73
4
5 0
2 0
7 0
1 0
-7
2
2 1
6 1
-2
73
-4
-5
1
-3
-8
-------------------------------------------------------------------------------
Salida sin comentar: vuestro resultado ha de coincidir exactamente con éste
(probándolo con el comando diff de unix/linux), salvo las líneas en blanco del
final, que pueden variar.
------------------------------------------------------------------------------
10 79 91 23 54 89
0
10 79 91 23 54 89
2
10 79 91 23 54 89 51
1
73 10 79 91 23 54 89 51
1
10 79 91 23 54 89 51
11
10 23 51 54 79 89 91
------------------------------------------------------------------------------
Joc de proves privat
jp privado 1 10 4 2 5 6 7 5 3 7 false 23 4 3 6 3 2 6 7 4 true 54 6 6 3 6 9 8 6 7 false 89 3 1 4 5 3 2 5 6 true 79 4 2 2 5 2 7 5 3 true 11 4 2 5 2 2 7 4 3 true 91 2 4 1 5 1 3 6 7 false 51 8 4 6 5 1 2 4 6 true 45 5 1 2 2 4 6 5 5 true 73 5 6 8 7 6 6 5 5 false 23 89 10 0 0 91 0 0 79 0 54 0 0 1 5 2 5 3 5 4 5 5 5 7 5 6 5 8 5 -4 -1 51 -4 -1 73 -4 -1 11 -4 -6 73 4 5 0 2 0 7 0 1 0 -7 2 1 1 6 1 -2 54 -4 -5 2 -3 -8 jp privado 2 57 3 4 5 4 3 4 5 4 false 89 4 5 6 4 4 5 6 5 false 33 4 6 4 3 6 7 6 7 true 60 6 7 8 7 8 9 5 7 true 70 3 5 7 8 9 7 4 2 false 91 4 5 3 6 4 6 4 3 true 80 5 6 6 3 5 6 3 2 false 12 5 6 4 7 6 4 6 4 true 13 5 7 5 4 7 4 3 7 false 14 7 6 6 4 7 5 3 7 true 57 89 0 60 0 91 0 0 33 0 70 80 0 0 0 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 -4 -1 12 -4 -1 13 -4 -3 -5 2 -1 14 -4 -3 -5 2 -2 91 -2 91 -2 80 -4 -5 8 -2 14 -2 12 -2 60 -2 89 -2 13 -2 70 -2 33 -4 -3 -2 57 -5 7 -1 14 -4 -3 -8 jp privado 3 57 1 4 5 4 3 4 5 4 false 89 4 1 6 4 4 6 6 9 false 33 4 6 1 3 6 7 6 7 true 60 6 7 8 1 8 9 5 7 true 70 9 9 9 9 1 9 9 9 false 91 9 9 9 9 9 1 9 9 false 80 5 6 6 3 5 6 1 2 true 12 5 6 4 7 6 4 6 1 true 13 1 1 1 1 9 9 1 1 true 14 7 6 6 5 7 3 4 7 true 57 0 89 70 0 33 91 0 0 0 0 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 -4 -1 12 -4 -2 12 -6 12 8 1 1 2 1 3 1 4 1 5 1 6 2 7 2 8 9 -1 12 -1 13 -6 60 1 6 3 -1 60 -4 -1 80 -4 -1 14 -4 -8
Solucions als jocs de proves privats
solucion jp privado 1 -- comienza solucion 10 89 91 23 79 54 2 10 89 91 23 51 79 54 1 73 10 89 91 23 51 79 54 0 73 10 89 91 23 51 79 54 1 73 10 89 91 23 51 79 54 10 23 51 73 79 89 91 -- acaba solucion solucion jp privado 2 -- comienza solucion 89 60 91 57 33 80 70 1 12 89 60 91 57 33 80 70 1 12 89 60 91 57 13 33 80 70 12 13 33 57 60 70 80 89 91 14 1 14 12 89 60 91 57 13 33 80 70 12 13 14 33 57 60 70 80 89 91 0 1 0 1 14 12 89 60 57 13 33 70 91 1 1 1 1 1 1 1 57 57 1 12 1 14 14 -- acaba solucion solucion jp privado 3 -- comienza solucion 57 70 91 33 89 2 12 57 70 91 33 89 1 0 2 0 57 70 91 33 89 13 2 57 70 91 33 80 89 13 0 57 70 91 33 80 89 13 -- acaba solucion
Fitxers: Associacio.java, Planeta.java, Sistema_Solar.java, prap.java
El codi te alguns errors!!
prap.java
import utilsPRAP.InOut;
public class prap{
public static void main (String args[]) throws Exception
{
InOut io = new InOut();
Planeta p = new Planeta();
Sistema_Solar s = new Sistema_Solar();
Associacio a = new Associacio();
s.llegir_sistema_solar(io);
a.llegir_associacio(io,s);
int i = 0;
i = io.readint();
for (;i != -8;)
{
switch (i)
{
case -1:
a.alta_planeta(s,io.readint(),io);
break;
case -2:
a.baixa_planeta(s,io.readint(),io);
break;
case -3:
a.ordena_creixent(io,s);
break;
case -4:
a.ordena_estructura(io);
break;
case -5:
io.write(s.millor_planeta_segons_criteri(io.readint()-1));
io.writeln();
break;
case -6:
p.modificar_criteris_planeta(io.readint(),io,s);
break;
case -7:
a.modificar_requisits_associacio(io);
break;
}
i = io.readint();
}
return;
}
}
Sistema_Solar.java
import utilsPRAP.InOut;
public class Sistema_Solar{
private static final int NUM_PLANETES = 10;
private Planeta planetes[];
public void nou_sistema_solar() throws Exception
{
int i=0;
planetes= new Planeta[NUM_PLANETES];
while (i != NUM_PLANETES)
{
planetes[i]= new Planeta();
i++;
}
}
public void llegir_sistema_solar(InOut canal) throws Exception
{
int i=0;
this.nou_sistema_solar();
while (i != NUM_PLANETES)
{
this.planetes[i].llegir_planeta(canal);
i++;
}
}
public int millor_planeta_segons_criteri(int n) throws Exception
{
int id=0;
int i = 0;
int h =0;
boolean trobat = false;
while(!trobat && i != NUM_PLANETES)
{
if (!this.planetes[i].consultar_pertany_associacio())
{
id =this.planetes[i].consultar_identificador();
h=i+1;
trobat = true;
}
else
{
i++;
}
}
if (trobat)
{
while (h < NUM_PLANETES)
{
if (!this.planetes[h].consultar_pertany_associacio())
{
if (this.planetes[h].consultar_criteri_planeta(n) > consulta_planeta(id).consultar_criteri_planeta(n))
{
id = this.planetes[h].consultar_identificador();
}
else if (this.planetes[h].consultar_criteri_planeta(n) == consulta_planeta(id).consultar_criteri_planeta(n))
{
if (this.planetes[h].consultar_identificador() < id)
{
id = this.planetes[h].consultar_identificador();
}
}
}
h++;
}
}
return id;
}
public Planeta consulta_planeta(int id) throws Exception
{
int i=0;
boolean b=false;
while(!b && i != NUM_PLANETES)
{
if (this.planetes[i].consultar_identificador()==id)
{
b=true;
}
else
{
i++;
}
}
return planetes[i];
}
public int[] consulta_planetes_associacio() throws Exception
{
int[] vector= new int[NUM_PLANETES];
int g=0;
while (g != NUM_PLANETES)
{
vector[g]=-1;
g++;
}
int i = 0;
int h=0;
while(i != NUM_PLANETES)
{
if (this.planetes[i].consultar_pertany_associacio())
{
vector[h]=this.planetes[i].consultar_identificador();
h++;
}
i++;
}
return vector;
}
}
Planeta.java
import utilsPRAP.InOut;
public class Planeta{
private static final int MAX_CRITERIS = 8;
private int identificador;
private int criteris[];
private boolean pertany_associacio;
private boolean te_aigua;
public void nou_planeta(int id) throws Exception
{
criteris = new int[MAX_CRITERIS];
int i=0;
identificador=id;
while ( i != MAX_CRITERIS)
{
criteris[i]=0;
i++;
}
pertany_associacio= false;
te_aigua= false;
}
public void llegir_planeta(InOut canal) throws Exception
{
this.nou_planeta(canal.readint());
int i = 0;
while(i != MAX_CRITERIS)
{
this.criteris[i]= canal.readint();
i++;
}
this.modifica_aigua(canal.readboolean());
}
public void modificar_criteris_planeta(int id, InOut canal, Sistema_Solar s) throws Exception
{
int i = 0;
int num = canal.readint();
while (i != num)
{
s.consulta_planeta(id).criteris[canal.readint()-1]=canal.readint();
i=i+1;
}
}
public void modifica_pertinenca(boolean b) throws Exception
{
this.pertany_associacio=b;
}
public void modifica_aigua(boolean b) throws Exception
{
this.te_aigua=b;
}
public int consultar_identificador() throws Exception
{
return identificador;
}
public int consultar_criteri_planeta(int i) throws Exception
{
return criteris[i];
}
public boolean consultar_pertany_associacio() throws Exception
{
return pertany_associacio;
}
public boolean consultar_aigua() throws Exception
{
return te_aigua;
}
}
Associacio.java
import utilsPRAP.InOut;
import tadsPRAP.Arbol;
import tadsPRAP.EmptyTreeException;
public class Associacio{
private static final int MAX_REQUISITS = 8;
private Arbol estructura;
private int requisits[];
public void nova_associacio() throws Exception
{
requisits = new int[MAX_REQUISITS];
int i=0;
estructura=null;
while(i != MAX_REQUISITS)
{
requisits[i]=0;
i++;
}
}
public void llegir_associacio(InOut canal, Sistema_Solar s) throws Exception
{
int i=0;
this.nova_associacio();
estructura = llegir_arbre_int(0, canal,s);
while(i != MAX_REQUISITS)
{
requisits[canal.readint()-1]=canal.readint();
i++;
}
}
public Arbol llegir_arbre_int(int marca, InOut canal, Sistema_Solar s) throws Exception
{
Arbol b, c;
int x = canal.readint ();
Integer wx = new Integer (x);
if (x != marca)
{
s.consulta_planeta(x).modifica_pertinenca(true);
b = llegir_arbre_int (marca, canal,s);
c = llegir_arbre_int (marca, canal,s);
b.plantar (wx, c);
}
else
{
b = new Arbol ();
b.a_nulo ();
}
return b;
}
public void alta_planeta(Sistema_Solar s, int id, InOut canal) throws Exception
{
if (comparar_requisits(s,id))
{
if (this.estructura.es_nulo())
{
Arbol aux1 = new Arbol();
Arbol aux3= new Arbol();
aux1.a_nulo();
Integer idx = new Integer(id);
aux3.plantar(idx,aux1,aux1);
this.estructura.copiar_arbol(aux3);
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(1);
}
else
{
int[] vecc = new int[20];
int f=0;
while (f < 20)
{
vecc[f]=-1;
vecc[f+1]=0;
f=f+2;
}
vecc = cerca_planeta_normal(this.estructura,s,id,vecc,0);
int pdd = menor_distancia(vecc);
if (pdd != -1)
{
this.estructura.copiar_arbol(alta_plan(this.estructura,id,pdd,s));
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(1);
}
}
}
else
{
if (s.consulta_planeta(id).consultar_aigua())
{
if (this.estructura.es_nulo())
{
canal.writeln(0);
}
else
{
int[] vec = new int[20];
int i=0;
while (i < 20)
{
vec[i]=-1;
vec[i+1]=0;
i=i+2;
}
vec = cerca_planeta_compens(this.estructura,s,id,vec,0);
int pd = menor_distancia(vec);
if (pd != -1)
{
this.estructura.copiar_arbol(alta_plan(this.estructura,id,pd,s));
s.consulta_planeta(id).modifica_pertinenca(true);
canal.writeln(2);
}
else
{
canal.writeln(0);
}
}
}
else
{
canal.writeln(0);
}
}
}
private int menor_distancia( int[] vector) throws Exception
{
int i =0;
int id=-1;
int prof =12;
while(i < 20)
{
if (vector[i] != -1)
{
if (vector[i+1] < prof)
{
id = vector[i];
prof = vector[i+1];
}
}
i=i+2;
}
return id;
}
private int[] cerca_planeta_normal(Arbol a, Sistema_Solar s, int id, int[] vector, int res) throws Exception
{
Arbol aux1, aux2;
int[] c,d;
if (a.es_nulo())
{
res =0;
}
else
{
aux1 = new Arbol();
aux2 = new Arbol();
c = new int[20];
d = new int[20];
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
c=cerca_planeta_normal(aux1,s,id, vector, res+1);
d=cerca_planeta_normal(aux2,s,id, vector, res+1);
if (aux1.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
else if (aux2.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
else if (aux1.es_nulo() && aux2.es_nulo())
{
desa(wraiz.intValue(),res, vector);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en cerca_planeta_normal");
}
}
return vector;
}
private int[] cerca_planeta_compens(Arbol a, Sistema_Solar s, int id, int[] vector, int res) throws Exception
{
Arbol aux1, aux2;
int[] c,d;
if (a.es_nulo())
{
res =0;
}
else
{
aux1 = new Arbol();
aux2 = new Arbol();
c = new int[20];
d = new int[20];
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
c=cerca_planeta_compens(aux1,s,id, vector, res+1);
d=cerca_planeta_compens(aux2,s,id, vector, res+1);
if (aux1.es_nulo() || aux2.es_nulo())
{
if (!aux1.es_nulo() || !aux2.es_nulo())
{
if ( !aux1.es_nulo())
{
Integer ali = (Integer) aux1.raiz();
if (!s.consulta_planeta(ali.intValue()).consultar_aigua())
{
if (compara_compens(s,id,ali.intValue()))
{
desa(wraiz.intValue(),res, vector);
}
}
}
else
{
Integer adi = (Integer) aux2.raiz();
if (!s.consulta_planeta(adi.intValue()).consultar_aigua())
{
if (compara_compens(s,id,adi.intValue()))
{
desa(wraiz.intValue(),res, vector);
}
}
}
}
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en cerca_planeta_compensa");
}
}
return vector;
}
private void desa(int h, int p, int[] vector) throws Exception
{
int i = 0;
boolean b= false;
while(!b && i < 20)
{
if (vector[i] == -1)
{
vector[i] = h;
vector[i+1] = p;
b=true;
}
i=i+2;
}
}
private Arbol alta_plan(Arbol a, int id, int padre, Sistema_Solar s) throws Exception
{
Arbol aux1, aux2, aux3,c,d;
aux3= new Arbol();
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
c=new Arbol();
d= new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
if (wraiz.intValue()==padre)
{
Integer idx = new Integer(id);
Arbol aux0 = new Arbol();
aux0.a_nulo();
if (aux1.es_nulo())
{
aux1.plantar(idx,aux0, aux0);
aux3.plantar(wraiz,aux1,aux2);
}
else
{
aux2.plantar(idx,aux0, aux0);
aux3.plantar(wraiz,aux1,aux2);
}
}
else
{
c=alta_plan(aux1,id,padre,s);
d=alta_plan(aux2,id,padre,s);
aux3.plantar(wraiz,c,d);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en alta_plan");
}
}
return aux3;
}
private boolean compara_compens(Sistema_Solar s, int p, int q) throws Exception
{
int i=0;
boolean b = true;
while( b && i != MAX_REQUISITS)
{
int m = s.consulta_planeta(p).consultar_criteri_planeta(i);
if (m < this.requisits[i])
{
int n = s.consulta_planeta(q).consultar_criteri_planeta(i);
if (m + n - this.requisits[i] < this.requisits[i])
{
b=false;
}
}
i++;
}
return b;
}
public void baixa_planeta(Sistema_Solar s, int id, InOut canal) throws Exception
{
if (s.consulta_planeta(id).consultar_pertany_associacio())
{
Arbol dd = new Arbol();
dd.copiar_arbol(intenta_baixa(s,this.estructura,id, canal));
this.estructura.copiar_arbol(dd);
}
else
{
canal.writeln(0);
}
}
public Arbol intenta_baixa(Sistema_Solar s,Arbol a,int id, InOut canal) throws Exception
{
Arbol aux1, aux2, aux3,c,d;
aux3= new Arbol();
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
c=new Arbol();
d= new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
Integer wraiz = (Integer) a.raiz();
if (wraiz.intValue()==id)
{
if ( aux1.es_nulo() && aux2.es_nulo())
{
a.a_nulo();
s.consulta_planeta(id).modifica_pertinenca(false);
canal.writeln(1);
}
else
{
canal.writeln(0);
aux3.plantar(wraiz,aux1,aux2);
}
}
else
{
c=intenta_baixa(s,aux1,id,canal);
d=intenta_baixa(s,aux2,id,canal);
aux3.plantar(wraiz,c,d);
}
}
catch (EmptyTreeException e)
{
System.err.println("Error en intenta_baixa");
}
}
return aux3;
}
public int[] consultar_requisits_associacio() throws Exception
{
return this.requisits;
}
public void modificar_requisits_associacio(InOut canal) throws Exception
{
int i =0;
int x = canal.readint();
while( i != x)
{
this.requisits[canal.readint()-1] = canal.readint();
i++;
}
}
public boolean comparar_requisits(Sistema_Solar s, int id) throws Exception
{
int i =0;
boolean b =false;
while (!b && i != MAX_REQUISITS)
{
if (this.requisits[i] > s.consulta_planeta(id).consultar_criteri_planeta(i))
{
b= true;
}
i++;
}
return !b;
}
public void ordena_creixent(InOut canal, Sistema_Solar s) throws Exception
{
if (!this.estructura.es_nulo())
{
int h =0;
int[] vector = new int[10];
vector=s.consulta_planetes_associacio();
qsort (vector,0,vector.length-1);
while (h!= vector.length)
{
if (vector[h] != -1)
{
canal.write(vector[h]+" ");
}
h++;
}
canal.writeln();
}
}
private void qsort (int v[], int p, int q) throws Exception
{
if (p < q)
{
int m = particio (v,p,q);
qsort (v,p,m-1);
qsort (v,m+1,q);
}
}
private int particio (int v[], int p, int q) throws Exception
{
int z = v[p];
int f = q;
int m = p+1;
while (m <= f)
{
if (v[f] < z)
{
int aux = v[f]; v[f] = v[m]; v[m] = aux;
m = m+1;
}
else
{
f = f-1;
}
}
m = f; v[p] = v[m]; v[m] = z;
return m;
}
public void ordena_estructura(InOut canal) throws Exception
{
if (!this.estructura.es_nulo())
{
escriure_arbol_int(this.estructura, canal);
canal.writeln();
}
}
public void escriure_arbol_int(Arbol a, InOut io) throws Exception
{
Arbol aux1, aux2;
if (!a.es_nulo())
{
aux1 = new Arbol();
aux2 = new Arbol();
try
{
aux1.hi(a);
aux2.hd(a);
escriure_arbol_int(aux1,io);
Integer wraiz = (Integer) a.raiz();
io.write(wraiz.intValue()+" ");
escriure_arbol_int(aux2,io);
}
catch (EmptyTreeException e)
{
System.err.println("Error en escribir_arbol");
}
}
}
}
