尋找給定數組的 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中文網其他相關文章！