Java 中的分数简化

Question

我的任务是培养一个理性的班级。如果 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);
    }  
}

Answer 1

有趣的问题。下面是一些用最少的代码完成此操作的可执行代码：

/** @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);
}

Answer 2

你需要 GCD。要么像 Nathan 提到的那样使用 BigInteger，要么如果不能，使用你自己的 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，你可能应该创建一个新函数。只是让它变得更干净、更容易阅读。您也可以测试该功能。

Answer 3

作为参考，您实现的是原始减法 欧几里得算法计算最大公约数两个数字。

更快的版本是在循环中使用整数除法的余数，例如 % 而不是 -：

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。马特的答案显示了同一算法的递归版本。

Answer 4

您应该使此类不是静态方法的容器。这是一个骨架

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
    }
}

Answer 5

我使用了一个类似的 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 > 分子和分母。如果简化比率的分母等于 1，isInteger() 返回 true。

Answer 6

注意到这里的所有答案都没有提到欧几里得算法的迭代实现。

  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  

我像 @Bohemian 一样实现了验证测试，递归和迭代实现的工作原理相同，但是迭代方法更快。基准测试显示了很小的改进，但它是改进，总体来说，不要过多使用堆栈并完全依赖 Java VM 来优化其实现依赖，感觉更好。即使基准测试相同，我仍然会对迭代感觉更好，因为迭代更便携，而递归仅由我的主机 Java 优化，但在其他虚拟机上可能没有那么好优化。

基准测试结果（代码位于答案的底部）：

(100 000 000 iterations)
gcd recursive:  3113ms
gcd iterative:  3079ms
gcd BigInteger: 13672ms

符号：

我注意到的一个区别（除了性能之外）是符号的处理方式不同，手工实现的欧几里得算法gcdLong 和我的 gcdLongIterative 行为相同，但两者都与 BigInteger 不同，后者倾向于“保持”符号原样。看起来本质上 gcd 和 gcdLongIterative 可以返回负数，而 BigInteger 只会返回正数。

gcdLong and gcdLongIterative implementations:
 -4/-2   => 2/1
-10/200  => 1/-20
 10/-200 => 1/-20

BigInteger implementation tends to 'keep' the signs:
 -4/-2   => -2/-1
-10/200  => -1/20
 10/-200 => 1/-20

用于分数时的所有结果都是有效的，但如果您期望特定“样式”的数字，则值得考虑后处理标准化。

例如，如果首选 BigInteger 行为，那么仅返回绝对值就足够了，如下所示：

  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return Math.abs(a);
  }  

性能：

受 @Xabster 基准测试启发（来自 Java：获取最大公约数，哪种方法更好？）我将其扩展以测试所有 3 个实现，但在某些情况下，递归和迭代执行相同的操作在大多数情况下，迭代速度稍快一些。

基准测试代码：

import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class Test {
  
  private static final int BENCHMARK_ITERATIONS = 100000000; 
  

  public static long gcdLong(long a, long b) {
    return b == 0 ? a : gcdLong(b, a % b);
  }

  
  public static long gcdLongIterative(long a, long b) {
    long tmp;
    
    while (0 != b) {
      tmp = b;
      b   = a % b;
      a   = tmp;
    }
    
    return a;
  }  
  
  
  public static long gcdLongBigInteger(long a, long b) {
    return BigInteger.valueOf(a).gcd(BigInteger.valueOf((b))).longValue();
  }

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

  
  public static String asFractionGcdLongIterative(long a, long b) {
    long gcd = gcdLongIterative(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static String asFractionGcdLongBI(long a, long b) {
    long gcd = gcdLongBigInteger(a, b);
    return (a / gcd) + "/" + (b / gcd);
  }
  
  
  public static void test(String actual, String expected) {
    boolean match = expected.equals(actual);
    
    if (match) {
      System.out.println("Actual and expected match=" + expected);      
    } else {
      System.out.println("NO match expected=" + expected + " actual=" + actual);            
    }
  }
  
  
  public static class Values {
    public long   a;
    public long   b;
    public String expected;

    public Values(long a, long b, String expected) {
      this.a = a;
      this.b = b;
      this.expected = expected;
    }
  }
  
  
  public static void validityTest() {
    List<Values> vals = new LinkedList<Values>(Arrays.asList(
        new Values(500, 1000, "1/2"),
        new Values(17,  3,    "17/3"),
        new Values(462, 1071, "22/51"),
        new Values(-4,  -2,   "2/1"),
        new Values(-10, 200,  "1/-20"),
        new Values(10,  -200, "1/-20")
    ));
    
    System.out.println("------  Recursive implementation -------");
    vals.forEach(v -> test(asFractionGcdLong(v.a, v.b), v.expected));
    System.out.println();    
    
    System.out.println("------  Iterative implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongIterative(v.a, v.b), v.expected));
    System.out.println();    

    System.out.println("------  BigInteger implementation -------");    
    vals.forEach(v -> test(asFractionGcdLongBI(v.a, v.b), v.expected));
    System.out.println();    
  }

  
  public static void benchMark() {
    Random r = new Random();
    
    long[] nums = new long[BENCHMARK_ITERATIONS];
    for (int i = 0 ; i < nums.length ; i++) nums[i] = r.nextLong();

    System.out.println("Waming up for benchmark...");
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);

    System.out.println("Started benchmark...");
    long s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLong(i, i + 1);
    System.out.println("recursive:  " + (System.currentTimeMillis() - s) + "ms");

    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongIterative(i, i + 1);
    System.out.println("iterative:  " + (System.currentTimeMillis() - s) + "ms");    
    
    s = System.currentTimeMillis();
    for (int i = 0 ; i < nums.length-1; i++) gcdLongBigInteger(i, i + 1);
    System.out.println("BigInteger: " + (System.currentTimeMillis() - s) + "ms");    
  }
  
  
  public static void main(String[] args) {
    validityTest();
    benchMark();
  }
  
}