Finden Sie GCD-Paare für ein bestimmtes Array

Java-Fragen und Antworten: Das Finden von GCD-Paaren eines bestimmten Arrays ist eine häufige Frage, die die Berechnung des größten gemeinsamen Teilers (GCD) der Zahlen im Array erfordert. In Java können Sie dieses Problem mit dem euklidischen Algorithmus lösen. In diesem Artikel stellt der PHP-Editor Xigua vor, wie man mit Java eine Methode schreibt, um das GCD-Paar eines bestimmten Arrays zu finden, und hilft den Lesern, diesen Algorithmus besser zu verstehen und anzuwenden.

Frageninhalt

Gegeben sei ein ganzzahliges Array der Größe n, wobei n eine gerade Zahl ist. Wählen Sie 2 Zahlen aus dem Array aus und finden Sie gcd. Wählen Sie ebenfalls zwei Elemente aus den verbleibenden Elementen im Array aus und suchen Sie nach gcd. Wiederholen Sie die obigen Schritte, um das gcd-Paar zu finden. Summieren Sie die gcd-Werte und erhalten Sie die höchste Summe.

Einschränkungen:

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

Beispiel 1:

arr = [3,4,9,5]

Antwort:

4

Anleitung:

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.

Beispiel 2:

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

Antwort:

6

Anleitung:

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.

Das ist mein Code:

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);
}

Mein Code funktioniert für das erste Beispiel, liefert aber für das zweite Beispiel eine falsche Ausgabe. Ich habe es debuggt und festgestellt, dass die von mir verwendete Methode falsch war. Was ist der richtige Weg, dieses Problem zu lösen?

Lösung

Wir können alle möglichen Wege rekursiv durchsuchen, um den gesamten gcd zu berechnen. was zu tun?

Wenn das Array nur zwei Elemente enthält, können wir den gcd nur dieser beiden Elemente zurückgeben.

Wenn es mehr enthält, iterieren wir über alle Wertepaare. Für jedes Paar berechnen wir seinen gcd und rufen unsere Funktion auch rekursiv mit einer Kopie des Arrays auf, wobei beide Werte entfernt wurden. Wenn wir die Ergebnisse beider Berechnungen addieren, erhalten wir den gesamten gcd für das aktuell ausgewählte Wertepaar.

Jetzt behalten wir einfach den Überblick über den besten bisher gefundenen gcd und geben ihn am Ende zurück.

Dies ist der Code, der genau das tun (sollte).

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;
}

Dieser Algorithmus ist ziemlich langsam. Wenn Sie die Dinge beschleunigen müssen, gibt es mindestens zwei Bereiche, in denen Sie sich verbessern können:

• Die Berechnung des gcd ist ein teurer Vorgang. Durch die Vorabberechnung des gcd aller möglichen eindeutigen Wertepaare und deren Speicherung in einer Hashmap werden Doppelberechnungen vermieden.
• Es prüft einige mögliche Permutationen mehrmals. (z. B. ist die Auswahl des ersten Paares und dann des zweiten Paares bei der nächsten Rekursion dasselbe wie die Auswahl des zweiten Paares und dann des ersten Paares) Ich habe einige vage Ideen, wie ich dieses Problem lösen kann, aber heute Abend ist es zu spät. Tut mir leid .

Höchstwahrscheinlich gibt es einen schnelleren Algorithmus, das ist nur meine Idee.

Herausgeber: Nun, nach etwas Schlaf habe ich es plötzlich verstanden. Wenn wir beim Erstellen von Paaren die äußere Schleife weglassen, erhalten wir keine doppelte Sortierung von Paaren. Ersetzen Sie einfach überall i durch 0, so:

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;
  }
}

Das obige ist der detaillierte Inhalt vonFinden Sie GCD-Paare für ein bestimmtes Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!