Inform\'atica. Primer Trabajo (25-3-1998) RECURSI\'ON PLANA Y ABSTRACCI\'ON DE DATOS Estos ejercicios pueden resolverse individualmente o en un grupo de no m\'as de 3 alumnos. Aquellos trabajos entre los que se detecte copia ser\'an penalizados. Cada grupo debe enviar por correo electr\'onico dos mensajes: [-] Uno en el que S\'OLO se debe incluir el fichero con el programa que se pide, con ``Subject'': trabajo1.scm y enviado s\'olo por uno de los componentes del grupo. Para la correcci\'on, se considerar\'a que el programa enviado es todo el mensaje, por lo que cualquier texto que no forme parte del programa deber\'a ser comentado (con puntos y comas). Antes de incluir el fichero en el mensaje comprueba que el fichero carga perfectamente en el Scheme de Merlin evaluando (load ``NOMBRE-DE-FICHERO'') donde NOMBRE-DE-FICHERO es el nombre del fichero en el que has escrito el trabajo y que vas a enviar por correo. Cualquier trabajo enviado que no cargue no se corregir\'a. [-] Otro mensaje, enviado por el MISMO componente del grupo que envi\'o el anterior, con ``Subject'' Grupo trabajo 1, en el que se especifican claramente los componentes del grupo, as\'i como cualquier otra observaci\'on que se quiera incluir. NOTA IMPORTANTE: Los mensajes deben tener el subject indicado EXACTAMENTE. Las direcciones de correo son: Si tu profesor es F\'elix Lara: felix@merlin.fie.us.es Si tu profesor es Álvaro Romero: aroji@merlin.fie.us.es Si tu profesor es Miguel Ángel Guti\'errez: naranjo@merlin.fie.us.es El trabajo ser\'a corregido usando Scheme en Merl\'in, pero por supuesto puedes realizar el trabajo en casa. Se valorar\'an no s\'olo la correcci\'on de los programas sino tambi\'en la claridad en la presentaci\'on, por lo que cada programa deber\'a estar adecuadamente comentado adem\'as de llevar a cabo, de manera correcta y eficiente, la tarea que se le pide. Los programas deber\'an ser enviados no m\'as tarde del 5 DE MAYO DE 1998. NOTA: NO INCLUIR el texto de la pr\'actica en el fichero en el que se haga el trabajo. INTRODUCCI\'ON En cierta regi\'on, de cierto planeta, pueden encontrarse unos extraños seres, que en lo sucesivo llamaremos bichos, que suelen vivir formando filas indias. Cada uno de estos seres est\'a caracterizado por su llamativo color (rojo, verde o azul) y un n\'umero de tent\'aculos que var\'ia de un individuo a otro. Su vida no suele ser muy larga (apenas unos cuantos d\'ias) y su duraci\'on est\'a determinada gen\'eticamente por la duraci\'on de la vida de sus progenitores. Resulta particularmente curiosa su forma de reproducci\'on, denominada ``reproducci\'on por contiguidad'' (recordemos que estos bichos viven dispuestos en fila india): cada par de individuos que se encuentren adyacentes en la fila, provocan el nacimiento de un nuevo individuo entre ellos. Como es de esperar las caracter\'isticas del nuevo individuo (color, n\'umero de tent\'aculos y edad m\'axima) est\'an determinadas por las de sus progenitores de acuerdo con unas leyes de herencia fijas. El objetivo de esta pr\'actica es simular (de un modo bastante rudimentario) la evoluci\'on de una poblaci\'on de bichos y escribir algunos procedimientos que nos den informaci\'on sobre la misma. Para ello describiremos un tipo abstracto de dato, con el que representaremos a los bichos, y trataremos cada poblaci\'on de bichos como una lista, que representa la fila en que estos seres se organizan. EL TIPO ABSTRACTO DE DATO Todo bicho tiene 4 caracter\'isticas: color, n\'umero de tent\'aculos, edad (expresada en d\'ias) y edad m\'axima (expresada tambi\'en en d\'ias). Un bicho muere al alcanzar su edad m\'axima. La reproducci\'on como ya hemos dicho se produce por contiguidad, de tal modo que cada d\'ia los bichos existentes dan lugar a una nueva generaci\'on. Cada bicho se reproduce todos los d\'ias, incluyendo el d\'ia siguiente a su nacimiento y el d\'ia de su muerte. Representaremos a cada bicho por una lista de 4 elementos, situados en el mismo orden en que se especifican, a saber: un s\'imbolo (rojo, verde o azul) que nos indica su color, un n\'umero entero que nos indica el n\'umero de tent\'aculos, otro n\'umero entero, que nos indica la edad actual del bicho (expresada en d\'ias) y, por \'ultimo, otro n\'umero entero, que nos indica la edad m\'axima (en d\'ias) que puede alcanzar. Los siguientes procedimientos constituir\'an los selectores y constructores de nuestro tipo abstracto de datos. En concreto tenemos: (1) Un procedimiento color que recibe como entrada un bicho (es decir, una lista como la descrita anteriormente) y devuelve como valor el color del bicho. Por ejemplo: (color '(rojo 6 2 3)) ==> rojo (2) Un procedimiento numero-tentaculos que recibe como entrada un bicho y devuelve como valor su n\'umero de tent\'aculos. Por ejemplo: (numero-tentaculos '(rojo 6 2 3)) ==> 6 (3) Un procedimiento edad que recibe como entrada un bicho y devuelve como valor su edad. Por ejemplo: (edad '(rojo 6 2 3)) ==> 2 (4) Un procedimiento edad-maxima que recibe como entrada un bicho y devuelve como valor la edad m\'axima que puede alcanzar. Por ejemplo: (edad-maxima '(rojo 6 2 3)) ==> 3 (5) Un procedimento haz-bicho con cuatro argumentos que, al recibir como entrada un s\'imbolo (que suponemos un color) y 3 n\'umeros devuelve como valor un bicho (es decir una lista de cuatro elementos) con el color, el n\'umero de tent\'aculos, la edad actual y la edad m\'axima correspondientes a los valores recibidos. Por ejemplo: (haz-bicho 'verde 4 1 2)) ==> (verde 4 1 2) (haz-bicho 'azul 5 0 3)) ==> (azul 5 0 3) A continuaci\'on, proporcionamos una definici\'on de estos procedimientos: (define color car) (define numero-tentaculos cadr) (define edad caddr) (define edad-maxima cadddr) (define haz-bicho list) NOTA IMPORTANTE: Todos los procedimientos de esta pra\'actica deber\'an definirse usando estos constructores y selectores para manejar el tipo abstracto de dato ``bicho'', independientemente de la representaci\'on elegida. De este modo, si se cambia la representaci\'on escogida, todos los procedimientos seguir\'an funcionando correctamente. POBLACIONES Una poblaci\'on de bichos se representar\'a por una lista cuyos elementos son bichos (es decir, listas de cuatro elementos). Los siguientes procedimientos nos permitir\'an simular la evoluci\'on de una poblaci\'on. Para ello deben definirse: (1) Un procedimiento reproduce que reciba como entrada dos bichos, b1 y b2, y devuelva como valor otro bicho, hijo de los dos anteriores, cuyas caracter\'isticas (color, n\'umero de tent\'aculos y edad m\'axima) se determinan del siguiente modo: [-] Si b1 y b2 tienen el mismo color, su hijo tendr\'a tambi\'en ese color, y si son de diferente color, entonces el hijo tendr\'a un color distinto al de ambos (recordemos que s\'olo son posibles tres colores), por ejemplo, si los colores son verde y rojo, el hijo ser\'a azul, si los padres son rojo y azul entonces el hijo ser\'a verde, etc. [-] El n\'umero de tent\'aculos es el m\'aximo de los n\'umeros de tent\'aculos de los padres m\'as 1, si estos tienen el mismo color, y el m\'inimo, en caso contrario. [-] La edad m\'axima del hijo se determina a partir de su n\'umero tent\'aculos y su color, de acuerdo con la siguiente tabla: _______________________________________ | | COLOR | | |_____________________| | N=Num. TENT. | azul | rojo | verde | |_______________|______|______|_______| | N <= 2 | 2 | 1 | 2 | |_______________|______|______|_______| | 3 <= N <= 6 | 5 | 3 | 4 | |_______________|______|______|_______| | 7 <= N | 3 | 3 | 3 | |_______________|______|______|_______| (reproduce '(rojo 6 2 3) '(rojo 5 2 3)) ==> (rojo 7 0 3) (reproduce '(azul 5 1 3) '(verde 1 2 5)) ==> (rojo 1 0 1) Con objeto de facilitar la definici\'on del procedimiento reproduce se definir\'an previamente los siguientes procedimientos: (1) Un procedimiento nuevo-color que reciba como entrada dos bichos y devuelva como valor el color que tendr\'ia su hijo. Por ejemplo: (nuevo-color '(rojo 6 2 3) '(rojo 5 2 3)) ==> rojo (nuevo-color '(azul 5 1 3) '(verde 1 2 5)) ==> rojo (2) Un procedimiento nuevo-numero-tentaculos que reciba como entrada dos bichos y devuelva n\'umero de tent\'aculos que tendr\'ia su hijo. Por ejemplo: (nuevo-numero-tentaculos '(rojo 6 2 3) '(rojo 5 2 3)) ==> 7 (nuevo-numero-tentaculos '(azul 5 1 3) '(verde 1 2 5)) ==> 1 (3) Un procedimiento nueva-edad-maxima que reciba como entrada dos bichos y devuelva como valor la edad m\'axima que tendr\'ia su hijo. Por ejemplo: (nueva-edad-maxima '(rojo 6 2 3) '(rojo 5 2 3)) ==> 3 (nueva-edad-maxima '(azul 5 1 3) '(verde 1 2 5)) ==> 1 (4) Un procedimiento generacion que recibe como entrada una poblaci\'on (es decir, una lista de bichos) y devuelve la poblaci\'on resultante al siguiente d\'ia. Esta poblaci\'on se obtiene del siguiente modo: en primer lugar incrementamos en 1 la edad de cada bicho, a continuaci\'on, por cada par de bichos adyacentes en la lista nace uno nuevo (cuyas caracter\'isticas vienen determinadas por el procedimiento reproduce) y se sit\'ua entre sus padres; una vez nacidos todos los posibles hijos, mueren todos los bichos cuya edad en este momento, supere su edad m\'axima. Por ejemplo: (define P1 '((rojo 6 2 3) (rojo 5 2 3) (azul 5 1 3) (verde 1 2 5))) (generacion P1) ==> ((rojo 6 3 3) (rojo 7 0 3) (rojo 5 3 3) (verde 5 0 4) (azul 5 2 3) (rojo 1 0 1) (verde 1 3 5)) (define P2 '((azul 3 5 5) (verde 1 0 2))) (generacion P2) ==> ((rojo 1 0 1) (verde 1 1 2)) (5) Un procedimiento evolucion que reciba como entrada una poblaci\'on P, y un n\'umero entero positivo n, y devuelva como valor la poblaci\'on (es decir, la lista) resultante tras el paso de n d\'ias, es decir, despu\'es de aplicar sucesivamente el procedimiento generacion n veces, comenzando con la poblaci\'on P. (define P '((verde 1 0 1) (azul 1 0 2))) (evolucion P 1) ==> ((verde 1 1 1) (rojo 1 0 1) (azul 1 1 2)) (evolucion P 2) ==> ((azul 1 0 2) (rojo 1 1 1) (verde 1 0 2) (azul 1 2 2)) (evolucion P 3) ==> ((azul 1 1 2) (verde 1 0 2) (azul 1 0 2) (verde 1 1 2) (rojo 1 0 1)) OBTENER INFORMACI\'ON Los siguientes procedimientos nos servir\'an para obtener datos acerca de la distribuci\'on de las distintas caracter\'isticas (color, n\'umero de tent\'aculos, edad y edad m\'axima) entre los individuos de la poblaci\'on. Deben definirse los siguientes procedimientos: (1) Un procedimiento lista-color que reciba como entrada un color ( rojo, verde o azul) y una poblaci\'on, y devuelva como valor la lista formada por los individuos de la poblaci\'on que tengan el color especificado. Por ejemplo: (define P3 (generacion P1)) (lista-color 'rojo P3) ==> ((rojo 6 3 3) (rojo 7 0 3) (rojo 5 3 3) (rojo 1 0 1)) (lista-color 'verde P3) ==> ((verde 5 0 4) (verde 1 3 5)) (2) Un procedimiento cuenta-colores que reciba una poblaci\'on y devuelva como valor una lista de tres n\'umeros que ser\'an, el n\'umero de individuos de la poblaci\'on que tienen el color azul, el n\'umero de individuos que tienen color rojo y el n\'umero de individuos de color verde, EN ESE ORDEN. (cuenta-colores P1) ==> (1 2 1) (cuenta-colores P3) ==> (1 4 2) (3) Un procedimiento lista-tentaculos que reciba como entrada un par punteado formado por dos n\'umeros enteros, a y b, y una poblaci\'on, y devuelva como valor la lista de los individuos cuyo n\'umero de tent\'aculos, N, verifica, a <= N <= b. Por ejemplo: (lista-tentaculos '(1 . 2) P3) ==> ((rojo 1 0 1) (verde 1 3 5)) (lista-tentaculos '(8 . 10) P3) ==> () (4) Un procedimiento lista-edades que reciba como entrada una lista de n\'umeros enteros (edades) y una poblaci\'on, y devuelva la lista formada por los individuos de la poblaci\'on cuya edad actual pertenece a la lista dada. Por ejemplo: (lista-edades '(1 2) P3) ==> ((azul 5 2 3)) (lista-edades '(0) P3) ==> ((rojo 7 0 3) (verde 5 0 4) (rojo 1 0 1)) (5) Un procedimiento combinacion que reciba como entrada un s\'imbolo (que suponemos es un color), un n\'umero entero positivo y una poblaci\'on, y devuelva como valor el n\'umero de individuos de la poblaci\'on que tienen ese color y ese n\'umero de tent\'aculos. Por ejemplo: (combinacion 'rojo 4 P1) ==> 0 (combinacion 'verde 1 P1) ==> 1 (6) Un procedimiento lista-ancianos que, dada una poblaci\'on, nos devuelva la lista de los individuos cuya edad coincide con su edad m\'axima. Por ejemplo: (lista-ancianos P1) ==> () (lista-ancianos P3) ==> ((rojo 6 3 3) (rojo 5 3 3)) (7) Un procedimiento medias que reciba como entrada una poblaci\'on y devuelva un par punteado, formado por la media del n\'umero de tent\'aculos y la media de las edades de los bichos que integran la poblaci\'on, EN ESE ORDEN. Por ejemplo: (medias P1) ==> (4.25 . 1.75) (medias P3) ==> (4.28571428571429 . 1.57142857142857)