查找给定数组的 GCD 对

Java问答：查找给定数组的GCD对是一个常见问题，需要对数组中的数字进行最大公约数（GCD）的计算。在Java中，可以使用欧几里得算法来解决这个问题。在本篇文章中，php小编西瓜将介绍如何使用Java编写一个方法来查找给定数组的GCD对，帮助读者更好地理解和应用这一算法。

问题内容

给定一个大小为 n 的整数数组，其中 n 是偶数。从数组中选取 2 个数字并找到 gcd。同样，从数组中剩余的项中选取 2 项并找到 gcd。重复上述步骤找到 gcd 对。对 gcd 值求和并得到最高的总和。

约束：

n is in range 2 to 20
arr[i] is in range 1 to 10^9

示例 1：

arr = [3,4,9,5]

答案：

4

说明：

a) gcd of (4,5) is 1
b) gcd of (3,9) is 3
sum = 1+3 = 4. this is the highest possible gcd sum.

示例 2：

arr = [1,2,3,4,5,6]

答案：

6

说明：

a) gcd of (1,5) is 1
b) gcd of (2,4) is 2
c) gcd of (3,6) is 3
sum = 1+2+3 = 6. this is the highest possible gcd sum.

这是我的代码：

public static int solve(int[] ar) {
   int n = ar.length;
   Arrays.sort(ar);
   int sum = 0;
   for(int i=0; i<n/2; i++) {
     int a = ar.get(i), b = ar.get(n-i-1);
     int c = gcd(a,b); 
     sum += c;
   }
   return sum;
}

static int gcd(int a, int b)
{
    // if b=0, a is the GCD
    if (b == 0)
        return a;

    // call the gcd() method recursively by
    // replacing a with b and b with
    // modulus(a,b) as long as b != 0
    else
        return gcd(b, a % b);
}

我的代码适用于第一个示例，但为第二个示例提供了错误的输出。 我调试了一下，发现我使用的方法不正确。解决这个问题的正确方法是什么？

解决方法

我们可以递归搜索所有可能的方法来计算总 gcd。怎么办？

如果数组只包含两个元素，我们可以只返回这两个元素的 gcd。

如果它包含更多，让我们迭代所有值对。对于每一对，我们计算它的 gcd，并且我们还使用删除了两个值的数组副本递归调用我们的函数。如果我们将两个计算的结果相加，我们就会得到当前选择的值对的总 gcd。

现在我们只跟踪迄今为止找到的最佳 gcd，并在最后返回它。

这是（应该）完全做到这一点的代码。

int solve(int[] ar) {
  // if we have only two elements, there's not much else we can do.
  if(ar.length == 2) {
    return gcd(ar[0], ar[1]);
  }

  //keep track of the largest gcd
  int best = 0;
  
  // for every pair of values in the array
  //  make a copy of the array without the pair and call recursively
  for(int i = 0; i < ar.length; i++) {
    for(int j = i + 1; j < ar.length; j++) {
      
      int score = gcd(ar[i], ar[j]);
      
      // make a copy
      int[] ar2 = new int[ar.length - 2];
      int copy_k = 0;
      for(int k=0; k < ar.length; k++) {
        // skip values that we already visited
        if(k == i || k == j) {
          continue;
        }
        
        ar2[copy_k] = ar[k];
        copy_k += 1;
      }
      
      // call recursively
      score += solve(ar2);
      
      if(score > best) // we found a better pair
        best = score;
    }
  }
  
  return best;
}

这个算法相当慢。如果您需要加快速度，至少有两个方面可以改进：

• 计算 gcd 是一项昂贵的操作。 预先计算所有可能的唯一值对的 gcd 并将它们存储在哈希图中将消除双重计算。
• 它会多次检查一些可能的排列。 （例如，在下一次递归中选择第一对，然后选择第二对与选择第二对，然后选择第一对相同）我对如何解决这个问题有一些模糊的想法，但今天晚上太晚了，抱歉。

很可能存在更快的算法，这只是我的想法。

编辑：好吧，经过一番睡眠后，我突然明白了。如果我们在创建对时省略外循环，我们将不会得到任何重复的对排序。基本上只是在各处用 0 替换 i ，如下所示：

for(int j = 1; j < ar.length; j++) {
    
  int score = gcd(ar[0], ar[j]);
  
  // Make a copy
  int[] ar2 = new int[ar.length - 2];
  int copy_k = 0;
  for(int k=1; k < ar.length; k++) {
    // Skip values that we already visited
    if(k == j) {
      continue;
    }
    
    ar2[copy_k] = ar[k];
    copy_k += 1;
  }
}

以上是查找给定数组的 GCD 对的详细内容。更多信息请关注PHP中文网其他相关文章！