Der beste Weg, um einen Bruch in Java darzustellen?

100

Ich versuche mit Brüchen in Java zu arbeiten.

Ich möchte arithmetische Funktionen implementieren. Dazu benötige ich zunächst eine Möglichkeit, die Funktionen zu normalisieren. Ich weiß, dass ich 1/6 und 1/2 erst addieren kann, wenn ich einen gemeinsamen Nenner habe. Ich muss 1/6 und 3/6 hinzufügen. Ein naiver Ansatz würde mich dazu bringen, 2/12 und 6/12 hinzuzufügen und dann zu reduzieren. Wie kann ich einen gemeinsamen Nenner mit dem geringsten Leistungsverlust erreichen? Welcher Algorithmus ist dafür am besten geeignet?


Version 8 (danke an hstoerr ):

Verbesserungen umfassen:

  • Die Methode equals () stimmt jetzt mit der Methode compareTo () überein
final class Fraction extends Number {
    private int numerator;
    private int denominator;

    public Fraction(int numerator, int denominator) {
        if(denominator == 0) {
            throw new IllegalArgumentException("denominator is zero");
        }
        if(denominator < 0) {
            numerator *= -1;
            denominator *= -1;
        }
        this.numerator = numerator;
        this.denominator = denominator;
    }

    public Fraction(int numerator) {
        this.numerator = numerator;
        this.denominator = 1;
    }

    public int getNumerator() {
        return this.numerator;
    }

    public int getDenominator() {
        return this.denominator;
    }

    public byte byteValue() {
        return (byte) this.doubleValue();
    }

    public double doubleValue() {
        return ((double) numerator)/((double) denominator);
    }

    public float floatValue() {
        return (float) this.doubleValue();
    }

    public int intValue() {
        return (int) this.doubleValue();
    }

    public long longValue() {
        return (long) this.doubleValue();
    }

    public short shortValue() {
        return (short) this.doubleValue();
    }

    public boolean equals(Fraction frac) {
        return this.compareTo(frac) == 0;
    }

    public int compareTo(Fraction frac) {
        long t = this.getNumerator() * frac.getDenominator();
        long f = frac.getNumerator() * this.getDenominator();
        int result = 0;
        if(t>f) {
            result = 1;
        }
        else if(f>t) {
            result = -1;
        }
        return result;
    }
}

Ich habe alle vorherigen Versionen entfernt. Mein Dank geht an:

elf81
quelle
33
Code wegwerfen
Patrick
3
Patricks Kommentar hätte +1 verdient, wenn er als Antwort veröffentlicht worden wäre. In den meisten Fällen ist das die richtige Antwort. "Kenne und benutze die Bibliotheken", wie Effective Java sagt. Die ursprüngliche Frage ist ebenfalls klar und nützlich.
Jonik
Sie haben bemerkt, dass Sie meine Antwort akzeptiert haben. Wenn Sie diesen Code tatsächlich verwenden und Probleme damit oder etwas finden, das ihm fehlt, lassen Sie es mich bitte wissen! mailen Sie mir von meiner Website: vacant-nebula.com/contact/kip
Kip
Ich schlage vor, dass Sie Ihre "compareTo" -Methode bearbeiten und "this.getNumerator ()" zu lange vor der Multiplikation umwandeln . Andernfalls ist der Code immer noch anfällig für Überlauf. Ich denke auch, dass es schön wäre, Comparable <Fraction> zu implementieren, da Sie die compareTo-Methode bereits implementiert haben.
Hosam Aly
Und da Sie so weit gegangen sind, kann es nützlich sein, auch equals und hashCode zu implementieren.
Hosam Aly

Antworten:

65

Es ist einfach so, dass ich vor nicht allzu langer Zeit eine BigFraction-Klasse für Project Euler-Probleme geschrieben habe . Es behält einen BigInteger-Zähler und -Nenner bei, sodass es niemals überläuft. Aber es wird ein bisschen langsam für viele Operationen sein, von denen Sie wissen, dass sie niemals überlaufen werden. Verwenden Sie es trotzdem, wenn Sie es wollen. Ich wollte das irgendwie vorführen. :) :)

Bearbeiten : Die neueste und beste Version dieses Codes, einschließlich Unit-Tests, wird jetzt auf GitHub gehostet und ist auch über Maven Central verfügbar . Ich lasse meinen Originalcode hier, damit diese Antwort nicht nur ein Link ist ...


import java.math.*;

/**
 * Arbitrary-precision fractions, utilizing BigIntegers for numerator and
 * denominator.  Fraction is always kept in lowest terms.  Fraction is
 * immutable, and guaranteed not to have a null numerator or denominator.
 * Denominator will always be positive (so sign is carried by numerator,
 * and a zero-denominator is impossible).
 */
public final class BigFraction extends Number implements Comparable<BigFraction>
{
  private static final long serialVersionUID = 1L; //because Number is Serializable
  private final BigInteger numerator;
  private final BigInteger denominator;

  public final static BigFraction ZERO = new BigFraction(BigInteger.ZERO, BigInteger.ONE, true);
  public final static BigFraction ONE = new BigFraction(BigInteger.ONE, BigInteger.ONE, true);

  /**
   * Constructs a BigFraction with given numerator and denominator.  Fraction
   * will be reduced to lowest terms.  If fraction is negative, negative sign will
   * be carried on numerator, regardless of how the values were passed in.
   */
  public BigFraction(BigInteger numerator, BigInteger denominator)
  {
    if(numerator == null)
      throw new IllegalArgumentException("Numerator is null");
    if(denominator == null)
      throw new IllegalArgumentException("Denominator is null");
    if(denominator.equals(BigInteger.ZERO))
      throw new ArithmeticException("Divide by zero.");

    //only numerator should be negative.
    if(denominator.signum() < 0)
    {
      numerator = numerator.negate();
      denominator = denominator.negate();
    }

    //create a reduced fraction
    BigInteger gcd = numerator.gcd(denominator);
    this.numerator = numerator.divide(gcd);
    this.denominator = denominator.divide(gcd);
  }

  /**
   * Constructs a BigFraction from a whole number.
   */
  public BigFraction(BigInteger numerator)
  {
    this(numerator, BigInteger.ONE, true);
  }

  public BigFraction(long numerator, long denominator)
  {
    this(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
  }

  public BigFraction(long numerator)
  {
    this(BigInteger.valueOf(numerator), BigInteger.ONE, true);
  }

  /**
   * Constructs a BigFraction from a floating-point number.
   * 
   * Warning: round-off error in IEEE floating point numbers can result
   * in answers that are unexpected.  For example, 
   *     System.out.println(new BigFraction(1.1))
   * will print:
   *     2476979795053773/2251799813685248
   * 
   * This is because 1.1 cannot be expressed exactly in binary form.  The
   * given fraction is exactly equal to the internal representation of
   * the double-precision floating-point number.  (Which, for 1.1, is:
   * (-1)^0 * 2^0 * (1 + 0x199999999999aL / 0x10000000000000L).)
   * 
   * NOTE: In many cases, BigFraction(Double.toString(d)) may give a result
   * closer to what the user expects.
   */
  public BigFraction(double d)
  {
    if(Double.isInfinite(d))
      throw new IllegalArgumentException("double val is infinite");
    if(Double.isNaN(d))
      throw new IllegalArgumentException("double val is NaN");

    //special case - math below won't work right for 0.0 or -0.0
    if(d == 0)
    {
      numerator = BigInteger.ZERO;
      denominator = BigInteger.ONE;
      return;
    }

    final long bits = Double.doubleToLongBits(d);
    final int sign = (int)(bits >> 63) & 0x1;
    final int exponent = ((int)(bits >> 52) & 0x7ff) - 0x3ff;
    final long mantissa = bits & 0xfffffffffffffL;

    //number is (-1)^sign * 2^(exponent) * 1.mantissa
    BigInteger tmpNumerator = BigInteger.valueOf(sign==0 ? 1 : -1);
    BigInteger tmpDenominator = BigInteger.ONE;

    //use shortcut: 2^x == 1 << x.  if x is negative, shift the denominator
    if(exponent >= 0)
      tmpNumerator = tmpNumerator.multiply(BigInteger.ONE.shiftLeft(exponent));
    else
      tmpDenominator = tmpDenominator.multiply(BigInteger.ONE.shiftLeft(-exponent));

    //1.mantissa == 1 + mantissa/2^52 == (2^52 + mantissa)/2^52
    tmpDenominator = tmpDenominator.multiply(BigInteger.valueOf(0x10000000000000L));
    tmpNumerator = tmpNumerator.multiply(BigInteger.valueOf(0x10000000000000L + mantissa));

    BigInteger gcd = tmpNumerator.gcd(tmpDenominator);
    numerator = tmpNumerator.divide(gcd);
    denominator = tmpDenominator.divide(gcd);
  }

  /**
   * Constructs a BigFraction from two floating-point numbers.
   * 
   * Warning: round-off error in IEEE floating point numbers can result
   * in answers that are unexpected.  See BigFraction(double) for more
   * information.
   * 
   * NOTE: In many cases, BigFraction(Double.toString(numerator) + "/" + Double.toString(denominator))
   * may give a result closer to what the user expects.
   */
  public BigFraction(double numerator, double denominator)
  {
    if(denominator == 0)
      throw new ArithmeticException("Divide by zero.");

    BigFraction tmp = new BigFraction(numerator).divide(new BigFraction(denominator));
    this.numerator = tmp.numerator;
    this.denominator = tmp.denominator;
  }

  /**
   * Constructs a new BigFraction from the given BigDecimal object.
   */
  public BigFraction(BigDecimal d)
  {
    this(d.scale() < 0 ? d.unscaledValue().multiply(BigInteger.TEN.pow(-d.scale())) : d.unscaledValue(),
         d.scale() < 0 ? BigInteger.ONE                                             : BigInteger.TEN.pow(d.scale()));
  }

  public BigFraction(BigDecimal numerator, BigDecimal denominator)
  {
    if(denominator.equals(BigDecimal.ZERO))
      throw new ArithmeticException("Divide by zero.");

    BigFraction tmp = new BigFraction(numerator).divide(new BigFraction(denominator));
    this.numerator = tmp.numerator;
    this.denominator = tmp.denominator;
  }

  /**
   * Constructs a BigFraction from a String.  Expected format is numerator/denominator,
   * but /denominator part is optional.  Either numerator or denominator may be a floating-
   * point decimal number, which in the same format as a parameter to the
   * <code>BigDecimal(String)</code> constructor.
   * 
   * @throws NumberFormatException  if the string cannot be properly parsed.
   */
  public BigFraction(String s)
  {
    int slashPos = s.indexOf('/');
    if(slashPos < 0)
    {
      BigFraction res = new BigFraction(new BigDecimal(s));
      this.numerator = res.numerator;
      this.denominator = res.denominator;
    }
    else
    {
      BigDecimal num = new BigDecimal(s.substring(0, slashPos));
      BigDecimal den = new BigDecimal(s.substring(slashPos+1, s.length()));
      BigFraction res = new BigFraction(num, den);
      this.numerator = res.numerator;
      this.denominator = res.denominator;
    }
  }

  /**
   * Returns this + f.
   */
  public BigFraction add(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    //n1/d1 + n2/d2 = (n1*d2 + d1*n2)/(d1*d2) 
    return new BigFraction(numerator.multiply(f.denominator).add(denominator.multiply(f.numerator)),
                           denominator.multiply(f.denominator));
  }

  /**
   * Returns this + b.
   */
  public BigFraction add(BigInteger b)
  {
    if(b == null)
      throw new IllegalArgumentException("Null argument");

    //n1/d1 + n2 = (n1 + d1*n2)/d1
    return new BigFraction(numerator.add(denominator.multiply(b)),
                           denominator, true);
  }

  /**
   * Returns this + n.
   */
  public BigFraction add(long n)
  {
    return add(BigInteger.valueOf(n));
  }

  /**
   * Returns this - f.
   */
  public BigFraction subtract(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    return new BigFraction(numerator.multiply(f.denominator).subtract(denominator.multiply(f.numerator)),
                           denominator.multiply(f.denominator));
  }

  /**
   * Returns this - b.
   */
  public BigFraction subtract(BigInteger b)
  {
    if(b == null)
      throw new IllegalArgumentException("Null argument");

    return new BigFraction(numerator.subtract(denominator.multiply(b)),
                           denominator, true);
  }

  /**
   * Returns this - n.
   */
  public BigFraction subtract(long n)
  {
    return subtract(BigInteger.valueOf(n));
  }

  /**
   * Returns this * f.
   */
  public BigFraction multiply(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    return new BigFraction(numerator.multiply(f.numerator), denominator.multiply(f.denominator));
  }

  /**
   * Returns this * b.
   */
  public BigFraction multiply(BigInteger b)
  {
    if(b == null)
      throw new IllegalArgumentException("Null argument");

    return new BigFraction(numerator.multiply(b), denominator);
  }

  /**
   * Returns this * n.
   */
  public BigFraction multiply(long n)
  {
    return multiply(BigInteger.valueOf(n));
  }

  /**
   * Returns this / f.
   */
  public BigFraction divide(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    if(f.numerator.equals(BigInteger.ZERO))
      throw new ArithmeticException("Divide by zero");

    return new BigFraction(numerator.multiply(f.denominator), denominator.multiply(f.numerator));
  }

  /**
   * Returns this / b.
   */
  public BigFraction divide(BigInteger b)
  {
    if(b == null)
      throw new IllegalArgumentException("Null argument");

    if(b.equals(BigInteger.ZERO))
      throw new ArithmeticException("Divide by zero");

    return new BigFraction(numerator, denominator.multiply(b));
  }

  /**
   * Returns this / n.
   */
  public BigFraction divide(long n)
  {
    return divide(BigInteger.valueOf(n));
  }

  /**
   * Returns this^exponent.
   */
  public BigFraction pow(int exponent)
  {
    if(exponent == 0)
      return BigFraction.ONE;
    else if (exponent == 1)
      return this;
    else if (exponent < 0)
      return new BigFraction(denominator.pow(-exponent), numerator.pow(-exponent), true);
    else
      return new BigFraction(numerator.pow(exponent), denominator.pow(exponent), true);
  }

  /**
   * Returns 1/this.
   */
  public BigFraction reciprocal()
  {
    if(this.numerator.equals(BigInteger.ZERO))
      throw new ArithmeticException("Divide by zero");

    return new BigFraction(denominator, numerator, true);
  }

  /**
   * Returns the complement of this fraction, which is equal to 1 - this.
   * Useful for probabilities/statistics.

   */
  public BigFraction complement()
  {
    return new BigFraction(denominator.subtract(numerator), denominator, true);
  }

  /**
   * Returns -this.
   */
  public BigFraction negate()
  {
    return new BigFraction(numerator.negate(), denominator, true);
  }

  /**
   * Returns -1, 0, or 1, representing the sign of this fraction.
   */
  public int signum()
  {
    return numerator.signum();
  }

  /**
   * Returns the absolute value of this.
   */
  public BigFraction abs()
  {
    return (signum() < 0 ? negate() : this);
  }

  /**
   * Returns a string representation of this, in the form
   * numerator/denominator.
   */
  public String toString()
  {
    return numerator.toString() + "/" + denominator.toString();
  }

  /**
   * Returns if this object is equal to another object.
   */
  public boolean equals(Object o)
  {
    if(!(o instanceof BigFraction))
      return false;

    BigFraction f = (BigFraction)o;
    return numerator.equals(f.numerator) && denominator.equals(f.denominator);
  }

  /**
   * Returns a hash code for this object.
   */
  public int hashCode()
  {
    //using the method generated by Eclipse, but streamlined a bit..
    return (31 + numerator.hashCode())*31 + denominator.hashCode();
  }

  /**
   * Returns a negative, zero, or positive number, indicating if this object
   * is less than, equal to, or greater than f, respectively.
   */
  public int compareTo(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    //easy case: this and f have different signs
    if(signum() != f.signum())
      return signum() - f.signum();

    //next easy case: this and f have the same denominator
    if(denominator.equals(f.denominator))
      return numerator.compareTo(f.numerator);

    //not an easy case, so first make the denominators equal then compare the numerators 
    return numerator.multiply(f.denominator).compareTo(denominator.multiply(f.numerator));
  }

  /**
   * Returns the smaller of this and f.
   */
  public BigFraction min(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    return (this.compareTo(f) <= 0 ? this : f);
  }

  /**
   * Returns the maximum of this and f.
   */
  public BigFraction max(BigFraction f)
  {
    if(f == null)
      throw new IllegalArgumentException("Null argument");

    return (this.compareTo(f) >= 0 ? this : f);
  }

  /**
   * Returns a positive BigFraction, greater than or equal to zero, and less than one.
   */
  public static BigFraction random()
  {
    return new BigFraction(Math.random());
  }

  public final BigInteger getNumerator() { return numerator; }
  public final BigInteger getDenominator() { return denominator; }

  //implementation of Number class.  may cause overflow.
  public byte   byteValue()   { return (byte) Math.max(Byte.MIN_VALUE,    Math.min(Byte.MAX_VALUE,    longValue())); }
  public short  shortValue()  { return (short)Math.max(Short.MIN_VALUE,   Math.min(Short.MAX_VALUE,   longValue())); }
  public int    intValue()    { return (int)  Math.max(Integer.MIN_VALUE, Math.min(Integer.MAX_VALUE, longValue())); }
  public long   longValue()   { return Math.round(doubleValue()); }
  public float  floatValue()  { return (float)doubleValue(); }
  public double doubleValue() { return toBigDecimal(18).doubleValue(); }

  /**
   * Returns a BigDecimal representation of this fraction.  If possible, the
   * returned value will be exactly equal to the fraction.  If not, the BigDecimal
   * will have a scale large enough to hold the same number of significant figures
   * as both numerator and denominator, or the equivalent of a double-precision
   * number, whichever is more.
   */
  public BigDecimal toBigDecimal()
  {
    //Implementation note:  A fraction can be represented exactly in base-10 iff its
    //denominator is of the form 2^a * 5^b, where a and b are nonnegative integers.
    //(In other words, if there are no prime factors of the denominator except for
    //2 and 5, or if the denominator is 1).  So to determine if this denominator is
    //of this form, continually divide by 2 to get the number of 2's, and then
    //continually divide by 5 to get the number of 5's.  Afterward, if the denominator
    //is 1 then there are no other prime factors.

    //Note: number of 2's is given by the number of trailing 0 bits in the number
    int twos = denominator.getLowestSetBit();
    BigInteger tmpDen = denominator.shiftRight(twos); // x / 2^n === x >> n

    final BigInteger FIVE = BigInteger.valueOf(5);
    int fives = 0;
    BigInteger[] divMod = null;

    //while(tmpDen % 5 == 0) { fives++; tmpDen /= 5; }
    while(BigInteger.ZERO.equals((divMod = tmpDen.divideAndRemainder(FIVE))[1]))
    {
      fives++;
      tmpDen = divMod[0];
    }

    if(BigInteger.ONE.equals(tmpDen))
    {
      //This fraction will terminate in base 10, so it can be represented exactly as
      //a BigDecimal.  We would now like to make the fraction of the form
      //unscaled / 10^scale.  We know that 2^x * 5^x = 10^x, and our denominator is
      //in the form 2^twos * 5^fives.  So use max(twos, fives) as the scale, and
      //multiply the numerator and deminator by the appropriate number of 2's or 5's
      //such that the denominator is of the form 2^scale * 5^scale.  (Of course, we
      //only have to actually multiply the numerator, since all we need for the
      //BigDecimal constructor is the scale.
      BigInteger unscaled = numerator;
      int scale = Math.max(twos, fives);

      if(twos < fives)
        unscaled = unscaled.shiftLeft(fives - twos); //x * 2^n === x << n
      else if (fives < twos)
        unscaled = unscaled.multiply(FIVE.pow(twos - fives));

      return new BigDecimal(unscaled, scale);
    }

    //else: this number will repeat infinitely in base-10.  So try to figure out
    //a good number of significant digits.  Start with the number of digits required
    //to represent the numerator and denominator in base-10, which is given by
    //bitLength / log[2](10).  (bitLenth is the number of digits in base-2).
    final double LG10 = 3.321928094887362; //Precomputed ln(10)/ln(2), a.k.a. log[2](10)
    int precision = Math.max(numerator.bitLength(), denominator.bitLength());
    precision = (int)Math.ceil(precision / LG10);

    //If the precision is less than 18 digits, use 18 digits so that the number
    //will be at least as accurate as a cast to a double.  For example, with
    //the fraction 1/3, precision will be 1, giving a result of 0.3.  This is
    //quite a bit different from what a user would expect.
    if(precision < 18)
      precision = 18;

    return toBigDecimal(precision);
  }

  /**
   * Returns a BigDecimal representation of this fraction, with a given precision.
   * @param precision  the number of significant figures to be used in the result.
   */
  public BigDecimal toBigDecimal(int precision)
  {
    return new BigDecimal(numerator).divide(new BigDecimal(denominator), new MathContext(precision, RoundingMode.HALF_EVEN));
  }

  //--------------------------------------------------------------------------
  //  PRIVATE FUNCTIONS
  //--------------------------------------------------------------------------

  /**
   * Private constructor, used when you can be certain that the fraction is already in
   * lowest terms.  No check is done to reduce numerator/denominator.  A check is still
   * done to maintain a positive denominator.
   * 
   * @param throwaway  unused variable, only here to signal to the compiler that this
   *                   constructor should be used.
   */
  private BigFraction(BigInteger numerator, BigInteger denominator, boolean throwaway)
  {
    if(denominator.signum() < 0)
    {
      this.numerator = numerator.negate();
      this.denominator = denominator.negate();
    }
    else
    {
      this.numerator = numerator;
      this.denominator = denominator;
    }
  }

}
Pennen
quelle
Wenn ein Argument null ist, lösen Sie eine NullPointerException aus. In der Tat wird der Code das sowieso tun, so dass Ihre Überprüfung (und Ersetzung durch IllegalArgumentException (unnötiges Aufblähen des Codes)
Cletus
24
Ich bin nicht einverstanden; Wenn ein anderer Benutzer diese Klasse verwenden würde, ohne auf meine Quelle zu schauen, und eine NullPointerException erhalten würde, würde er denken, dass mein Code einen Fehler enthält. Eine IllegalArgumentException zeigt jedoch, dass er den vom Javadoc implizierten Vertrag gebrochen hat (obwohl ich ihn nicht explizit angegeben habe).
Kip
1
Nur eine Frage, was ist los mit Fraction und BigFraction in Commons Math?
Mortimer
@ Mortimer: nicht sicher, ich habe es nie angeschaut
Kip
61
  • Mach es unveränderlich ;
  • Machen Sie es kanonisch , was bedeutet, dass 6/4 zu 3/2 wird (der größte gemeinsame Divisor- Algorithmus ist dafür nützlich);
  • Nennen Sie es rational, da das, was Sie darstellen, eine rationale Zahl ist ;
  • Sie können BigIntegerbeliebig genaue Werte speichern. Wenn nicht, dann long, was eine einfachere Implementierung hat;
  • Machen Sie den Nenner immer positiv. Das Zeichen sollte vom Zähler getragen werden.
  • Verlängern Number;
  • Implementieren Comparable<T>;
  • Implementieren equals()und hashCode();
  • Fügen Sie die Factory-Methode für eine Zahl hinzu, die durch a dargestellt wird String.
  • Fügen Sie einige Convenience-Factory-Methoden hinzu.
  • Füge a hinzu toString(); und
  • Mach es Serializable.

In der Tat versuchen Sie dies für die Größe an. Es läuft, kann aber einige Probleme haben:

public class BigRational extends Number implements Comparable<BigRational>, Serializable {
    public final static BigRational ZERO = new BigRational(BigInteger.ZERO, BigInteger.ONE);
    private final static long serialVersionUID = 1099377265582986378L;

    private final BigInteger numerator, denominator;

    private BigRational(BigInteger numerator, BigInteger denominator) {
        this.numerator = numerator;
        this.denominator = denominator;
    }

    private static BigRational canonical(BigInteger numerator, BigInteger denominator, boolean checkGcd) {
        if (denominator.signum() == 0) {
            throw new IllegalArgumentException("denominator is zero");
        }
        if (numerator.signum() == 0) {
            return ZERO;
        }
        if (denominator.signum() < 0) {
            numerator = numerator.negate();
            denominator = denominator.negate();
        }
        if (checkGcd) {
            BigInteger gcd = numerator.gcd(denominator);
            if (!gcd.equals(BigInteger.ONE)) {
                numerator = numerator.divide(gcd);
                denominator = denominator.divide(gcd);
            }
        }
        return new BigRational(numerator, denominator);
    }

    public static BigRational getInstance(BigInteger numerator, BigInteger denominator) {
        return canonical(numerator, denominator, true);
    }

    public static BigRational getInstance(long numerator, long denominator) {
        return canonical(new BigInteger("" + numerator), new BigInteger("" + denominator), true);
    }

    public static BigRational getInstance(String numerator, String denominator) {
        return canonical(new BigInteger(numerator), new BigInteger(denominator), true);
    }

    public static BigRational valueOf(String s) {
        Pattern p = Pattern.compile("(-?\\d+)(?:.(\\d+)?)?0*(?:e(-?\\d+))?");
        Matcher m = p.matcher(s);
        if (!m.matches()) {
            throw new IllegalArgumentException("Unknown format '" + s + "'");
        }

        // this translates 23.123e5 to 25,123 / 1000 * 10^5 = 2,512,300 / 1 (GCD)
        String whole = m.group(1);
        String decimal = m.group(2);
        String exponent = m.group(3);
        String n = whole;

        // 23.123 => 23123
        if (decimal != null) {
            n += decimal;
        }
        BigInteger numerator = new BigInteger(n);

        // exponent is an int because BigInteger.pow() takes an int argument
        // it gets more difficult if exponent needs to be outside {-2 billion,2 billion}
        int exp = exponent == null ? 0 : Integer.valueOf(exponent);
        int decimalPlaces = decimal == null ? 0 : decimal.length();
        exp -= decimalPlaces;
        BigInteger denominator;
        if (exp < 0) {
            denominator = BigInteger.TEN.pow(-exp);
        } else {
            numerator = numerator.multiply(BigInteger.TEN.pow(exp));
            denominator = BigInteger.ONE;
        }

        // done
        return canonical(numerator, denominator, true);
    }

    // Comparable
    public int compareTo(BigRational o) {
        // note: this is a bit of cheat, relying on BigInteger.compareTo() returning
        // -1, 0 or 1.  For the more general contract of compareTo(), you'd need to do
        // more checking
        if (numerator.signum() != o.numerator.signum()) {
            return numerator.signum() - o.numerator.signum();
        } else {
            // oddly BigInteger has gcd() but no lcm()
            BigInteger i1 = numerator.multiply(o.denominator);
            BigInteger i2 = o.numerator.multiply(denominator);
            return i1.compareTo(i2); // expensive!
        }
    }

    public BigRational add(BigRational o) {
        if (o.numerator.signum() == 0) {
            return this;
        } else if (numerator.signum() == 0) {
            return o;
        } else if (denominator.equals(o.denominator)) {
            return new BigRational(numerator.add(o.numerator), denominator);
        } else {
            return canonical(numerator.multiply(o.denominator).add(o.numerator.multiply(denominator)), denominator.multiply(o.denominator), true);
        }
    }


    public BigRational multiply(BigRational o) {
        if (numerator.signum() == 0 || o.numerator.signum( )== 0) {
            return ZERO;
        } else if (numerator.equals(o.denominator)) {
            return canonical(o.numerator, denominator, true);
        } else if (o.numerator.equals(denominator)) {
            return canonical(numerator, o.denominator, true);
        } else if (numerator.negate().equals(o.denominator)) {
            return canonical(o.numerator.negate(), denominator, true);
        } else if (o.numerator.negate().equals(denominator)) {
            return canonical(numerator.negate(), o.denominator, true);
        } else {
            return canonical(numerator.multiply(o.numerator), denominator.multiply(o.denominator), true);
        }
    }

    public BigInteger getNumerator() { return numerator; }
    public BigInteger getDenominator() { return denominator; }
    public boolean isInteger() { return numerator.signum() == 0 || denominator.equals(BigInteger.ONE); }
    public BigRational negate() { return new BigRational(numerator.negate(), denominator); }
    public BigRational invert() { return canonical(denominator, numerator, false); }
    public BigRational abs() { return numerator.signum() < 0 ? negate() : this; }
    public BigRational pow(int exp) { return canonical(numerator.pow(exp), denominator.pow(exp), true); }
    public BigRational subtract(BigRational o) { return add(o.negate()); }
    public BigRational divide(BigRational o) { return multiply(o.invert()); }
    public BigRational min(BigRational o) { return compareTo(o) <= 0 ? this : o; }
    public BigRational max(BigRational o) { return compareTo(o) >= 0 ? this : o; }

    public BigDecimal toBigDecimal(int scale, RoundingMode roundingMode) {
        return isInteger() ? new BigDecimal(numerator) : new BigDecimal(numerator).divide(new BigDecimal(denominator), scale, roundingMode);
    }

    // Number
    public int intValue() { return isInteger() ? numerator.intValue() : numerator.divide(denominator).intValue(); }
    public long longValue() { return isInteger() ? numerator.longValue() : numerator.divide(denominator).longValue(); }
    public float floatValue() { return (float)doubleValue(); }
    public double doubleValue() { return isInteger() ? numerator.doubleValue() : numerator.doubleValue() / denominator.doubleValue(); }

    @Override
    public String toString() { return isInteger() ? String.format("%,d", numerator) : String.format("%,d / %,d", numerator, denominator); }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        BigRational that = (BigRational) o;

        if (denominator != null ? !denominator.equals(that.denominator) : that.denominator != null) return false;
        if (numerator != null ? !numerator.equals(that.numerator) : that.numerator != null) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = numerator != null ? numerator.hashCode() : 0;
        result = 31 * result + (denominator != null ? denominator.hashCode() : 0);
        return result;
    }

    public static void main(String args[]) {
        BigRational r1 = BigRational.valueOf("3.14e4");
        BigRational r2 = BigRational.getInstance(111, 7);
        dump("r1", r1);
        dump("r2", r2);
        dump("r1 + r2", r1.add(r2));
        dump("r1 - r2", r1.subtract(r2));
        dump("r1 * r2", r1.multiply(r2));
        dump("r1 / r2", r1.divide(r2));
        dump("r2 ^ 2", r2.pow(2));
    }

    public static void dump(String name, BigRational r) {
        System.out.printf("%s = %s%n", name, r);
        System.out.printf("%s.negate() = %s%n", name, r.negate());
        System.out.printf("%s.invert() = %s%n", name, r.invert());
        System.out.printf("%s.intValue() = %,d%n", name, r.intValue());
        System.out.printf("%s.longValue() = %,d%n", name, r.longValue());
        System.out.printf("%s.floatValue() = %,f%n", name, r.floatValue());
        System.out.printf("%s.doubleValue() = %,f%n", name, r.doubleValue());
        System.out.println();
    }
}

Ausgabe ist:

r1 = 31,400
r1.negate() = -31,400
r1.invert() = 1 / 31,400
r1.intValue() = 31,400
r1.longValue() = 31,400
r1.floatValue() = 31,400.000000
r1.doubleValue() = 31,400.000000

r2 = 111 / 7
r2.negate() = -111 / 7
r2.invert() = 7 / 111
r2.intValue() = 15
r2.longValue() = 15
r2.floatValue() = 15.857142
r2.doubleValue() = 15.857143

r1 + r2 = 219,911 / 7
r1 + r2.negate() = -219,911 / 7
r1 + r2.invert() = 7 / 219,911
r1 + r2.intValue() = 31,415
r1 + r2.longValue() = 31,415
r1 + r2.floatValue() = 31,415.857422
r1 + r2.doubleValue() = 31,415.857143

r1 - r2 = 219,689 / 7
r1 - r2.negate() = -219,689 / 7
r1 - r2.invert() = 7 / 219,689
r1 - r2.intValue() = 31,384
r1 - r2.longValue() = 31,384
r1 - r2.floatValue() = 31,384.142578
r1 - r2.doubleValue() = 31,384.142857

r1 * r2 = 3,485,400 / 7
r1 * r2.negate() = -3,485,400 / 7
r1 * r2.invert() = 7 / 3,485,400
r1 * r2.intValue() = 497,914
r1 * r2.longValue() = 497,914
r1 * r2.floatValue() = 497,914.281250
r1 * r2.doubleValue() = 497,914.285714

r1 / r2 = 219,800 / 111
r1 / r2.negate() = -219,800 / 111
r1 / r2.invert() = 111 / 219,800
r1 / r2.intValue() = 1,980
r1 / r2.longValue() = 1,980
r1 / r2.floatValue() = 1,980.180176
r1 / r2.doubleValue() = 1,980.180180

r2 ^ 2 = 12,321 / 49
r2 ^ 2.negate() = -12,321 / 49
r2 ^ 2.invert() = 49 / 12,321
r2 ^ 2.intValue() = 251
r2 ^ 2.longValue() = 251
r2 ^ 2.floatValue() = 251.448975
r2 ^ 2.doubleValue() = 251.448980
Cletus
quelle
30

Ich versuche, mit richtigen Brüchen in Java zu arbeiten.

Apache Commons Math hat seit einiger Zeit eine Fraction- Klasse. Meistens die Antwort auf "Junge, ich wünschte, Java hätte so etwas wie X in der Kernbibliothek!" finden Sie unter dem Dach der Apache Commons-Bibliothek .

Giermark
quelle
2
Ich werde Ihnen sagen, warum dies so niedrig ist, die Apache Commons-Bibliothek ist nicht für Neulinge geeignet. Erstens gibt es keinen direkten Link zum Herunterladen auf dieser Seite (er ist im Seitenleistenmenü versteckt), zweitens gibt es keine Anweisungen zur Verwendung (Hinzufügen eines JARs zu Ihrem Erstellungspfad), drittens habe ich einen classDefNotFound-Fehler erhalten, nachdem ich alles hinzugefügt habe . Sie erhalten also keine positiven Stimmen von uns Leuten, die nur wissen, wie man kopiert und einfügt.
Noumenon
@ Noumenon, wie wäre es, einen Build-Manager (z. B. Maven) zu verwenden und einfach die Abhängigkeit in POM hinzuzufügen?
Eugene.polschikov
1
Ich würde gerne ein kleines Klappentext "Wie man das in Ihrem Projekt verwendet" für die Noobs sehen. Dieser Vorschlag könnte dort hineingehen. Das heißt, ich habe herausgefunden, wie es geht, und es in meiner Factory-App verwendet, für die Bruchteile von Zoll angezeigt werden mussten, und ich bin nie zurückgekommen, um Ihnen Ihre Zustimmung zu geben. Also danke, hier ist es verspätet.
Noumenon
Das ist faires Feedback. Hier ist auch mein verspäteter Dank! :)
Yawmark
Dieser ist ziemlich einfach zu bedienen.
Eric Wang
24

Bitte machen Sie es zu einem unveränderlichen Typ! Der Wert eines Bruchs ändert sich nicht - eine Hälfte wird beispielsweise nicht zu einem Drittel. Anstelle von setDenominator könnten Sie withDenominator verwenden, das einen neuen zurückgibt Bruch der denselben Zähler, aber den angegebenen Nenner hat.

Das Leben ist vielMit unveränderlichen Typen einfacher.

Das Überschreiben von Gleichheit und Hashcode wäre ebenfalls sinnvoll, sodass es in Karten und Mengen verwendet werden kann. Die Punkte von Outlaw Programmer zu arithmetischen Operatoren und zur Formatierung von Zeichenfolgen sind ebenfalls gut.

Schauen Sie sich als allgemeine Anleitung BigInteger und BigDecimal an. Sie machen nicht dasselbe, aber sie sind ähnlich genug, um Ihnen gute Ideen zu geben.

Jon Skeet
quelle
5
"Bitte machen Sie es zu einem unveränderlichen Typ! Der Wert eines Bruchs ändert sich nicht - eine Hälfte wird zum Beispiel nicht zu einem Drittel." Die Liste / das Tupel / der Vektor (1, 2, 3, 4) wird auch nicht zum Wert (4, 3, 2, 1), aber es scheint die meisten Leute, die Listen ändern, nicht zu stören. Nicht, dass ich der Unveränderlichkeit für Brüche nicht zustimme, aber es verdient ein besseres Argument. Es fühlt sich wie ein Wert mehr als ein Bündel von Staat an. Ist die Erwartung eines Programmierers der richtige Grund, sich leiten zu lassen? Ich bin mir nicht 100% sicher, aber es klingt nach einer guten Idee.
Jonas Kölker
2
Nun, im wirklichen Leben Listen tun ändern: Wie schreiben Sie eine Einkaufsliste? Sie beginnen mit einem leeren Blatt Papier und schreiben darauf. Auf halbem Weg würden Sie es immer noch "die Einkaufsliste" nennen. Trotzdem bemüht sich die funktionale Programmierung, gerade Listen unveränderlich zu machen ...
Jon Skeet
7

Zum einen würde ich die Setter loswerden und Fractions unveränderlich machen.

Sie möchten wahrscheinlich auch Methoden zum Hinzufügen, Subtrahieren usw. und möglicherweise eine Möglichkeit, die Darstellung in verschiedenen String-Formaten zu erhalten.

EDIT: Ich würde wahrscheinlich die Felder als "endgültig" markieren, um meine Absicht zu signalisieren, aber ich denke, es ist keine große Sache ...

Outlaw Programmer
quelle
2
Ich frage mich, wie viele Antworten "unveränderlich machen" wir am Ende haben werden :)
Jon Skeet
5
  • Es ist irgendwie sinnlos ohne arithmetische Methoden wie add () und multiplizieren () usw.
  • Sie sollten auf jeden Fall equals () und hashCode () überschreiben.
  • Sie sollten entweder eine Methode hinzufügen, um den Bruch zu normalisieren, oder dies automatisch tun. Überlegen Sie, ob 1/2 und 2/4 gleich sein sollen oder nicht - dies hat Auswirkungen auf die Methoden equals (), hashCode () und compareTo ().
Michael Borgwardt
quelle
5

Ich muss sie vom kleinsten zum größten bestellen, also muss ich sie schließlich auch als Doppel darstellen

Nicht unbedingt notwendig. (Wenn Sie mit Gleichheit richtig umgehen möchten, verlassen Sie sich nicht auf double, um richtig zu arbeiten.) Wenn b * d positiv ist, ist a / b <c / d, wenn ad <bc. Wenn es sich um negative Ganzzahlen handelt, kann dies angemessen behandelt werden ...

Ich könnte umschreiben als:

public int compareTo(Fraction frac)
{
    // we are comparing this=a/b with frac=c/d 
    // by multiplying both sides by bd.
    // If bd is positive, then a/b < c/d <=> ad < bc.
    // If bd is negative, then a/b < c/d <=> ad > bc.
    // If bd is 0, then you've got other problems (either b=0 or d=0)
    int d = frac.getDenominator();
    long ad = (long)this.numerator * d;
    long bc = (long)this.denominator * frac.getNumerator();
    long diff = ((long)d*this.denominator > 0) ? (ad-bc) : (bc-ad);
    return (diff > 0 ? 1 : (diff < 0 ? -1 : 0));
}

Die Verwendung von longhier soll sicherstellen, dass es keinen Überlauf gibt, wenn Sie zwei große multiplizierenint s . handle Wenn Sie garantieren können, dass der Nenner immer nicht negativ ist (wenn er negativ ist, negieren Sie einfach sowohl den Zähler als auch den Nenner), müssen Sie nicht mehr prüfen, ob b * d positiv ist, und einige Schritte speichern. Ich bin mir nicht sicher, nach welchem ​​Verhalten Sie mit einem Nenner von Null suchen.

Ich bin mir nicht sicher, wie die Leistung im Vergleich zur Verwendung von Doppelwerten verglichen werden soll. (Das heißt, wenn Sie sich so sehr für die Leistung interessieren) Hier ist eine Testmethode, die ich zur Überprüfung verwendet habe. (Scheint richtig zu funktionieren.)

public static void main(String[] args)
{
    int a = Integer.parseInt(args[0]);
    int b = Integer.parseInt(args[1]);
    int c = Integer.parseInt(args[2]);
    int d = Integer.parseInt(args[3]);
    Fraction f1 = new Fraction(a,b); 
    Fraction f2 = new Fraction(c,d);
    int rel = f1.compareTo(f2);
    String relstr = "<=>";
    System.out.println(a+"/"+b+" "+relstr.charAt(rel+1)+" "+c+"/"+d);
}

(ps Sie könnten eine Umstrukturierung in Betracht ziehen, um sie zu implementieren Comparableoder Comparatorfür Ihre Klasse.)

Jason S.
quelle
Dies gilt nicht, wenn beispielsweise a = 1, b = 3, c = -2, d = -3. Wenn b und d positiv sind, ist es wahr, dass a / b <c / d genau dann ist, wenn ad <bc.
Luke Woodward
Argh, ich habe die Qualifikation falsch verstanden. (danke!) Die Bedingung sollte sein, wenn bd> 0.
Jason S
Wahr. Genauer gesagt ist a / b <c / d <=> ac <bd wahr, vorausgesetzt bd> 0. Wenn bd <0 ist, ist das Gegenteil wahr. (Wenn bd = 0, dann haben Sie eine
Paul Brinkley
Schließen. du meinst a / b <c / d <=> ad <bc für bd> 0. (Ich habe es gleich beim ersten Mal in meinen Code-Kommentaren richtig gemacht!)
Jason S
4

Eine sehr geringfügige Verbesserung könnte möglicherweise darin bestehen, den von Ihnen berechneten doppelten Wert so zu speichern, dass Sie ihn nur beim ersten Zugriff berechnen. Dies wird kein großer Gewinn sein, wenn Sie nicht häufig auf diese Nummer zugreifen, aber es ist auch nicht allzu schwierig, dies zu tun.

Ein zusätzlicher Punkt könnte die Fehlerprüfung sein, die Sie im Nenner durchführen ... Sie ändern automatisch 0 in 1. Sie sind sich nicht sicher, ob dies für Ihre spezielle Anwendung korrekt ist, aber im Allgemeinen stimmt etwas nicht, wenn jemand versucht, durch 0 zu teilen . Ich würde dies eine Ausnahme auslösen lassen (eine spezielle Ausnahme, wenn Sie dies für erforderlich halten), anstatt den Wert auf eine scheinbar willkürliche Weise zu ändern, die dem Benutzer nicht bekannt ist.

Im Gegensatz zu einigen anderen Kommentaren zum Hinzufügen von Methoden zum Hinzufügen von Subtrahieren usw. ... da Sie nicht erwähnt haben, dass sie benötigt werden, gehe ich davon aus, dass Sie dies nicht tun. Und wenn Sie keine Bibliothek bauen, die wirklich an vielen Orten oder von anderen Menschen genutzt wird, gehen Sie mit YAGNI (Sie werden sie nicht brauchen, also sollte sie nicht da sein.)

Beska
quelle
Die Tatsache, dass er getNumerator () und getDenominator () hat, lässt mich glauben, dass er AUSSERHALB dieser Klasse neue Brüche erstellt hat. Diese Logik gehört wahrscheinlich hierher, wenn sie existiert.
Outlaw Programmer
+1 Das stille Ändern von 0 zu 1 im Nenner ist ein Rezept für eine Katastrophe.
Maaartinus
4

Es gibt verschiedene Möglichkeiten, diesen oder einen beliebigen Werttyp zu verbessern:

  • Machen Sie Ihre Klasse unveränderlich , einschließlich der endgültigen Festlegung von Zähler und Nenner
  • Konvertieren Sie Brüche automatisch in eine kanonische Form , z. B. 2/4 -> 1/2
  • Implementiere toString ()
  • Implementieren Sie "public static Fraction valueOf (String s)", um von Strings in Brüche zu konvertieren. Implementieren Sie ähnliche Factory-Methoden zum Konvertieren von int, double usw.
  • Implementieren Sie Addition, Multiplikation usw.
  • Konstruktor aus ganzen Zahlen hinzufügen
  • Override entspricht / hashCode
  • Erwägen Sie, Fraction zu einer Schnittstelle mit einer Implementierung zu machen, die bei Bedarf zu BigInteger wechselt
  • Betrachten Sie eine Unterklassifizierung Anzahl
  • Erwägen Sie, benannte Konstanten für allgemeine Werte wie 0 und 1 einzuschließen
  • Erwägen Sie, es serialisierbar zu machen
  • Test auf Division durch Null
  • Dokumentieren Sie Ihre API

Schauen Sie sich im Grunde die API für andere Werteklassen wie Double , Integer an und tun Sie, was sie tun :)

Dave Ray
quelle
3

Wenn Sie den Zähler und den Nenner eines Bruchs mit dem Nenner des anderen multiplizieren und umgekehrt, erhalten Sie zwei Brüche (die immer noch dieselben Werte sind) mit demselben Nenner und können die Zähler direkt vergleichen. Daher müssten Sie den doppelten Wert nicht berechnen:

public int compareTo(Fraction frac) {
    int t = this.numerator * frac.getDenominator();
    int f = frac.getNumerator() * this.denominator;
    if(t>f) return 1;
    if(f>t) return -1;
    return 0;
}
Francisco Canedo
quelle
Dies schlägt fehl, wenn frac.getDenominator () und this.denominator entgegengesetzte Vorzeichen haben. (Siehe meinen Beitrag.) Außerdem muss man darauf achten, dass die Multiplikation überlaufen kann.
Jason S
Ah ja, das stimmt. Aber in diesem Fall bevorzuge ich die Implementierung von Kip, die ich zumindest verstehen kann. ;)
Francisco Canedo
Ich möchte darauf hinweisen, dass in meiner Implementierung nur der Zähler negativ sein kann. Ich verwende auch BigInteger, damit es nie zu einem Überlauf kommt (natürlich auf Kosten einer gewissen Leistung).
Kip
2

wie ich diesen Code verbessern würde:

  1. ein Konstruktor basierend auf String Fraction (String s) // erwarte "number / number"
  2. ein Kopierkonstruktor Bruch (Bruchkopie)
  3. Überschreiben Sie die Klonmethode
  4. implementiert die Methoden equals, toString und hashcode
  5. implementiert die Schnittstelle java.io.Serializable, Comparable
  6. eine Methode "double getDoubleValue ()"
  7. eine Methode add / dividieren / etc ...
  8. Ich würde diese Klasse als unveränderlich machen (keine Setter)
Pierre
quelle
Eine ziemlich schöne Liste. Es ist wahrscheinlich nicht erforderlich, zu klonen / serialisierbar zu sein, aber alles andere ist vernünftig.
Outlaw Programmer
@OutlawProgrammer: Ja, entweder 8 oder 3. Klonbar unveränderlich ist ein Unsinn.
Maaartinus
2

Sie haben bereits eine compareTo-Funktion ... Ich würde die Comparable-Schnittstelle implementieren.

Vielleicht spielt es keine Rolle, was auch immer Sie damit machen werden.

Dave Costa
quelle
2

Wenn Sie sich abenteuerlustig fühlen, schauen Sie sich JScience an . Es hat eine RationalKlasse, die Brüche darstellt.

Zach Scrivena
quelle
2

Konkret : Gibt es eine bessere Möglichkeit, einen Null-Nenner zu übergeben? Das Setzen des Nenners auf 1 fühlt sich mächtig willkürlich an. Wie kann ich das richtig machen?

Ich würde sagen, wirf eine ArithmeticException für die Division durch Null, da genau das passiert:

public Fraction(int numerator, int denominator) {
    if(denominator == 0)
        throw new ArithmeticException("Divide by zero.");
    this.numerator = numerator;
    this.denominator = denominator;
}

Anstelle von "Durch Null teilen" möchten Sie möglicherweise die Meldung "Durch Null teilen: Nenner für Bruch ist Null" anzeigen.

Pennen
quelle
1

Wenn Sie ein Bruchobjekt erstellt haben, warum sollten Sie anderen Objekten erlauben, den Zähler oder den Nenner festzulegen? Ich würde denken, dass diese nur gelesen werden sollten. Es macht das Objekt unveränderlich ...

Außerdem ... sollte das Setzen des Nenners auf Null eine ungültige Argumentausnahme auslösen (ich weiß nicht, was es in Java ist).

Jason Punyon
quelle
Oder werfen Sie eine neue ArithmeticException ("Teilen durch Null")
Kip
1

Timothy Budd hat eine gute Implementierung einer Rational-Klasse in seinen "Data Structures in C ++". Natürlich eine andere Sprache, aber die Portierung auf Java ist sehr gut.

Ich würde mehr Konstruktoren empfehlen. Ein Standardkonstruktor hätte den Zähler 0, den Nenner 1. Ein einzelner arg-Konstruktor würde einen Nenner von 1 annehmen. Überlegen Sie, wie Ihre Benutzer diese Klasse verwenden könnten.

Keine Prüfung auf Nenner Null? Wenn Sie vertraglich programmieren, müssen Sie es hinzufügen.

Duffymo
quelle
1

Ich werde den dritten oder fünften oder was auch immer die Empfehlung sein, Ihren Bruch unveränderlich zu machen. Ich würde auch empfehlen, dass Sie die Number- Klasse erweitern. Ich würde mir wahrscheinlich die Double- Klasse ansehen , da Sie wahrscheinlich viele der gleichen Methoden implementieren möchten.

Sie sollten wahrscheinlich auch Comparable and Serializable implementieren, da dieses Verhalten wahrscheinlich erwartet wird. Daher müssen Sie compareTo () implementieren. Sie müssen auch equals () überschreiben, und ich kann nicht stark genug betonen, dass Sie auch hashCode () überschreiben. Dies kann jedoch einer der wenigen Fälle sein, in denen compareTo () und equals () nicht konsistent sein sollen, da die auf einander reduzierbaren Brüche nicht unbedingt gleich sind.

James
quelle
1

Eine Aufräumpraxis, die ich mag, ist, nur eine Rückkehr zu haben.

 public int compareTo(Fraction frac) {
        int result = 0
        double t = this.doubleValue();
        double f = frac.doubleValue();
        if(t>f) 
           result = 1;
        else if(f>t) 
           result -1;
        return result;
    }
Milhous
quelle
1

Verwenden Sie die Rational-Klasse aus der JScience- Bibliothek. Es ist das Beste für die gebrochene Arithmetik, die ich in Java gesehen habe.

Alexander Temerev
quelle
1

Ich habe Cletus 'Antwort aufgeräumt :

  • Javadoc für alle Methoden hinzugefügt.
  • Überprüfungen für Methodenvoraussetzungen hinzugefügt.
  • Ersetzt das benutzerdefinierte Parsen valueOf(String)durch das, BigInteger(String)das sowohl flexibler als auch schneller ist.
import com.google.common.base.Splitter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.List;
import java.util.Objects;
import org.bitbucket.cowwoc.preconditions.Preconditions;

/**
 * A rational fraction, represented by {@code numerator / denominator}.
 * <p>
 * This implementation is based on <a
 * href="https://stackoverflow.com/a/474577/14731">https://stackoverflow.com/a/474577/14731</a>
 * <p>
 * @author Gili Tzabari
 */
public final class BigRational extends Number implements Comparable<BigRational>
{
    private static final long serialVersionUID = 0L;
    public static final BigRational ZERO = new BigRational(BigInteger.ZERO, BigInteger.ONE);
    public static final BigRational ONE = new BigRational(BigInteger.ONE, BigInteger.ONE);

    /**
     * Ensures the fraction the denominator is positive and optionally divides the numerator and
     * denominator by the greatest common factor.
     * <p>
     * @param numerator   a numerator
     * @param denominator a denominator
     * @param checkGcd    true if the numerator and denominator should be divided by the greatest
     *                    common factor
     * @return the canonical representation of the rational fraction
     */
    private static BigRational canonical(BigInteger numerator, BigInteger denominator,
        boolean checkGcd)
    {
        assert (numerator != null);
        assert (denominator != null);
        if (denominator.signum() == 0)
            throw new IllegalArgumentException("denominator is zero");
        if (numerator.signum() == 0)
            return ZERO;
        BigInteger newNumerator = numerator;
        BigInteger newDenominator = denominator;
        if (newDenominator.signum() < 0)
        {
            newNumerator = newNumerator.negate();
            newDenominator = newDenominator.negate();
        }
        if (checkGcd)
        {
            BigInteger gcd = newNumerator.gcd(newDenominator);
            if (!gcd.equals(BigInteger.ONE))
            {
                newNumerator = newNumerator.divide(gcd);
                newDenominator = newDenominator.divide(gcd);
            }
        }
        return new BigRational(newNumerator, newDenominator);
    }

    /**
     * @param numerator   a numerator
     * @param denominator a denominator
     * @return a BigRational having value {@code numerator / denominator}
     * @throws NullPointerException if numerator or denominator are null
     */
    public static BigRational valueOf(BigInteger numerator, BigInteger denominator)
    {
        Preconditions.requireThat(numerator, "numerator").isNotNull();
        Preconditions.requireThat(denominator, "denominator").isNotNull();
        return canonical(numerator, denominator, true);
    }

    /**
     * @param numerator   a numerator
     * @param denominator a denominator
     * @return a BigRational having value {@code numerator / denominator}
     */
    public static BigRational valueOf(long numerator, long denominator)
    {
        BigInteger bigNumerator = BigInteger.valueOf(numerator);
        BigInteger bigDenominator = BigInteger.valueOf(denominator);
        return canonical(bigNumerator, bigDenominator, true);
    }

    /**
     * @param value the parameter value
     * @param name  the parameter name
     * @return the BigInteger representation of the parameter
     * @throws NumberFormatException if value is not a valid representation of BigInteger
     */
    private static BigInteger requireBigInteger(String value, String name)
        throws NumberFormatException
    {
        try
        {
            return new BigInteger(value);
        }
        catch (NumberFormatException e)
        {
            throw (NumberFormatException) new NumberFormatException("Invalid " + name + ": " + value).
                initCause(e);
        }
    }

    /**
     * @param numerator   a numerator
     * @param denominator a denominator
     * @return a BigRational having value {@code numerator / denominator}
     * @throws NullPointerException     if numerator or denominator are null
     * @throws IllegalArgumentException if numerator or denominator are empty
     * @throws NumberFormatException    if numerator or denominator are not a valid representation of
     *                                  BigDecimal
     */
    public static BigRational valueOf(String numerator, String denominator)
        throws NullPointerException, IllegalArgumentException, NumberFormatException
    {
        Preconditions.requireThat(numerator, "numerator").isNotNull().isNotEmpty();
        Preconditions.requireThat(denominator, "denominator").isNotNull().isNotEmpty();
        BigInteger bigNumerator = requireBigInteger(numerator, "numerator");
        BigInteger bigDenominator = requireBigInteger(denominator, "denominator");
        return canonical(bigNumerator, bigDenominator, true);
    }

    /**
     * @param value a string representation of a rational fraction (e.g. "12.34e5" or "3/4")
     * @return a BigRational representation of the String
     * @throws NullPointerException     if value is null
     * @throws IllegalArgumentException if value is empty
     * @throws NumberFormatException    if numerator or denominator are not a valid representation of
     *                                  BigDecimal
     */
    public static BigRational valueOf(String value)
        throws NullPointerException, IllegalArgumentException, NumberFormatException
    {
        Preconditions.requireThat(value, "value").isNotNull().isNotEmpty();
        List<String> fractionParts = Splitter.on('/').splitToList(value);
        if (fractionParts.size() == 1)
            return valueOfRational(value);
        if (fractionParts.size() == 2)
            return BigRational.valueOf(fractionParts.get(0), fractionParts.get(1));
        throw new IllegalArgumentException("Too many slashes: " + value);
    }

    /**
     * @param value a string representation of a rational fraction (e.g. "12.34e5")
     * @return a BigRational representation of the String
     * @throws NullPointerException     if value is null
     * @throws IllegalArgumentException if value is empty
     * @throws NumberFormatException    if numerator or denominator are not a valid representation of
     *                                  BigDecimal
     */
    private static BigRational valueOfRational(String value)
        throws NullPointerException, IllegalArgumentException, NumberFormatException
    {
        Preconditions.requireThat(value, "value").isNotNull().isNotEmpty();
        BigDecimal bigDecimal = new BigDecimal(value);
        int scale = bigDecimal.scale();
        BigInteger numerator = bigDecimal.unscaledValue();
        BigInteger denominator;
        if (scale > 0)
            denominator = BigInteger.TEN.pow(scale);
        else
        {
            numerator = numerator.multiply(BigInteger.TEN.pow(-scale));
            denominator = BigInteger.ONE;
        }

        return canonical(numerator, denominator, true);
    }

    private final BigInteger numerator;
    private final BigInteger denominator;

    /**
     * @param numerator   the numerator
     * @param denominator the denominator
     * @throws NullPointerException if numerator or denominator are null
     */
    private BigRational(BigInteger numerator, BigInteger denominator)
    {
        Preconditions.requireThat(numerator, "numerator").isNotNull();
        Preconditions.requireThat(denominator, "denominator").isNotNull();
        this.numerator = numerator;
        this.denominator = denominator;
    }

    /**
     * @return the numerator
     */
    public BigInteger getNumerator()
    {
        return numerator;
    }

    /**
     * @return the denominator
     */
    public BigInteger getDenominator()
    {
        return denominator;
    }

    @Override
    @SuppressWarnings("AccessingNonPublicFieldOfAnotherObject")
    public int compareTo(BigRational other)
    {
        Preconditions.requireThat(other, "other").isNotNull();

        // canonical() ensures denominator is positive
        if (numerator.signum() != other.numerator.signum())
            return numerator.signum() - other.numerator.signum();

        // Set the denominator to a common multiple before comparing the numerators
        BigInteger first = numerator.multiply(other.denominator);
        BigInteger second = other.numerator.multiply(denominator);
        return first.compareTo(second);
    }

    /**
     * @param other another rational fraction
     * @return the result of adding this object to {@code other}
     * @throws NullPointerException if other is null
     */
    @SuppressWarnings("AccessingNonPublicFieldOfAnotherObject")
    public BigRational add(BigRational other)
    {
        Preconditions.requireThat(other, "other").isNotNull();
        if (other.numerator.signum() == 0)
            return this;
        if (numerator.signum() == 0)
            return other;
        if (denominator.equals(other.denominator))
            return new BigRational(numerator.add(other.numerator), denominator);
        return canonical(numerator.multiply(other.denominator).
            add(other.numerator.multiply(denominator)),
            denominator.multiply(other.denominator), true);
    }

    /**
     * @param other another rational fraction
     * @return the result of subtracting {@code other} from this object
     * @throws NullPointerException if other is null
     */
    @SuppressWarnings("AccessingNonPublicFieldOfAnotherObject")
    public BigRational subtract(BigRational other)
    {
        return add(other.negate());
    }

    /**
     * @param other another rational fraction
     * @return the result of multiplying this object by {@code other}
     * @throws NullPointerException if other is null
     */
    @SuppressWarnings("AccessingNonPublicFieldOfAnotherObject")
    public BigRational multiply(BigRational other)
    {
        Preconditions.requireThat(other, "other").isNotNull();
        if (numerator.signum() == 0 || other.numerator.signum() == 0)
            return ZERO;
        if (numerator.equals(other.denominator))
            return canonical(other.numerator, denominator, true);
        if (other.numerator.equals(denominator))
            return canonical(numerator, other.denominator, true);
        if (numerator.negate().equals(other.denominator))
            return canonical(other.numerator.negate(), denominator, true);
        if (other.numerator.negate().equals(denominator))
            return canonical(numerator.negate(), other.denominator, true);
        return canonical(numerator.multiply(other.numerator), denominator.multiply(other.denominator),
            true);
    }

    /**
     * @param other another rational fraction
     * @return the result of dividing this object by {@code other}
     * @throws NullPointerException if other is null
     */
    public BigRational divide(BigRational other)
    {
        return multiply(other.invert());
    }

    /**
     * @return true if the object is a whole number
     */
    public boolean isInteger()
    {
        return numerator.signum() == 0 || denominator.equals(BigInteger.ONE);
    }

    /**
     * Returns a BigRational whose value is (-this).
     * <p>
     * @return -this
     */
    public BigRational negate()
    {
        return new BigRational(numerator.negate(), denominator);
    }

    /**
     * @return a rational fraction with the numerator and denominator swapped
     */
    public BigRational invert()
    {
        return canonical(denominator, numerator, false);
    }

    /**
     * @return the absolute value of this {@code BigRational}
     */
    public BigRational abs()
    {
        if (numerator.signum() < 0)
            return negate();
        return this;
    }

    /**
     * @param exponent exponent to which both numerator and denominator is to be raised.
     * @return a BigRational whose value is (this<sup>exponent</sup>).
     */
    public BigRational pow(int exponent)
    {
        return canonical(numerator.pow(exponent), denominator.pow(exponent), true);
    }

    /**
     * @param other another rational fraction
     * @return the minimum of this object and the other fraction
     */
    public BigRational min(BigRational other)
    {
        if (compareTo(other) <= 0)
            return this;
        return other;
    }

    /**
     * @param other another rational fraction
     * @return the maximum of this object and the other fraction
     */
    public BigRational max(BigRational other)
    {
        if (compareTo(other) >= 0)
            return this;
        return other;
    }

    /**
     * @param scale        scale of the BigDecimal quotient to be returned
     * @param roundingMode the rounding mode to apply
     * @return a BigDecimal representation of this object
     * @throws NullPointerException if roundingMode is null
     */
    public BigDecimal toBigDecimal(int scale, RoundingMode roundingMode)
    {
        Preconditions.requireThat(roundingMode, "roundingMode").isNotNull();
        if (isInteger())
            return new BigDecimal(numerator);
        return new BigDecimal(numerator).divide(new BigDecimal(denominator), scale, roundingMode);
    }

    @Override
    public int intValue()
    {
        return (int) longValue();
    }

    @Override
    public long longValue()
    {
        if (isInteger())
            return numerator.longValue();
        return numerator.divide(denominator).longValue();
    }

    @Override
    public float floatValue()
    {
        return (float) doubleValue();
    }

    @Override
    public double doubleValue()
    {
        if (isInteger())
            return numerator.doubleValue();
        return numerator.doubleValue() / denominator.doubleValue();
    }

    @Override
    @SuppressWarnings("AccessingNonPublicFieldOfAnotherObject")
    public boolean equals(Object o)
    {
        if (this == o)
            return true;
        if (!(o instanceof BigRational))
            return false;
        BigRational other = (BigRational) o;

        return numerator.equals(other.denominator) && Objects.equals(denominator, other.denominator);
    }

    @Override
    public int hashCode()
    {
        return Objects.hash(numerator, denominator);
    }

    /**
     * Returns the String representation: {@code numerator / denominator}.
     */
    @Override
    public String toString()
    {
        if (isInteger())
            return String.format("%,d", numerator);
        return String.format("%,d / %,d", numerator, denominator);
    }
}
Gili
quelle
0

Erste Bemerkung:

Schreiben Sie niemals Folgendes:

if ( condition ) statement;

Das ist viel besser

if ( condition ) { statement };

Erstellen Sie einfach, um eine gute Angewohnheit zu erstellen.

Indem Sie die Klasse wie vorgeschlagen unveränderlich machen, können Sie auch das Double nutzen, um die Operationen equals und hashCode sowie compareTo auszuführen

Hier ist meine schnelle schmutzige Version:

public final class Fraction implements Comparable {

    private final int numerator;
    private final int denominator;
    private final Double internal;

    public static Fraction createFraction( int numerator, int denominator ) { 
        return new Fraction( numerator, denominator );
    }

    private Fraction(int numerator, int denominator) {
        this.numerator   = numerator;
        this.denominator = denominator;
        this.internal = ((double) numerator)/((double) denominator);
    }


    public int getNumerator() {
        return this.numerator;
    }

    public int getDenominator() {
        return this.denominator;
    }


    private double doubleValue() {
        return internal;
    }

    public int compareTo( Object o ) {
        if ( o instanceof Fraction ) { 
            return internal.compareTo( ((Fraction)o).internal );
        }
        return 1;
    }

    public boolean equals( Object o ) {
          if ( o instanceof Fraction ) {  
             return this.internal.equals( ((Fraction)o).internal );
          } 
          return false;
    }

    public int hashCode() { 
        return internal.hashCode();
    }



    public String toString() { 
        return String.format("%d/%d", numerator, denominator );
    }

    public static void main( String [] args ) { 
        System.out.println( Fraction.createFraction( 1 , 2 ) ) ;
        System.out.println( Fraction.createFraction( 1 , 2 ).hashCode() ) ;
        System.out.println( Fraction.createFraction( 1 , 2 ).compareTo( Fraction.createFraction(2,4) ) ) ;
        System.out.println( Fraction.createFraction( 1 , 2 ).equals( Fraction.createFraction(4,8) ) ) ;
        System.out.println( Fraction.createFraction( 3 , 9 ).equals( Fraction.createFraction(1,3) ) ) ;
    }       

}

Informationen zur statischen Factory-Methode können später hilfreich sein, wenn Sie den Bruch in Unterklassen unterteilen, um komplexere Aufgaben zu erledigen, oder wenn Sie einen Pool für die am häufigsten verwendeten Objekte verwenden.

Es kann sein, dass dies nicht der Fall ist, ich wollte nur darauf hinweisen. :) :)

Siehe Effektives erstes Java- Element.

OscarRyz
quelle
0

Könnte nützlich sein, um einfache Dinge wie Hin- und Herbewegung hinzuzufügen, den Rest zu erhalten und ganz zu werden.

Darth Joshua
quelle
Diese Antwort eignet sich als Kommentar.
Jasonw
Schreckliche Entschuldigung für die späte Antwort, aber ich glaube, es ist eine Mindestanzahl von Wiederholungen (50?) Erforderlich, um eine Antwort zu kommentieren, die ich nicht habe ...
Darth Joshua
0

Obwohl Sie über die Methoden compareTo () verfügen, sollten Sie auch Comparable implementieren, wenn Sie Dienstprogramme wie Collections.sort () verwenden möchten.

public class Fraction extends Number implements Comparable<Fraction> {
 ...
}

Für eine hübsche Anzeige empfehle ich außerdem, toString () zu überschreiben.

public String toString() {
    return this.getNumerator() + "/" + this.getDenominator();
}

Und schließlich würde ich die Klasse öffentlich machen, damit Sie sie aus verschiedenen Paketen verwenden können.

Kenny Cason
quelle
0

Diese Funktion zur Vereinfachung der Verwendung des Eukledian-Algorithmus ist beim Definieren von Brüchen sehr nützlich

 public Fraction simplify(){


     int safe;
     int h= Math.max(numerator, denominator);
     int h2 = Math.min(denominator, numerator);

     if (h == 0){

         return new Fraction(1,1);
     }

     while (h>h2 && h2>0){

          h = h - h2;
          if (h>h2){

              safe = h;
              h = h2;
              h2 = safe;

          }  

     }

  return new Fraction(numerator/h,denominator/h);

 }
Brennan
quelle
0

Für die branchenübliche Fraction / Rational-Implementierung würde ich sie so implementieren, dass sie NaN, positive Unendlichkeit, negative Unendlichkeit und optional negative Null mit einer Betriebssemantik darstellen kann, die genau den IEEE 754-Standardzuständen für Gleitkomma-Arithmetik entspricht (dies erleichtert auch die Umrechnung in / von Gleitkommawerten). Da der Vergleich mit Null, Eins und den oben genannten speziellen Werten nur einen einfachen, aber kombinierten Vergleich von Zähler und Nenner mit 0 und 1 erfordert, würde ich zur Vereinfachung der Verwendung mehrere isXXX- und compareToXXX-Methoden hinzufügen (z. B. eq0 () Verwenden Sie hinter den Kulissen den Zähler == 0 && Nenner! = 0, anstatt den Client mit einer nullwertigen Instanz vergleichen zu lassen. Einige statisch vordefinierte Werte (ZERO, ONE, TWO, TEN, ONE_TENTH, NAN usw.) sind ebenfalls nützlich. da sie an mehreren Stellen als konstante Werte erscheinen. Dies ist meiner Meinung nach der beste Weg.

Tiamin
quelle
0

Klassenfraktion:

     public class Fraction {
        private int num;            // numerator 
        private int denom;          // denominator 
        // default constructor
        public Fraction() {}
        // constructor
        public Fraction( int a, int b ) {
            num = a;
            if ( b == 0 )
                throw new ZeroDenomException();
            else
                denom = b;
        }
        // return string representation of ComplexNumber
        @Override
        public String toString() {
            return "( " + num + " / " + denom + " )";
        }
        // the addition operation
        public Fraction add(Fraction x){
            return new Fraction(
                    x.num * denom + x.denom * num, x.denom * denom );
        }
        // the multiplication operation
        public Fraction multiply(Fraction x) {
            return new Fraction(x.num * num, x.denom * denom);
        } 
}

Das Hauptprogramm:

    static void main(String[] args){
    Scanner input = new Scanner(System.in);
    System.out.println("Enter numerator and denominator of first fraction");
    int num1 =input.nextInt();
    int denom1 =input.nextInt();
    Fraction x = new Fraction(num1, denom1);
    System.out.println("Enter numerator and denominator of second fraction");
    int num2 =input.nextInt();
    int denom2 =input.nextInt();
    Fraction y = new Fraction(num2, denom2);
    Fraction result = new Fraction();
    System.out.println("Enter required operation: A (Add), M (Multiply)");
    char op = input.next().charAt(0);
    if(op == 'A') {
        result = x.add(y);
        System.out.println(x + " + " + y + " = " + result);
    }
BasmaSH
quelle