Programación: elementos

Informática. Matrices dispersas. Vectores. Especificaciones

  • Enviado por: Alberto García
  • Idioma: castellano
  • País: España España
  • 2 páginas
publicidad
publicidad

Elementos de Programación 7-9-01

Problema 1. Matrices más Dispersas (3 puntos)

Te han encargado la realización de un TAD para trabajar con matrices de nº reales. La matriz máxima posible tiene maxf filas y maxc columnas. En los problemas donde vas a usar este TAD, la mayoría de los valores son 0. Por tanto, si usamos un vector de dos dimensiones, estaremos desperdiciando mucha memoria.

Por este motivo, te han dicho que implementes la matriz como un vector de 1 a maxf filas, donde cada elemento del vector es una lista cuyos nodos tienen dos campos de información: la columna correspondiente, y el valor, siempre que no sea 0. Los valores que son 0 no aparecen representados explícitamente en la estructura de datos.

1 En este dibujo está representada

parcialmente, la estructura indicada (puede

2 faltar más información para completarla y

conseguir las complejidades indicadas)

3

4

.

. Esto sería una matriz en la que todos los

elementos son 0 excepto el (2,5), que vale

. 3.7, el (4,1) que vale 5.1, y el (4,8), que

maxf vale 2.2

TAD

Matriz es Crear, Filas, Columnas, PonerValor, ObtenerValor, Fila.

Operaciones

Crear (nf,nc: Entero) retorna Matriz

efecto Crea una matriz de nf filas por nc columnas con todos los valores

nulos.

Filas (M:Matriz) retorna Entero

efecto Devuelve el nº de filas que tiene la matriz M. Complejidad O(1).

Columnas (M:Matriz) retorna Entero

efecto Devuelve el nº de columnas que tiene la matriz M. Complejidad O(1).

PonerValor (M:Matriz; f,c:Entero; v:Real)

modifica Matriz

efecto Pone en la posición (f,c) de la matriz M el valor v. Si ya existiera un

valor en esa posición distinto de 0, se sustituye por el nuevo. (Podemos suponer que v nunca va a ser 0)

ObtenerValor (M:Matriz; f,c: Entero)

retorna Real

efecto Devuelve el valor real de la matriz M que ocupa la posición (f,c);

1. Definir el tipo Matriz

2. Implementa las operaciones del TAD.

3. Explica, sin implementar, cómo se modifiacaría la operación PonerValor si el parámetro v pudiera tener valor 0.

Problema 2. Urbanización (4 puntos)

Actualmente se está construyendo una nueva urbanización en una zona residencial de Cáceres, por lo que se ha decidido que la comunidad de vecinos de la urbanización mantenga información de los propietarios de las parcelas compradas, teniendo en cuenta que habrá un máximo de 125 parcelas en la urbanización.

Para manejar la información referente a una parcela (nombre del propietario, nº de habitaciones de la casa, si tiene o no piscina) se usará un objeto que tiene la siguiente descripción (que suponemos totalmente implementado):

Parcela= Object

Procedure Crear (prop:string; habit:byte; pisc:boolean);

Function Obtener_propietario:string;

Function Obtener_habitaciones: byte;

Function Obtener_si_piscina: boolean;

private

propietario: string;

n_habitaciones: integer;

piscina: boolean;

end;

Para llevar la gestión de la comunidad, crearemos un TAD que nos facilite esta tarea. Este TAD deberá implementarse como un nuevo OBJETO y utilizar el anterior objeto Parcela. La especificación del TAD es la siguiente:

TAD

Urbanización es Crear, Añadir, Total, Buscar, ConPiscina

Operaciones

Crear retorna Urbanización

efecto Inicializa la estructura.

Añadir (U:Urbanización; N:cadena; nhabit:entero; pisc:booleano)

modifica Urbanización

efecto Añade ordenadamente,según el nombre del propietario N,un nuevo

habitante a la urbanización, cuya casa tiene nhabit habitaciones y pisc indica di tiene o no piscina.

Total (U:Urbanización)

retorna Entero

efecto Devuelve el nº de parcelas ocupadas que hay en la urbanización

actualmente. La complejidad de esta operación debe ser constante.

Buscar (U:Urbanización; Hab: entero; pisc: boolean)

retorna Cadena

efecto Devuelve el nombre del primer propietario que encontremos que

posee una casa con las especificaciones de Hab habitaciones y con

o sin piscina según indique el parámetro pisc.

ConPiscina (U:Urbanización)

retorna Entero

efecto Devuelve el nº de casas que tienen piscina.

Nota: Para poder aprobar el exámen es necesario obtener una nota mayor o igual a 6 en el test y tener en cada ejercicio 4 puntos cómo mínimo (Cada ejercicio se puntúa sobre 10).

3.7

5

?

2.2

8

5.1

1