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.
这是我的代码：
具有服装类网店的常用的功能和完善的商品类型管理、商品管理、配送支付管理、订单管理、会员分组、会员管理、查询统计和多项商品促销功能。系统具有静态HTML生成、UTF-8多语言支持、可视化模版引擎等技术特点，适合建立服装、鞋帽、服饰类网店。系统具有以下主要功能模块： 网站参数设置 - 对网站的一些参数进行个性化定义 会员类型设置 - 可以任意创建多个会员类型，设置不同会员类型的权限和价格级别 货币类型
public static int solve(int[] ar) {
int n = ar.length;
Arrays.sort(ar);
int sum = 0;
for(int i=0; i
我的代码适用于第一个示例，但为第二个示例提供了错误的输出。
我调试了一下，发现我使用的方法不正确。解决这个问题的正确方法是什么？
解决方法
我们可以递归搜索所有可能的方法来计算总 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;
}
}
