Rechercher des paires GCD pour un tableau donné

Questions et réponses Java : La recherche de paires GCD d'un tableau donné est une question courante qui nécessite le calcul du plus grand diviseur commun (PGCD) des nombres du tableau. En Java, vous pouvez utiliser l'algorithme euclidien pour résoudre ce problème. Dans cet article, l'éditeur PHP Xigua présentera comment utiliser Java pour écrire une méthode permettant de trouver la paire GCD d'un tableau donné, aidant ainsi les lecteurs à mieux comprendre et appliquer cet algorithme.

Contenu de la question

Étant donné un tableau d'entiers de taille n, où n est un nombre pair. Choisissez 2 nombres dans le tableau et trouvez pgcd. De même, choisissez 2 éléments parmi les éléments restants du tableau et recherchez pgcd. Répétez les étapes ci-dessus pour trouver la paire pgcd. Additionnez les valeurs pgcd et obtenez la somme la plus élevée.

Contraintes :

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

Exemple 1 :

arr = [3,4,9,5]

Réponse :

4

Instructions :

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.

Exemple 2 :

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

Réponse :

6

Instructions :

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.

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

Mon code fonctionne pour le premier exemple mais donne un résultat erroné pour le deuxième exemple. Je l'ai débogué et j'ai constaté que la méthode que j'utilisais était incorrecte. Quelle est la bonne façon de résoudre ce problème ?

Solution

Nous pouvons rechercher de manière récursive toutes les façons possibles de calculer le pgcd total. ce qu'il faut faire?

Si le tableau ne contient que deux éléments, nous pouvons renvoyer le pgcd de ces deux éléments uniquement.

S'il en contient plus, parcourons toutes les paires de valeurs. Pour chaque paire, nous calculons son pgcd, et nous appelons également notre fonction de manière récursive avec une copie du tableau avec les deux valeurs supprimées. Si nous additionnons les résultats des deux calculs, nous obtenons le pgcd total pour la paire de valeurs actuellement sélectionnée.

Maintenant, nous gardons simplement une trace du meilleur gcd trouvé jusqu'à présent et le renvoyons à la fin.

C'est le code qui (devrait) faire exactement cela.

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

Cet algorithme est assez lent. Si vous avez besoin d'accélérer les choses, il y a au moins deux domaines dans lesquels vous pouvez vous améliorer :

• Le calcul de pgcd est une opération coûteuse. Précalculer le pgcd de toutes les paires de valeurs uniques possibles et les stocker dans une hashmap éliminera les doubles calculs.
• Il vérifie plusieurs fois certaines permutations possibles. (par exemple, sélectionner la première paire puis la deuxième paire lors de la récursion suivante revient à sélectionner la deuxième paire puis la première paire) J'ai quelques vagues idées sur la façon de résoudre ce problème, mais il est trop tard ce soir, désolé .

Il existe très probablement un algorithme plus rapide, c'est juste mon idée.

Editeur : Eh bien, après un peu de sommeil, j'ai soudain compris. Si nous omettons la boucle externe lors de la création de paires, nous n'obtiendrons aucun tri de paires en double. En gros, remplacez simplement i par 0 partout, comme ceci :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!