// rational.h (c) 2007 adolfo@di-mare.com
/** \file rational.h
\brief Declara el tipo \c "rational".
- La clase \c rational implementa las operaciones aritméticas
principales para números rationales.
- [1/3] == [2/6] == ... [9/27] == ...
- [1/3] * [2/6] / [3/9] - [9/27]
- Permite usar racionales en cualquier sitio en donde se puedan
usar valores numéricos.
\author Adolfo Di Mare
\date 2005
*/
#ifndef rational_h
#define rational_h ///< Evita la inclusión múltiple
/// Definido por la biblioteca C++ estándar
namespace std { }
#include
using namespace std;
/** La clase \c rational implementa las operaciones aritméticas
principales para números rationales.
- [1/3] == [2/6] == ... [9/27] == ...
- [1/3] * [2/6] / [3/9] - [9/27]
*/
template
class rational {
private:
INT m_num; ///< Numerador
INT m_den; ///< Denominador
void simplify();
public:
/// Constructor de vector.
/// \see test_rational::test_constructor().
rational() : m_num(INT(0)), m_den(INT(1)) { }
rational(INT num) : m_num(num), m_den(INT(1)) { } ///< Constructor a partir de un valor entero.
rational(INT num, INT den)
: m_num(num), m_den(den) { simplify(); } ///< Constructor a partir de un valor quedbrado
/// Constructor de copia
rational(const rational& o) { m_num = o.m_num; m_den = o.m_den; }
~rational() { } ///< Destructor
void set( const INT& n=INT(0), const INT& d=INT(1) ); // Le cambia el valor a \c "*this"
/** Acceso al numerador.
\dontinclude test_rational.cpp
\skipline test::num_den()
\until }}
\see test_rational::test_num_den()
*/
const INT& num() const { return m_num; }
/// Acceso al denomirador (siempre >0).
const INT& den() const { return m_den; }
// void setNum(const INT& n) { m_num=n; simplify(); } // FEO
// void setDen(const INT& d) { m_den= ( d!=0 ? d : m_den) ; simplify(); } // FEO
rational& operator= (const rational&); // Asignación (copia)
rational& operator= (INT);
rational& swap ( rational& );
rational& operator+=( const rational& );
rational& operator-=( const rational& );
rational& operator*=( const rational& );
rational& operator/=( const rational& );
rational operator-() const; // menos unario
// uso NUM para no caerle encima ("shadow") a INT que es el tipo de la plantilla
template friend rational operator+( const rational&, const rational& );
template friend rational operator-( const rational&, const rational& );
template friend rational operator*( const rational&, const rational& );
template friend rational operator/( const rational&, const rational& );
template friend bool operator==( const rational&, const rational& );
template friend bool operator<( const rational&, const rational& );
template friend bool operator!=( const rational&, const rational& );
template friend bool operator<=( const rational&, const rational& );
template friend bool operator>=( const rational&, const rational& );
template friend bool operator>( const rational&, const rational& );
template friend rational& operator++( rational & r ); // ++r
template friend rational operator++( rational & r , int ); // r++
template friend rational& operator--( rational & r );
template friend rational operator--( rational & r , int );
template friend ostream& operator<< (ostream &, const rational& );
template friend istream& operator>> (istream &, rational& );
rational& fromString (const char* nStr);
template friend double real (const rational& ); // Conversión a real
template friend long integer(const rational& ); // Conversión a entero
template friend bool check_ok( const rational& r ); // Ok()
// excluidos porque producen ambigüedad con operadores aritméticos
// template operator double () { return double(m_num) / double(m_den); }
// template operator NUM () { return m_num / m_den ; }
template friend class test_rational; ///< Datos de prueba para la clase.
}; // rational
template
NUM mcd(NUM x, NUM y); // Calcula el Máximo Común Divisor
/// Sinónimo de \c mcd(x,y).
template
inline INT gcd( const INT& x, const INT& y ) { return mcd(x,y); }
/** Cambia el valor del número rational a \c "n/d".
\pre d != 0
.
\dontinclude test_rational.cpp
\skipline test::set()
\until }}
\see test_rational::test_set()
*/
template
inline void rational::set( const INT& n, const INT& d ) {
m_num = n;
#ifdef NDEBUG
m_den = d;
#else
if ( d==INT(0) ) {
m_den = INT(1);
}
else {
m_den = d;
}
#endif
simplify();
}
/** Copia desde \c "o".
- El valor anterior de \c "*this" se pierde.
\par Complejidad:
O( \c 1 )
\returns *this
\see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
\dontinclude test_rational.cpp
\skipline test::op_equal()
\until }}
\see test_rational::test_op_equal()
*/
template
inline rational& rational::operator=( const rational& o ) {
m_num = o.m_num,
m_den = o.m_den;
// sobra invocar a "simplify()" pues "o" ya está simplificado
return *this;
}
/** Intercambia los valores de \c "*this" y \c "o".
\par Complejidad:
O( \c 1 )
\returns *this
\see http://www.di-mare.com/adolfo/binder/c04.htm#sc08
\dontinclude test_rational.cpp
\skipline test::swap()
\until }}
\see test_rational::test_swap()
*/
template
inline rational& rational::swap( rational& o ) {
#if 1
rational tmp = o;
o = *this; // o.operator=( *this );
*this = tmp;
#else
// Esto NO funciona para objetos, métodos virtuales, etc.
char tmp[ sizeof( *this ) ];
memcpy( tmp, & o, sizeof( *this ) ); // tmp = o;
memcpy( & o, this, sizeof( *this ) ); // o = *this;
memcpy( this, tmp, sizeof( *this ) ); // *this = tmp;
// Esto violenta la integridad del Rep
#endif
return *this;
}
/** Asignación desde un \c "INT".
\dontinclude test_rational.cpp
\skipline test::op_equal()
\until }}
\see test_rational::test_op_equal()
*/
template
inline rational& rational::operator= ( INT entero ) {
m_num = entero;
m_den = 1;
return *this;
}
/** Multiplica \c "*this" por \c "num".
\dontinclude test_rational.cpp
\skipline test::op_mult_equal()
\until }}
\see test_rational::test_op_mult_equal()
*/
template
inline rational& rational::operator*=( const rational& num ) {
m_num *= num.m_num;
m_den *= num.m_den;
simplify();
return *this;
}
/** Divide \c "*this" por el valor de \c "num".
\pre (num != 0)
\dontinclude test_rational.cpp
\skipline test::op_mult_equal()
\until }}
\see test_rational::test_op_mult_equal()
*/
template
inline rational& rational::operator/=( const rational& num ) {
m_num *= num.m_den;
m_den *= num.m_num;
simplify();
return *this;
}
/** \c "-x".
- Menos unario.
- Calcula y retorna el valor \c "-x".
\dontinclude test_rational.cpp
\skipline test::op_minus()
\until }}
\see test_rational::test_op_minus()
*/
template
inline rational rational::operator-() const {
rational tmp = (*this); // tmp.rational( *this );
tmp.m_num = - tmp.m_num;
return tmp;
}
/** ¿ x == y ?.
\dontinclude test_rational.cpp
\skipline test::op_comp()
\until }}
\see test_rational::test_op_comp()
*/
template
inline bool operator==( const rational &x, const rational &y ) {
return (x.m_num == y.m_num) && (x.m_den == y.m_den);
/* Nota:
Como los números racionales siempre están simplificados, no puede
ocurrir que [1/1] está almacenado como [3/3] y en consecuencia
basta comparar los valores campo por campo para determinar si se
da o no la igualdad.
*/
}
/// ¿ x < y ?
template
inline bool operator<( const rational &x, const rational &y ) {
return (x.m_num * y.m_den) < (x.m_den * y.m_num);
/* Nota:
Una desigualdad de fracciones se preserva siempre que se
multiplique a ambos lados por un número positivo. Por eso:
[a/b] < [c/d] <==>
(b*d) * [a/b] < [c/d] * (b*d) <==>
(b/b) * (d*a) < (b*c) * (d/d) <==>
(d*a) < (b*c)
[a/b] > [c/d] <==> [(b*d)*a/b] > [(b*d)*c/d] <==> [d*a] > [b*c]
Debido a que el denominador siempre es un número positivo, el
trabajo de comparar 2 racionales se puede lograr haciendo 2
multiplicaciones de números enteros, en lugar de convertirlos
a punto flotante para hacer la división, que es hasta un orden
de magnitud más lento.
*/
// return double(x.m_num) / double(x.m_den) < double(y.m_num) / double(y.m_den);
}
/// ¿ x > y ?
template
inline bool operator>( const rational &x, const rational &y ) {
return (y < x);
}
/// ¿ x != y ?
template
inline bool operator!=( const rational& x, const rational& y ) {
return !(x == y);
}
/// ¿ x <= y ?
template
inline bool operator<=( const rational& x, const rational& y ) {
return !(y < x);
}
/// ¿ x >= y ?
template
inline bool operator>=( const rational& x, const rational& y ) {
return !(x < y);
}
/// Convertidor a punto flotante.
template
inline double real(const rational& num) {
return double (num.m_num) / double (num.m_den);
}
/// Convertidor a punto fijo.
template
inline long integer(const rational& num) {
return long ( num.m_num / num.m_den );
}
#if 0
/// Convertidor a punto fijo
template
inline rational::operator NUM() {
return NUM (m_num / m_den);
}
#endif
#include
#include // isdigit()
/** Verifica la invariante de la clase \c rational.
\par Rep Modelo de la clase:
\code
+---+
| 3 | <== m_num == numerador del número racional
+---+
|134| <== m_den == denominador del número racional
+---+
\endcode
- http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep
\remark
Libera al programador de implementar el método \c Ok()
- http://www.di-mare.com/adolfo/binder/c04.htm#sc11
\dontinclude test_rational.cpp
\skipline test::check_ok()
\until }}
\see test_rational::test_check_ok()
*/
template
bool check_ok( const rational& r ) {
if ( &r != 0 ) {
// Ok
}
else {
/// - Invariante: ningún objeto puede estar almacenado en la posición nula.
return false;
}
if ( r.m_den > 0 ) {
// Ok
}
else {
/// - Invariante: el denominador debe ser un número positivo.
return false;
}
if (r.m_num == 0) {
if ( r.m_den == 1 ) {
/// - Invariante: el cero debe representarse con denominador igual a "1".
return true;
}
else {
return false;
}
}
if ( mcd(r.m_num, r.m_den) == 1 ) {
// Ok
}
else {
/// - Invariante: el numerador y el denominador deben ser primos relativos.
return false;
}
return true;
}
/** Verifica la invariante de la clase \c rational.
\remark
Esta implementación nos se le mete al Rep
(casi siempre no es posible implementar una función como ésta).
- http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep
\remark
Libera al programador de implementar el método \c Ok()
- http://www.di-mare.com/adolfo/binder/c04.htm#sc11
*/
template
bool check_ok_no_Rep( const rational& r ) {
if ( ! (&r != 0) ) {
/// - Invariante: ningún objeto puede estar almacenado en la posición nula.
return false;
}
if ( ! (r.den() > 0) ) {
/// - Invariante: el denominador debe ser un número positivo.
return false;
}
if (r.num() == 0) {
if ( r.den() == 1 ) {
/// - Invariante: el cero debe representarse con denominador igual a "1".
return true;
}
else {
return false;
}
}
if ( ! ( mcd(r.num(), r.den()) == 1 ) ) {
/// - Invariante: el numerador y el denominador deben ser primos relativos.
return false;
}
return true;
}
/** Calcula el Máximo Común Divisor de los números \c "x" y \c "y".
- mcd(x,y) >= 1
siempre.
- MCD <==> GCD: Greatest Common Divisor .
\pre
(y != 0)
\remark
Se usa el algoritmo de Euclides para hacer el cálculo.
\par Ejemplo:
\code
2*3*5 == mcd( 2*2*2*2 * 3*3 * 5*5, 2*3*5 )
30 == mcd( -3600, -30 )
\endcode
\dontinclude test_rational.cpp
\skipline test::mcd()
\until }}
\see test_rational::test_mcd()
*/
template
NUM mcd(NUM x, NUM y) {
NUM g = (x < 0 ? -x : x); // trabaja con valores positivos
NUM r = (y < 0 ? -y : y); // "r" es el resto
NUM temp;
do {
temp = r;
r = g % r;
g = temp;
} while (NUM(0) != r);
return g;
}
/** Simplifica el numerador y el denomidador.
- Transforma el número rational de manera que el numerador y el
denominador sean primos relativos, asegurando además que el
denominador es siempre positivo.
- Si (m_num==0) ==> (m_den==1)
.
- Simplifica la fracción para que \c m_num y \c m_den sean números
primos relativos ie, mcd(m_num,m_den) == 1
.
- Asegura que \c m_den sea un número positivo.
- Restaura la invariante de la clase \c rational.
\dontinclude test_rational.cpp
\skipline test::simplify()
\until }}
\see test_rational::test_simplify()
*/
template
void rational::simplify() {
if (m_num == 0) {
m_den = 1;
return;
}
NUM divisor = mcd(m_num, m_den);
if (divisor > 1) { // ==> (divisor != 0)
m_num /= divisor;
m_den /= divisor;
}
if (m_den < 0) {
m_num = -m_num;
m_den = -m_den;
}
}
/** Le suma a \c "*this" el valor de \c "otro".
\dontinclude test_rational.cpp
\skipline test::op_add_equal()
\until }}
\see test_rational::test_op_add_equal()
*/
template
rational& rational::operator+=( const rational& otro ) {
m_num = m_num * otro.m_den + m_den * otro.m_num;
m_den *= otro.m_den;
simplify();
return *this;
}
/** Le resta a \c "*this" el valor de \c "otro".
\dontinclude test_rational.cpp
\skipline test::op_add_equal()
\until }}
\see test_rational::test_op_add_equal()
*/
template
rational& rational::operator-=( const rational& otro ) {
INT oldm_den = m_den;
INT oldm_num = m_num;
INT d = otro.m_den;
INT n = otro.m_num;
m_den *= d;
m_num = oldm_num * d - oldm_den * n;
simplify();
return *this;
}
/** Graba el valor de \c "r" en el flujo \c "COUT".
- Graba el valor en el formato [num/den].
- En particular, este es el operador que se invoca
cuando se usa, por ejemplo, este tipo de instrucción:
\code
cout << r << q;
\endcode
\dontinclude test_rational.cpp
\skipline test::op_out()
\until }}
\see test_rational::test_op_out()
*/
template
ostream& operator<<( ostream &COUT, const rational& r ) {
if ( r.m_den == 1 ) { // no hay parte fraccional
return COUT << "[" << r.m_num << "]" ;
} else {
return COUT << "[" << r.m_num << "/" << r.m_den << "]" ;
}
}
/** Lee del flujo de texto \c "CIN" el valor de \c "r".
\pre
El número rational debe haber sido escrito usando
el formato "[r/den]", aunque es permisible usar
algunos blancos.
- Se termina de leer el valor sólo cuando encuentra \c "]".
- [ -+-+-+-+- 4 / -- -+ -- 32 ]
se lee como
[1/8]
\dontinclude test_rational.cpp
\skipline test::op_in()
\until }}
\see test_rational::test_op_in()
*/
template
istream& operator>>( istream &CIN, rational& r ) {
char ch; // valor leido, letra por letra, de "CIN"
const NUM DIEZ = 10;
bool es_positivo = true; // manejo de los signos + y -
// se brinca todo hasta el primer dígito
do {
CIN >> ch;
if (ch == '-') { // cambia de signo
es_positivo = !es_positivo;
}
} while (!isdigit(ch));
// se traga el numerador
r.m_num = 0;
while (isdigit(ch)) { // convierte a GranNum: izq --> der
r.m_num = DIEZ * r.m_num + (ch-'0');
CIN >> ch;
}
// se brinca los blancos después del numerador
while (isspace(ch)) {
CIN >> ch;
}
if (ch ==']') { // es un número entero
r.m_den = 1;
}
else {
do { // se brinca todo hasta el denominador
CIN >> ch;
if (ch == '-') {
es_positivo = !es_positivo;
}
} while (!isdigit(ch));
// se traga el denominador
r.m_den = 0;
while (isdigit(ch)) {
r.m_den = DIEZ * r.m_den + (ch-'0');
CIN >> ch;
}
// El programa se duerme si en el flujo de entrada
// NO aparece el caracter delimitador final "]",
// pues la lectura termina hasta encontrar el "]".
while (ch != ']') {
CIN >> ch;
}
} // corrección: Andrés Arias
// le cambia el signo, si hace falta
if (! es_positivo) {
r.m_num = -r.m_num;
}
#ifndef NDEBUG
if ( r.m_den == NUM(0) ) {
r.m_den = 1;
}
#endif
r.simplify();
return CIN;
/*
no detecta errores...
[1/0] lo lee y no se queja
[ !#!#!$#@! 3/ aaaa 4 jajaja ] lo lee como [3/4]
... pero no se supone que el usuario cometa errores...
*/
}
/** Establece el varlor de \c "*this" a partir de la hilera \c "nStr".
\pre \c "nStr" debe estar escrita en el formato "[num/den]".
\dontinclude test_rational.cpp
\skipline test::fromString()
\until }}
\see test_rational::test_fromString()
*/
template
rational& rational::fromString (const char* nStr) {
char ch; // valor obtenido, caracter por caracter, de "nStr"
const NUM DIEZ = NUM(10);
bool es_positivo = true; // manejo de los signos + y -
// se brinca todo hasta el primer dígito
do {
ch = *nStr; nStr++;
if (ch == '-') { // cambia de signo
es_positivo = !es_positivo;
}
} while (!isdigit(ch));
// se traga el numerador
NUM num = NUM(0);
while (isdigit(ch)) { // convierte a : izq --> der
num = DIEZ * num + NUM(ch-'0');
ch = *nStr; nStr++;
}
// se brinca los blancos después del numerador
while (isspace(ch)) {
ch = *nStr; nStr++;
}
NUM den;
if (ch ==']') { // es un número entero
den = NUM(1);
}
else {
do { // se brinca todo hasta el denominador
ch = *nStr; nStr++;
if (ch == '-') {
es_positivo = !es_positivo;
}
} while (!isdigit(ch));
// se traga el denominador
den = NUM(0);
while (isdigit(ch)) {
den = DIEZ * den + NUM(ch-'0');
ch = *nStr; nStr++;
}
// Ya no importa si aparece o no el ']' del final del número
}
// le cambia el signo, si hace falta
if (! es_positivo) {
num = -num;
}
set( num, den );
return *this;
}
/** \c "x+y".
- Calcula y retorna la suma \c "x+y".
\dontinclude test_rational.cpp
\skipline test::op_add()
\until }}
\see test_rational::test_op_add()
*/
template
rational operator + (const rational &x, const rational &y) {
NUM res_num, res_den;
res_den = x.m_den * y.m_den;
res_num = x.m_num * y.m_den + x.m_den * y.m_num;
return rational(res_num, res_den);
}
/** \c "x-y".
- Calcula y retorna la resta \c "x-y".
\dontinclude test_rational.cpp
\skipline test::op_add()
\until }}
\see test_rational::test_op_add()
*/
template
rational operator-( const rational &x, const rational &y ) {
NUM res_num, res_den;
res_den = x.m_den * y.m_den;
res_num = x.m_num * y.m_den - x.m_den * y.m_num;
return rational(res_num, res_den);
}
/** \c "x*y".
- Calcula y retorna la multiplicación \c "x*y".
\dontinclude test_rational.cpp
\skipline test::op_mult()
\until }}
\see test_rational::test_op_mult()
*/
template
rational operator*( const rational &x, const rational &y ) {
NUM res_num, res_den;
res_num = x.m_num * y.m_num;
res_den = x.m_den * y.m_den;
return rational(res_num, res_den);
}
/** \c "x/y".
- Calcula y retorna la división \c "x/y".
\pre y != 0
\dontinclude test_rational.cpp
\skipline test::op_mult()
\until }}
\see test_rational::test_op_mult()
*/
template
rational operator/( const rational &x, const rational &y ) {
NUM res_num, res_den;
#ifdef NDEBUG
res_num = x.m_num * y.m_den;
res_den = x.m_den * y.m_num;
return rational(res_num, res_den);
#else
if (NUM(0) != y.m_num) {
res_num = x.m_num * y.m_den;
res_den = x.m_den * y.m_num;
return rational(res_num, res_den);
}
else {
return rational(NUM(0),NUM(1));
}
#endif
}
/** \c ++r.
\dontinclude test_rational.cpp
\skipline test::op_cpp()
\until }}
\see test_rational::test_op_cpp()
*/
template
inline rational& operator++( rational & r ) {
r.m_num += r.m_den;
return r;
}
/// \c r++.
template
inline rational operator++( rational & r , int ) {
rational tmp = r;
r.m_num += r.m_den;
return tmp;
}
/** \c --r.
\dontinclude test_rational.cpp
\skipline test::op_cpp()
\until }}
\see test_rational::test_op_cpp()
*/
template
inline rational& operator--( rational & r ) {
r.m_num -= r.m_den;
return r;
}
/// \c r--.
template
inline rational operator--( rational & r , int ) {
rational tmp = r;
r.m_num -= r.m_den;
return tmp;
}
#endif // rational_h
// EOF: rational.h