Comment trouver des triplets de pythagore dans un tableau plus vite que O(N^2)?

Quelqu'un peut-il suggérer un algorithme qui trouve tous les triplets de Pythagore parmi les nombres dans un tableau donné? Si c'est possible, s'il vous plaît, proposons un algorithme plus rapide que O(n2).

Triplet de pythagore est un ensemble {a,b,c} tels que a2 = b2 + c2. Exemple: pour le tableau [9, 2, 3, 4, 8, 5, 6, 10] la sortie de l'algorithme doit être {3, 4, 5} et {6, 8, 10}.

  • Qu'entendez-vous par "trouver des triplets de pythagore dans un tableau"? Êtes-vous commencer par un tableau d'entiers et d'essayer de trouver 3-l'élément de sous-ensembles que sont les triplets de Pythagore?
  • veuillez reformuler la question et de la rendre plus claire
  • la question n'est pas claire. peut-être, y compris un exemple de l'aide?
  • Désolé pour l'ambiguïté de la question. Je vais vous expliquer avec un exemple. Supposons que j'ai un tableau comme { 9,2, 3, 4, 8, 5,6, 10} puis mon algorithme doit générer la sortie 3, 4, 5 et 6, 8, 10 en O(n) la complexité ou inférieure à 0(n2)
  • Je sais que c'est un peu vieux mais si vous allez pour plus d'efficacité, vous pouvez organiser le tableau de haut en bas, et puis au moins réduire la liste vers le bas en veillant à ce que tous les candidats pour un est plus grand que b et c. De cette façon, si votre calculer chaque nombre avec des répétitions et vous avez 3 nombres dans un tableau, vous réduisez le nombre de chèques à partir de 27 à 2 :). Vous pouvez améliorer encore plus loin en ne permettant pas aux b et c du swap (Eg. b^2+c^2 = c^2+b^2), qui permettrait de réduire le nombre au-dessus de 1.
InformationsquelleAutor Supriya Sane | 2010-01-09