упрощение дробей в Java

Интересный вопрос. Вот некоторый исполняемый код, который делает это с минимальным кодом:

/** @return the greatest common denominator */
public static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b);
}

public static String asFraction(long a, long b) {
    long gcd = gcd(a, b);
    return (a / gcd) + "/" + (b / gcd);
}

// Some tests
public static void main(String[] args) {
    System.out.println(asFraction(500, 1000)); //  "1/2"
    System.out.println(asFraction(17, 3));     //  "17/3"
    System.out.println(asFraction(462, 1071)); //  "22/51"
}

Бонусные методы:

/** @return the lowest common multiple */
public static long lcm(long a, long b) {
    return a * b / gcd(a, b);
}

/** @return the greatest common denominator */
public static long gcd(List<? extends Number> numbers) {
    return numbers.stream().map(Number::longValue).reduce((a, b) -> gcd(a, b)).orElseThrow(NoSuchElementException::new);
}

/** @return the lowest common multiple */
public static long lcm(List<? extends Number> numbers) {
    return numbers.stream().map(Number::longValue).reduce((a, b) -> lcm(a, b)).orElseThrow(NoSuchElementException::new);
}

Вам нужен НОД. Либо используйте BigInteger, как упомянул Натан, либо, если вы не можете, используйте свой собственный.

public int GCD(int a, int b){
   if (b==0) return a;
   return GCD(b,a%b);
}

Затем вы можете разделить каждое число на НОД, как вы сделали выше.

Это даст вам неправильную дробь. Если вам нужна смешанная дробь, вы можете получить новые числа. Например, если у вас есть 1500 и 500 для входных данных, вы получите 3/2 в качестве ответа. Может быть, вы хотите 1 1/2. Таким образом, вы просто делите 3/2 и получаете 1, а затем получаете остаток от 3/2, который также равен 1. Знаменатель останется прежним.

whole = x/y;
numerator x%y;
denominator = y;

Если вы не верите мне, что это работает, вы можете проверить http://en.wikipedia.org/wiki/Euclidean_algorithm

Мне просто нравится рекурсивная функция, потому что она чистая и простая.

Ваш алгоритм близок, но не совсем корректен. Кроме того, вам, вероятно, следует создать новую функцию, если вы хотите найти gcd. Просто делает его немного чище и легче для чтения. Вы также можете протестировать эту функцию.

Для справки: вы внедрили исходный вычитающий евклидов алгоритм для вычислить наибольший общий делитель двух чисел.

Гораздо более быстрая версия использует остаток от целочисленного деления, например. % вместо - в вашем цикле:

while (n1 != 0 && n2 != 0){
  if(n1 > n2)
     n1 = n1 % n2;
  else
     n2 = n2 % n1;
}

... а затем убедитесь, что вы будете использовать тот, который не равен нулю.

Более упрощенная версия будет такой:

while(n1 != 0) {
   int old_n1 = n1;
   n1 = n2 % n1;
   n2 = old_n1;
}

а затем используйте n1. Ответ Мэтта показывает рекурсивную версию того же алгоритма.

Вы должны сделать этот класс чем-то отличным от контейнера для статических методов. Вот скелет

import java.math.BigInteger;
public class BigRational
{
    private BigInteger num;
    private BigInteger denom;
    public BigRational(BigInteger _num, BigInteger _denom)
    {
    //put the negative on top 
    // reduce BigRational using the BigInteger gcd method
    }
    public BigRational()
    {
        this(BigInteger.ZERO, BigInteger.ONE);
    }
    public BigRational add(BigRational that)
    {
    // return this + that;
    }

    .
    .
    .
    //etc
    }
}

У меня есть похожий класс BigRational, который я использую. GcdFunction использует функцию gcd BigInteger:

public class GcdFunction implements BinaryFunction {

    @Override
    public BigRational apply(final BigRational left, final BigRational right) {
        if (!(left.isInteger() && right.isInteger())) {
            throw new EvaluationException("GCD can only be applied to integers");
        }
        return new BigRational(left.getNumerator().gcd((right.getNumerator())));

    }

}

BigRational содержит BigInteger числитель и знаменатель. isInteger() возвращает значение true, если знаменатель упрощенного соотношения равен 1.