Ejercicio obligatorio 3
Fecha de entrega: Lunes 2 de junio
Introducción
Racionales
Queremos representar un TDA número racional, tal que pueda almacenar una fracción.
Se propone la siguiente representación con su correspondiente invariante:
struct racional {
// Representa una fracción mixta de la forma (-1)^s * (n / d).
// s es el signo, n el numerador y d el denominador.
// Invariante de representación:
// *) n y d diferentes de NULL.
// *) s será false o true según el número sea positivo o negativo respetivamente.
// *) La fracción es irreducible, es decir n y d son coprimos.
// *) d >= 1 (si n != 0).
// *) Si n == 0 => d == 1 && s == false.
bool s;
entero_t *n, *d;
};
Enteros
Se tiene implementado el TDA entero_t. Del mismo tenemos dos implementaciones
alternativas. La primera es tu implementación del EJ2. La segunda se provee en
este mismo enunciado y está basada en la siguiente representación interna:
struct entero {
uint64_t e;
};
La interfaz de este TDA es la misma que la del TDA del EJ2 con la siguiente
salvedad: Se actualizó la firma de la primitiva de división para ser
consistente con las demás funciones, la operación se aplica sobre el primer
operando. Además el parámetro resto ahora es optativo, si el mismo vale
NULL no se devuelve el resto. Y, finalmente, se agregaron dos constructores,
uno que devuelve el entero 0 y otro que devuelve el entero 1.
Si tenés el EJ2 funcionando implementar estos dos cambios en la firma deberían ser triviales. Ambas implementaciones deberían ser intercambiables.
Además se agregó una primitiva entero_multiplicar() que multiplica dos
números.
Se provee una (mala) implementación de esta primitiva para el TDA del EJ2:
bool entero_multiplicar(entero_t *a, const entero_t *b) {
entero_t *aa = _crear(1);
if(aa == NULL) return false;
entero_t *aux = _crear(a->n + b->n + 1);
if(aux == NULL) {
entero_destruir(aa);
return false;
}
// Swapeamos el contenido de a con aa, vamos a guardar el resultado en a
uint32_t *swap = aa->d;
aa->d = a->d;
a->d = swap;
aa->n = a->n;
a->n = 1;
for(size_t i = 0; i < b->n; i++) {
for(size_t j = 0; j < aa->n; j++) {
uint64_t m = (uint64_t)aa->d[j] * b->d[i];
aux->d[j] = m;
aux->d[j + 1] = m >> 32;
entero_sumar(a, aux);
aux->d[j] = 0;
}
aux->d[aa->n] = 0;
// INSISTO con lo que dije en dividir:
// Podríamos tener una función para desplazar elementos en el arreglo.
for(size_t j = 0; j < 32; j++)
entero_desplazar_izquierda(aa);
}
entero_destruir(aa);
entero_destruir(aux);
return true;
}
Es decir, tanto si terminaste la implementación del EJ2 como si no tenemos
completa una implementación del TDA entero_t disponible para usar.
Trabajo
Biblioteca entero_t
Se pide modlularizar el TDA entero_t como una biblioteca separando su .c de
su .h.
En el .h es indistinto qué implementación de la biblioteca utilicemos.
Auxiliares
Previo a implementar las primitivas, se alienta a implementar funciones auxiliares para manejar la normalización de los números y utilizarlas para ajustar el resultado de las operaciones a la invariante deseada.
Al respecto de la irreductibilidad, la misma se obtiene dividiendo numerador y denominador por el máximo común divisor (MCD). El mismo se puede calcular mediante el algoritmo de Euclides que se encuentra en el ejercicio número 30 de la guía de introducción al lenguaje C.
Si bien no es necesario para determinadas operaciones puede utilizarse el mínimo común múltiplo (mcm), el mismo puede calcularse en base al MCD como:
Y, la aclaración que estabas esperando, la implementación que tenemos de
entero_t implica crear muchos TDAs para realizar las operaciones. Para esta
implementación no es necesario verificar la creación de cada objeto que haya
que construir. Se asume que siempre hay memoria.
Hecha esta introducción se pide implementar las siguientes primitivas del racional:
Construcción
Constructor:
racional_t *racional_crear(bool es_negativo, entero_t *numerador, entero_t *denominador);.
Crea un racional_t en base al signo, numerador y denominador dados. El
denominador podría valer NULL, en ese caso se considera que la fracción se
crea desde un numerador entero, es decir, el denominador se debe
inicializar en uno.
Nota
Notar que esta primitiva no le impone ninguna precondición a Bárbara, salvo
que numerador sea diferente a NULL y que si se pasa un entero_t el
mismo esté inicializado.
Destructor:
void racional_destruir(racional_t *q);. Libera la memoria asociada.
Getters
const entero_t *racional_numerador(const racional_t *q); devuelve el
numerador de q.
const entero_t *racional_denominador(const racional_t *q); devuelve el
denominador de q.
bool racional_es_negativo(const racional_t *q); devuelve el signo de q.
Utilidades
Impresión:
bool racional_imprimir(const racional_t *q); imprime el racional por stdout.
El formato será +n/d o -n/d según corresponda con el signo.
Operaciones
Suma:
racional_t *racional_sumar(const racional_t *q, const racional_t *r);
devuelve la suma de ambos números.
Resta:
racional_t *racional_restar(const racional_t *q, const racional_t *r);
devuelve la resta de ambos números. (Si ya tenés implementada la suma, esta
función deberías poder implementarla en un par de líneas.)
Producto:
racional_t *racional_multiplicar(const racional_t *q, const racional_t *r);
devuelve el producto de los dos racionales.
División:
racional_t *racional_dividir(const racional_t *q, const racional_t *r);
devuelve la división de los dos racionales. (Misma aclaración que con la resta.)
Proyecto
Además de la implementación del entero te proveemos de un main.c que realiza
pruebas sobre las operaciones de la biblioteca de racionales. La misma prueba
las operaciones y los resultados, no prueba todas las funciones (como las de
impresión, comparación, etc.)
Se deberá hacer un proyecto tal que el main.c provisto testee a los módulos
del racional y el entero.
En cuantro a las pruebas observar que en los casos de prueba si el denominador
es cero el racional se construye con un NULL, es decir, es un entero.
Deberá entregarse los fuentes del TDA entero_t y racional_t con sus
respectivos archivos de encabezados y con el main.c dado. Además el Makefile
necesario para compilar la aplicación.
Nota
Los archivos con la implementación del TDA entero y el main con las pruebas
pueden descargarse en archivos_20251_ej3.tar.gz
Entrega
El proyecto debe:
Compilar correctamente con los flags:
-Wall -Werror -std=c99 -pedantic
pasar Valgrind correctamente,
La entrega se realiza a través del sistema de entregas.
El ejercicio es de entrega individual.