Matematische Methode zum Vergleichen eines Paares von 3 Variablen

Ich erhielt den Auftrag, ein Paar von 3 positiven Doppelvariablen in Java zu vergleichen, während ich deren Reihenfolge ignorierte. Ich habe folgendes gemacht:

if ((a1 == a2 && b1 == b2 && c1 == c2) ||
    (a1 == a2 && b1 == c2 && c1 == b2) ||
    (a1 == b2 && b1 == a2 && c1 == c2) ||
    (a1 == b2 && b1 == c2 && c1 == a2) ||
    (a1 == c2 && b1 == a2 && c1 == b2) ||
    (a1 == c2 && b1 == b2 && c1 == a2))
    // if true

Ich habe vom Lehrer gehört, dass es eine mathematische Möglichkeit gibt, dieses Paar von 3 Zahlen zu vergleichen.

Bisher habe ich versucht, ihre Addition, Subtraktion und die Summe ihrer Potenzen um 2 zu vergleichen, aber ich habe immer einen Fall gefunden, in dem das Paar unterschiedlich war und die Aussage wahr war.

Irgendwelche Ideen?

BEARBEITEN:

Ich habe die Aufgabe bereits gesendet und der Lehrer sagte, dass meine Antwort wahr sei. Ich frage aus Neugier.

TL; DR

Vergleichen Sie die Summe jedes Tripletts, das Produkt jedes Tripletts und die Summe der Produkte aller möglichen Kombinationen jedes Tripletts.

The Nitty Gritty

Nach dem Fundamentalsatz der Algebra müssen wir für ein Polynom vom Grad N N Wurzeln haben.

Mit dieser Tatsache lassen wir unsere Nullen sein a1, a2, and a3. Nun finden wir die Koeffizienten dieses Polynoms.

(x - a1) * (x - a2) * (x - a3)
(x^2 - (a1 + a2) * x + a1a2) * (x - a3) 
x^3 - (a1 + a2) * x^2 + (a1a2) * x - a3 * x^2 + (a1a3 + a2a3) * x - a1a2a3

x^3 + (-1 * (a1 + a2 + a3)) * x^2 + (a1a2 + a1a3 + a2a3) * x + (-1 * a1a2a3)

Wenn zwei Polynome äquivalent sind, müssen sie dieselben Wurzeln haben (wiederum von der FTA). Wir müssen also nur die Koeffizienten der erzeugten Polynome vergleichen.

Also, wenn,

(-1 * (a1 + a2 + a3) == (-1 * (b1 + b2 + b3))
      ---equivalently---
a1 + a2 + a3 == b1 + b2 + b3

Und

(a1a2 + a1a3 + a2a3) == (b1b2 + b1b3 + b2b3)

Und

-1 * a1a2a3 == -1 * b1b2b3
      ---equivalently---
a1a2a3 == b1b2b3

Dann können wir die Drillinge schließen a1, a2, a3und b1, b2, b3sind äquivalent.

Lohnt es sich?

Aus praktischer Sicht wollen wir sehen, ob dies tatsächlich effizienter ist als die Brute-Force-Prüfung, wie sie vom OP dargestellt wird.

Erste Prüfung: Summe und Vergleich. Dies erfordert insgesamt 4 Ergänzungen und 1 Überprüfung auf Gleichheit.

Gesamt prüfen = 5; Laufende Summe = 5

Zweite Prüfung: Produkt, Summe und Vergleich. Dies erfordert 6 Gesamtmultiplikationen, 4 Gesamtadditionen und 1 Überprüfung auf Gleichheit.

Gesamt prüfen = 11; Laufende Summe = 16

Dritte Prüfung: Produkt und Vergleich. Dies erfordert 4 Gesamtmultiplikationen und 1 Überprüfung auf Gleichheit.

Gesamt prüfen = 5; Laufende Summe = 21

Addiert man die beiden logischen UND-Operationen, so erfordert die Gesamtzahl der Binäroperationen für die "Koeffizienten des generierten Polynomansatzes" nur:

23 binäre Operationen

Die Brute-Force-Prüfung erfordert 18 Gesamtgleichheitsprüfungen, 12 logische UND-Vergleiche und 5 logische ODER-Vergleiche für insgesamt:

35 binäre Operationen

Also, streng genommen , ist die Antwort ja, die „Koeffizienten des erzeugten Polynom - Ansatz“ ist in der Tat effizienter. Doch wie @WJS weist darauf hin, hat der Brute - Force - Ansatz viel mehr Möglichkeiten für Kurzschlüsse und damit ausführen wie / effizienter als der mathematische Ansatz.

Für vollständige Gründlichkeit

Wir können die Überprüfung der Summe der Produkte aller möglichen Kombinationen jedes Tripletts nicht überspringen. Wenn wir dies weglassen, gibt es unzählige Beispiele, bei denen dies fehlschlägt. Betrachten Sie (23, 32, 45)und (24, 30, 46)^* :

23 + 32 + 45 = 100
24 + 30 + 46 = 100

23 * 32 * 45 = 33120
24 * 30 * 46 = 33120

Sie sind nicht gleichwertig, geben aber die gleiche Summe und das gleiche Produkt. Sie geben jedoch nicht die gleiche Summe der Produkte aller möglichen Kombinationen an:

23 * 32 + 23 * 45 + 32 * 45 = 3211
24 * 30 + 24 * 46 + 30 * 46 = 3204

^* Wenn Sie neugierig sind, wie Sie ein ähnliches Beispiel wie oben ableiten können, generieren Sie zuerst alle ganzzahligen Partitionen einer ganzen Zahl M der Länge 3, nehmen Sie ihr Produkt, suchen Sie die Duplikate und wählen Sie ein Paar aus.

Wenn Sie sortieren dürfen (a1 <= b1 <= c1 und a2 <= b2 <= c2), versuchen Sie, 2 ^ a1 * 3 ^ b1 * 5 ^ c1 mit 2 ^ a2 * 3 ^ b2 * 5 ^ c2 zu vergleichen (unter Verwendung der Primzahlen 2, 3, 5 als Basis)