在没有递归 while/for 循环的情况下使用 Java 流查找最大公约数

Question

请帮帮我。我需要将以下代码转换为使用 Java 流的代码。使用的方法是欧氏算法

public int gcd(int m, int n) {
    if (n == 0) {
        return m;
    } else {
        return gcd(n, m%n);
    }

我已经尝试通过以下方式使用流，但是递归是不允许的，我一直在尝试想出一种没有递归和循环的方法，因为我我对声明式方法还很陌生

return IntStream.of(m, n).reduce(0, (x, y) -> gcd(n, m-n));

Answer 1

只需遍历从 1 到两者中最小值的所有值。然后找到最大的一个将两者分开。

int gcd = IntStream.rangeClosed(1,Math.min(Math.abs(a),Math.abs(b)))
         .filter(r->a%r == 0 && b%r == 0)
         .max()
         .getAsInt();

a = 72;
b = 48;

gcd = 24;

请注意，由于您最终要除以 1，因此总会有一个答案，因此您可以安全地获得可选值。如果 gcd 是 1 那么数字是 relatively prime

这是非常低效的。坚持使用迭代欧几里得方法。

Answer 2

欧几里德算法的几乎逐字实现，您以流为例：

int gcd(int m, int n) {
    return Stream.iterate(new int[]{m, n}, vals -> new int[] {vals[1], vals[0] % vals[1]}).filter(v -> v[1] == 0).findFirst().get()[0];
}

它使用函数式编程中的 accumulator concept。

PS 交换数组中的值以避免每次都创建一个新数组会更有效，但即使使用这个新数组，它也比另一个答案中提供的蛮力算法更有效。

Answer 3

由于您仍在学习并提到从递归转换为迭代的能力，我冒昧地实施了目前想到的所有三个选项。方法的名称足够直观，但信息多总比少好：

gcdStream - 使用流实现。受到 here

的启发

gcdRecursive - 是基于递归的classic算法，你也用过

gcdIterative - 是将递归算法转换为迭代算法（通常使用 while 循环进行转换）

gcdStream - 使用流的实现。 Imo 是 classic 算法到基于流的最接近的转换。很高兴它使用模运算符进行迭代，所以它应该有更少的迭代然后线性

gcdStreamPair - 虽然每一个都起作用，但我觉得 gcdStream 有点冗长。因此，我研究了各种选项以使其更具可读性。用不可变的 Pair class 替换数组使其更具可读性。请参阅代码示例中的实现。

以这种方式研究方法 gcdRecursive -> gcdIterative -> gcdStream 翻译应该感觉很自然。

我把所有的方法都放在了一个UT里，通常你可以直接使用它。

import org.junit.jupiter.api.Test;
import java.util.stream.Stream;
import static org.junit.jupiter.api.Assertions.*;

public class GcdStreams {

   @Test
   public void t() {
       int a = 72, b = 48, expectedGcd = 24;

       assertEquals(expectedGcd, gcdStream(a,b));
   }

   private int gcdRecursive(int a, int b) {
       if (b == 0) {
           return a;
       } else {
           return gcd(b, a % b);
       }
   }

   private int gcdIterative(int a, int b) {
      do {
          int first = a;
          a = b;
          b = first % b;
      } while (b != 0);

      return a;
   }

   private int gcdStream(int a, int b) {
         return Stream.iterate(new int[] {a, b}, n -> new int[]{n[1], n[0] % n[1]})
                      .filter(x -> x[1] == 0)
                      .findFirst()
                      .map(x -> x[0])
                      .get();
   }

   private int gcdStreamPair(int a, int b) {
    return Stream.iterate(new Pair(a, b) , n -> new Pair(n.b, n.a % n.b))
                 .filter(x -> x.b == 0)
                 .findFirst()
                 .map(x -> x.a)
                 .get();
    }

    private class Pair {
        final int a,b;
        public Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

在没有递归 while/for 循环的情况下使用 Java 流查找最大公约数

Finding the Greatest Common Divisor using Java Stream without recursion while/for loops

java

algorithm

greatest-common-divisor

java-8

java-stream