code. compile. run. debug. share.
#include "fraction.h"
#include <iostream>
#include <set>
#include <map>
using Value = shk_fraction::Fraction;
using Numbers = std::multiset<Value>;
using Splited = std::pair<Numbers, Numbers>;
using SplitedList = std::set<Splited>;
using Results = std::set<Value>;
SplitedList GenerateSplit(const Numbers& lst) {
SplitedList ret;
using LL = uintmax_t;
LL max_i = (LL)1 << lst.size() - 2;
LL min_i = 1;
for (LL i = min_i; i <= max_i; ++i) {
auto j = i;
Splited splited;
for (const auto& el : lst) {
if (j%2) {
splited.first.insert(el);
} else {
splited.second.insert(el);
}
j >>= 1;
}
ret.insert(std::move(splited));
}
return ret;
}
Results Product(const Results& lhs, const Results& rhs) {
Results ret;
for (const auto& l : lhs) {
for (const auto& r : rhs) {
for (auto s : {-1, 1}) {
ret.merge(Results{s*(l+r), s*(l-r), s*l*r});
if (r != 0) {
ret.insert(s*l/r);
}
}
}
}
return ret;
}
Results MakeResultsImpl(const Numbers& lst);
Results MakeResults(const Numbers& lst) {
static std::map<Numbers, Results> cache;
if (cache.count(lst) == 1) {
return cache[lst];
}
auto ret = MakeResultsImpl(lst);
cache[lst] = ret;
return ret;
}
Results MakeResultsImpl(const Numbers& lst) {
Results ret;
if (lst.size() == 0) {
return ret;
}
if (lst.size() == 1) {
ret.insert(*lst.begin());
return ret;
}
for (const auto& [left, right] : GenerateSplit(lst)) {
ret.merge(
Product(MakeResults(left), MakeResults(right))
);
}
return ret;
}
int main()
{
Numbers ticket = {1, 8, 9, 0, 6, 0};
for (const auto& el : MakeResults(ticket)) {
std::cout << el << "\n";
}
return 0;
}
/**********************************************************************
Project: C++ Fractional Arithmetic Library with Overflow Checking
Language: C++ 2007
Author: Saied H. Khayat
Date: March 2012
URL: https://github.com/saiedhk
Copyright Notice: Free use of this library is permitted under the
guidelines and in accordance with the MIT License (MIT).
http://opensource.org/licenses/MIT
**********************************************************************/
#include "typedefs.h"
#ifndef SHK_FRACTION_H
#define SHK_FRACTION_H
// comment the following to disable run-time overflow checking
#define OVFCHECK
#include <iostream>
using std::ostream;
namespace shk_fraction
{
/**
Defines 'Fraction' class.
A fraction is the same as a rational number in mathematics.
A rational number is a number that can be written as a ratio of two integers.
In Fraction class, a Frction instance is always maintained in its reduced form.
The reduced form of a Fraction consists of denominator and numerator that
are relatively prime.
This class is fully checked against overflow and divide-by-zero conditions.
When such errors occur, an exception is generated to warn the caller.
The integers representing the numerator and denomerator of a fraction are of
type 'fint'. A 'fint' is a signed long long int.
*/
class Fraction
{
public:
//---------------------------
// constructors
//---------------------------
/**
Contructs the default Fraction instance: 0/1.
*/
Fraction(void);
/**
Contructs the Fraction instance: a/1.
@param a (of type fint)
*/
Fraction(fint a);
/**
Contructs the Fraction instance: a/1.
@param a numerator (of type fint)
@param b denominator (of type fint)
*/
Fraction(fint a, fint b);
//---------------------------
// accessors
//---------------------------
/**
Gets the numerator of Fraction.
*/
fint numerator(void) const; //
/**
Gets the denominator of Fraction.
*/
fint denominator(void) const;
/**
Gets the sign of Fraction.
*/
int sign(void) const;
/**
Gets the floating-point value of Fraction.
*/
double realValue(void) const;
/**
Gets the integer part of the floating-point value of Fraction.
*/
fint integerPart(void) const;
/**
Gets the fractional part of the floating-point value of Fraction.
*/
double fractionalPart(void) const;
//---------------------------
// mutators
//---------------------------
/**
Sets the numerator and denominator of Fraction.
@param a numerator (of type fint)
@param b denominator (of type fint)
*/
void set(fint a, fint b);
/**
Sets the numerator of Fraction.
@param a numerator (of type fint)
*/
void setNum(fint a);
/**
Sets the numerator of Fraction.
@param b denominator (of type fint)
*/
void setDenom(fint b);
/**
Negates the sign of Fraction.
*/
void negate(void);
/**
Converts Fraction to a proper fraction (i.e., a fraction that is less than 1).
@returns the integer part of Fraction
*/
fint properize(void);
//---------------------------
// Overloaded operators
//---------------------------
/**
Checks equality of two Fractions.
@param left Fraction
@param right Fraction
@returns true if equal, false if not equal
*/
friend bool operator==(const Fraction& left, const Fraction& right);
/**
Checks inequality of two Fractions.
@param left Fraction
@param right Fraction
@returns true if not equal, false if equal
*/
friend bool operator!=(const Fraction& left, const Fraction& right);
/**
Compares two Fractions.
@param left Fraction
@param right Fraction
@returns true if left > right, false otherwise
*/
friend bool operator>(const Fraction& left, const Fraction& right);
/**
Compares two Fractions.
@param left Fraction
@param right Fraction
@returns true if left < right, false otherwise
*/
friend bool operator<(const Fraction& left, const Fraction& right);
/**
Compares two Fractions.
@param left Fraction
@param right Fraction
@returns true if left >= right, false otherwise
*/
friend bool operator>=(const Fraction& left, const Fraction& right);
/**
Compares two Fractions.
@param left Fraction
@param right Fraction
@returns true if left <= right, false otherwise
*/
friend bool operator<=(const Fraction& left, const Fraction& right);
/**
Checks equality of a Fraction and a real.
@param left Fraction
@param right real
@returns true if left=right, false otherwise
*/
friend bool operator==(const Fraction& left, real right);
/**
Checks inequality of a Fraction and a real.
@param left Fraction
@param right real
@returns true if left != right, false otherwise
*/
friend bool operator!=(const Fraction& left, real right);
/**
Compares a Fraction with a real.
@param left Fraction
@param right real
@returns true if left > right, false otherwise
*/
friend bool operator>(const Fraction& left, real right);
/**
Compares a Fraction with a real.
@param left Fraction
@param right real
@returns true if left < right, false otherwise
*/
friend bool operator<(const Fraction& left, real right);
/**
Compares a Fraction with a real.
@param left Fraction
@param right real
@returns true if left >= right, false otherwise
*/
friend bool operator>=(const Fraction& left, real right);
/**
Compares a Fraction with a real.
@param left Fraction
@param right real
@returns true if left <= right, false otherwise
*/
friend bool operator<=(const Fraction& left, real right);
/**
Checks equality of a Fraction and a real.
@param left real
@param right Fraction
@returns true if left=right, false otherwise
*/
friend bool operator==(real left, const Fraction& right);
/**
Checks equality of a Fraction and a real.
@param left real
@param right Fraction
@returns true if left != right, false otherwise
*/
friend bool operator!=(real left, const Fraction& right);
/**
Compares a Fraction with a real.
@param left real
@param right Fraction
@returns true if left > right, false otherwise
*/
friend bool operator>(real left, const Fraction& right);
/**
Compares a Fraction with a real.
@param left real
@param right Fraction
@returns true if left < right, false otherwise
*/
friend bool operator<(real left, const Fraction& right);
/**
Compares a Fraction with a real.
@param left real
@param right Fraction
@returns true if left >= right, false otherwise
*/
friend bool operator>=(real left, const Fraction& right);
/**
Compares a Fraction with a real.
@param left real
@param right Fraction
@returns true if left <= right, false otherwise
*/
friend bool operator<=(real left, const Fraction& right);
/**
Adds two Fractions.
@param left Fraction
@param right Fraction
@returns Fraction
*/
friend Fraction operator+(const Fraction& left, const Fraction& right);
/**
Subtracts two Fractions.
@param left Fraction
@param right Fraction
@returns Fraction
*/
friend Fraction operator-(const Fraction& left, const Fraction& right);
/**
Mulitplies two Fractions.
@param left Fraction
@param right Fraction
@returns Fraction
*/
friend Fraction operator*(const Fraction& left, const Fraction& right);
/**
Divides two Fractions.
@param left Fraction
@param right Fraction
@returns Fraction
*/
friend Fraction operator/(const Fraction& left, const Fraction& right);
/**
Adds a Fraction and an integer
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator+(const Fraction& left, fint right);
/**
Subtracts an integer from a Fraction
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator-(const Fraction& left, fint right);
/**
Multiplies a Fraction by an integer
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator*(const Fraction& left, fint right);
/**
Divides a Fraction by an integer
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator/(const Fraction& left, fint right);
/**
Adds a Fraction and an integer
@param left fint
@param right Fraction
@returns Fraction
*/
friend Fraction operator+(fint left, const Fraction& right);
/**
Subtracts a Fraction from an integer
@param left fint
@param right Fraction
@returns Fraction
*/
friend Fraction operator-(fint left, const Fraction& right);
/**
Multiplies an integer by a Fraction
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator*(fint left, const Fraction& right);
/**
Divides an integer by a Fraction
@param left Fraction
@param right fint
@returns Fraction
*/
friend Fraction operator/(fint left, const Fraction& right);
/**
Negates a Fraction
@param a Fraction
@returns Fraction
*/
friend Fraction operator-(const Fraction& f);
/**
Sends a Fraction to an output stream
@param f Fraction
@returns reference to an output stream
*/
friend ostream& operator<<(ostream& out, const Fraction& f);
private:
fint num; // numerator
fint denom; // denominator
void reduce(void); // reduces fraction to its irreducible form
fint compare(Fraction f) const; // Compares fraction against another fraction f
// returns 0 if equal, negative if less than r,
// positive if greater than r
};
} // namespace shk_fraction
#endif // SHK_FRACTION_H
/**********************************************************************
Project: C++ Fractional Arithmetic Library with Overflow Checking
Language: C++ 2007
Author: Saied H. Khayat
Date: March 2012
URL: https://github.com/saiedhk
Copyright Notice: Free use of this library is permitted under the
guidelines and in accordance with the MIT License (MIT).
http://opensource.org/licenses/MIT
**********************************************************************/
#include "fraction.h"
#include "utility.h"
#include <assert.h>
namespace shk_fraction
{
//------------------------------------------------
// Constructors
//------------------------------------------------
Fraction::Fraction(void) : num(0), denom(1) {}
Fraction::Fraction(fint a) : num(a), denom(1) {}
Fraction::Fraction(fint a, fint b) : num(a), denom(b) { reduce(); }
//------------------------------------------------
// Accessors
//------------------------------------------------
fint Fraction::numerator() const
{
return num;
}
fint Fraction::denominator() const
{
return denom;
}
int Fraction::sign(void) const
{
return (num>=0) ? 1 : -1;
}
double Fraction::realValue(void) const
{
return static_cast<double>(num)/denom;
}
fint Fraction::integerPart(void) const
{
return (num / denom);
}
double Fraction::fractionalPart(void) const
{
return static_cast<double>(num)/denom - (num/denom);
}
//------------------------------------------------
// Mutators
//------------------------------------------------
// set numerator and denominator
void Fraction::set(fint a, fint b)
{
num = a;
denom = b;
reduce();
}
// set numerator
void Fraction::setNum(fint a)
{
num = a;
reduce();
}
// set denominator
void Fraction::setDenom(fint b)
{
denom = b;
reduce();
}
// change sign of fraction
void Fraction::negate(void)
{
num = -num;
}
// converts fraction to a proper fraction (in which num<denom)
// returns the integer part
fint Fraction::properize(void)
{
fint quotient = num / denom;
fint remainder = num % denom;
num = remainder;
return quotient;
}
//------------------------------------------------
// Operators
//------------------------------------------------
// equality checker
bool operator==(const Fraction& left, const Fraction& right)
{
return left.compare(right)==0;
}
// inequality checker
bool operator!=(const Fraction& left, const Fraction& right)
{
return left.compare(right)!=0;
}
// greater checker
bool operator>(const Fraction& left, const Fraction& right)
{
return left.compare(right) > 0;
}
// less checker
bool operator<(const Fraction& left, const Fraction& right)
{
return left.compare(right) < 0;
}
// equal or greater checker
bool operator>=(const Fraction& left, const Fraction& right)
{
return left.compare(right) >= 0;
}
// equal or less checker
bool operator<=(const Fraction& left, const Fraction& right)
{
return left.compare(right) <= 0;
}
//------------------------
// equality checker
bool operator==(real left, const Fraction& right)
{
return left == right.realValue();
}
// inequality checker
bool operator!=(real left, const Fraction& right)
{
return left != right.realValue();
}
// greater checker
bool operator>(real left, const Fraction& right)
{
return left > right.realValue();
}
// less checker
bool operator<(real left, const Fraction& right)
{
return left < right.realValue();
}
// equal or greater checker
bool operator>=(real left, const Fraction& right)
{
return left >= right.realValue();
}
// equal or less checker
bool operator<=(real left, const Fraction& right)
{
return left <= right.realValue();
}
//-----------------------
// equality checker
bool operator==(const Fraction& left, real right)
{
return left.realValue() == right;
}
// inequality checker
bool operator!=(const Fraction& left, real right)
{
return left.realValue() != right;
}
// greater checker
bool operator>(const Fraction& left, real right)
{
return left.realValue() > right;
}
// less checker
bool operator<(const Fraction& left, real right)
{
return left.realValue() < right;
}
// equal or greater checker
bool operator>=(const Fraction& left, real right)
{
return left.realValue() >= right;
}
// equal or less checker
bool operator<=(const Fraction& left, real right)
{
return left.realValue() <= right;
}
//----------------------------
// addition
Fraction operator+(const Fraction& left, const Fraction& right)
{
fint temp1 = left.num * right.denom;
fint temp2 = left.denom * right.num;
fint a = temp1 + temp2;
fint b = left.denom * right.denom;
#ifdef OVFCHECK
CheckMultOvf(left.num, right.denom, temp1);
CheckMultOvf(left.denom, right.num, temp2);
CheckAddOvf(temp1,temp2,a);
CheckMultOvf(left.denom, right.denom, b);
#endif
return Fraction(a,b);
}
// subtraction
Fraction operator-(const Fraction& left, const Fraction& right)
{
fint temp1 = left.num * right.denom;
fint temp2 = left.denom * right.num;
fint a = temp1 - temp2;
fint b = left.denom * right.denom;
#ifdef OVFCHECK
CheckMultOvf(left.num, right.denom, temp1);
CheckMultOvf(left.denom, right.num, temp2);
CheckAddOvf(temp1, -temp2, a);
CheckMultOvf(left.denom, right.denom, b);
#endif
return Fraction(a,b);
}
// Multiplication
Fraction operator*(const Fraction& left, const Fraction& right)
{
fint temp = gcd( abs(left.num), abs(right.denom) );
fint a1 = left.num / temp;
fint b1 = right.denom / temp;
temp = gcd( abs(left.denom), abs(right.num) );
fint a2 = right.num / temp;
fint b2 = left.denom / temp;
fint temp1 = a1 * a2;
fint temp2 = b1 * b2;
#ifdef OVFCHECK
CheckMultOvf(a1, a2, temp1);
CheckMultOvf(b1, b2, temp2);
#endif
return Fraction(temp1, temp2);
}
// Division
Fraction operator/(const Fraction& left, const Fraction& right)
{
if (right.num==0) throw ErrorDivideByZero;
fint temp = gcd( abs(left.num), abs(right.num) );
fint a1 = left.num / temp;
fint b1 = right.num / temp;
temp = gcd( abs( left.denom), abs(right.denom) );
fint a2 = right.denom / temp;
fint b2 = left.denom / temp;
fint temp1 = a1 * a2;
fint temp2 = b1 * b2;
#ifdef OVFCHECK
CheckMultOvf(a1, a2, temp1);
CheckMultOvf(b1, b2, temp2);
#endif
return Fraction((a1 * a2), (b1 * b2));
}
//----------------------
Fraction operator+(const Fraction& left, fint iright)
{
Fraction right(iright);
return left + right;
}
Fraction operator-(const Fraction& left, fint iright)
{
Fraction right(iright);
return left - right;
}
Fraction operator*(const Fraction& left, fint iright)
{
Fraction right(iright);
return left * right;
}
Fraction operator/(const Fraction& left, fint iright)
{
Fraction right(iright);
return left / right;
}
//----------------------
Fraction operator+(fint ileft, const Fraction& right)
{
Fraction left(ileft);
return left + right;
}
Fraction operator-(fint ileft, const Fraction& right)
{
Fraction left(ileft);
return left - right;
}
Fraction operator*(fint ileft, const Fraction& right)
{
Fraction left(ileft);
return left * right;
}
Fraction operator/(fint ileft, const Fraction& right)
{
Fraction left(ileft);
return left / right;
}
Fraction operator-(const Fraction& f)
{
Fraction result( -f.numerator(), f.denominator() );
return result;
}
//----------------------
ostream& operator<<(ostream &output, const Fraction& right)
{
if (right.denominator() != 1) {
output << right.numerator() << "/" << right.denominator();
} else {
output << right.numerator();
}
return output;
}
//----------------------
// Private Functions
// reduce fraction to simplest form
void Fraction::reduce(void)
{
if (denom==0) throw ErrorDivideByZero;
int sign = 1;
if (num<0) { sign = -sign; num = -num; }
if (denom<0) { sign = -sign; denom = -denom; }
fint temp = gcd(num, denom);
if (sign == -1) num = -num;
num = num / temp;
denom = denom / temp;
}
// compare two fractions
fint Fraction::compare(Fraction r) const
{
fint temp1 = num * r.denom;
fint temp2 = denom * r.num;
fint temp = temp1 - temp2;
#ifdef OVFCHECK
CheckMultOvf(num, r.denom, temp1);
CheckMultOvf(denom, r.num, temp2);
CheckAddOvf(temp1,-temp2,temp);
#endif
return temp;
}
} // namespace saied_hk
/**********************************************************************
Project: C++ Fractional Arithmetic Library with Overflow Checking
Language: C++ 2007
Author: Saied H. Khayat
Date: March 2012
URL: https://github.com/saiedhk
Copyright Notice: Free use of this library is permitted under the
guidelines and in accordance with the MIT License (MIT).
http://opensource.org/licenses/MIT
**********************************************************************/
#ifndef TYPEDEFS_H
#define TYPEDEFS_H
namespace shk_fraction
{
/**
Defines 'fint', the main integer type used in Fraction class.
*/
typedef signed long long int fint;
/**
Defines 'real', the main floating-point type in Fraction class.
*/
typedef double real;
/**
Defines exception codes.
*/
typedef enum
{
Ok,
ErrorDivideByZero,
ErrorAddOverflow,
ErrorMultOverflow
} ErrorCode;
} // namespace
#endif
/**********************************************************************
Project: C++ Fractional Arithmetic Library with Overflow Checking
Language: C++ 2007
Author: Saied H. Khayat
Date: March 2012
URL: https://github.com/saiedhk
Copyright Notice: Free use of this library is permitted under the
guidelines and in accordance with the MIT License (MIT).
http://opensource.org/licenses/MIT
**********************************************************************/
#include <assert.h>
#include "typedefs.h"
#ifndef UTILITY_H
#define UTILITY_H
namespace shk_fraction
{
// Utility functions
/**
Computes greatest common divisor of two integers (fints)
@param a fint
@param b fint
@returns gcd of a and b (fint)
*/
inline fint gcd(fint a, fint b)
{
assert((a>=0)&&(b>=0));
fint r;
if (a==0) return b;
if (b==0) return a;
while (r = a%b)
{
a = b;
b = r;
}
return b;
}
// Overflow checking functions
/**
Checks for overflow in addition, produces exception if overflow happens
@param a addend
@param b addend
@param c sum
@throws ErrorAddOverflow
*/
inline void CheckAddOvf(fint a, fint b, fint c)
{
const fint MASK = ((static_cast<fint>(1)<<(sizeof(fint)*8-1)));
if ( (~(a^b)) & (a^c) & MASK ) throw ErrorAddOverflow;
}
/**
Checks for overflow in multiplication, produces exception if overflow happens
@param a multiplicand
@param b multiplicand
@param c product
@throws ErrorMultOverflow
*/inline void CheckMultOvf(fint a, fint b, fint c)
{
if (a == 0) {
return;
}
if ( (c/a) != b ) throw ErrorMultOverflow;
}
} //namespace
#endif
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|