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：
#
答案：
說明：
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：
#
答案：
說明：
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 並將它們儲存在雜湊圖中將消除雙重計算。
- 它會多次檢查一些可能的排列。 （例如，在下一次遞歸中選擇第一對，然後選擇第二對與選擇第二對，然後選擇第一對相同）我對如何解決這個問題有一些模糊的想法，但今天晚上太晚了，抱歉。 < /em>
很可能有更快的演算法，這只是我的想法。
編輯：好吧，經過一番睡眠後，我突然明白了。如果我們在建立對時省略外循環，我們將不會得到任何重複的對排序。基本上只是在各處用 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中文網其他相關文章！
