упрощение дробей в Java - PullRequest
Новая
       94

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

20 голосов
/ 08 июля 2011

Моя задача - развить рациональный класс.Если 500 и 1000 мои входные данные, то (½) должны быть мои выходные данные.Я сам написал программу для ее поиска.

Есть ли другой лучший способ найти решение, или моя программа уже лучшая? 

public class Rational {

    public static void main(String[] args){

       int n1 = Integer.parseInt(args[0]);
       int n2 = Integer.parseInt(args[1]); 
       int temp1 = n1;
       int temp2 = n2; 

       while (n1 != n2){
         if(n1 > n2)
            n1 = n1 - n2;
         else
            n2 = n2 - n1;
       }      

      int n3 = temp1 / n1 ;
      int n4 = temp2 / n1 ;

      System.out.print("\n Output :\n");

      System.out.print(n3 + "/" + n4 + "\n\n" );
      System.exit(0);
    }  
}

Ответы [ 5 ]

41 голосов
/ 08 июля 2011

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

/** @return the greatest common denominator */
public static long gcm(long a, long b) {
    return b == 0 ? a : gcm(b, a % b); // Not bad for one line of code :)
}

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

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"
}
12 голосов
/ 08 июля 2011

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

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

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

Это даст вам неправильную дробь. Если вам нужна смешанная дробь, вы можете получить новые числа. Например, если у вас было 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. Просто делает его немного чище и легче для чтения. Вы также можете проверить эту функцию.

5 голосов
/ 08 июля 2011

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

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

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.Ответ Мэтта показывает рекурсивную версию того же алгоритма.

1 голос
/ 09 июля 2011

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

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
    }
}
0 голосов
/ 02 октября 2016

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

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.

...