Problem
Finde alle Tripel aus positiven ganzen Zahlen a < b < c, für die a² + b² = c² und a + b + c = perimeter gilt. Gib jedes Tripel als [a, b, c] zurück, sortiert nach aufsteigendem a und dann b. Permutationen derselben Seiten dürfen nicht enthalten sein.
Implementiere pythagorean_triplets(perimeter).
Eingabe
perimeter: Die geforderte Summe aller drei Seiten.
Ausgabe
Gib eine Liste der Tripel in der angegebenen Reihenfolge zurück.
Einschränkungen
3 ≤ perimeter ≤ 100.000. Gib eine leere Liste zurück, falls kein Dreieck die Bedingungen erfüllt.
Beispiele
Eingabe:
perimeter = 30
Erwartete Ausgabe:
expected = [
[5, 12, 13]
]Eingabe:
long long perimeter = 30;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
{5, 12, 13}
};Eingabe:
long perimeter = 30;
Erwartete Ausgabe:
long[][] expected = new long[][] {
new long[] {5, 12, 13}
};Erläuterung
5 + 12 + 13 = 30 und 5² + 12² = 13². Dies ist das einzige passende Tripel.
Eingabe:
perimeter = 11
Erwartete Ausgabe:
expected = []Eingabe:
long long perimeter = 11;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {};Eingabe:
long perimeter = 11;
Erwartete Ausgabe:
long[][] expected = new long[][] {};Erläuterung
Kein streng wachsendes Tripel aus positiven ganzen Zahlen mit rechtwinkligem Dreieck ergibt die Summe 11.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Ein gültiges Tripel muss sowohl die pythagoreische Gleichung als auch die Umfangssumme erfüllen.
Hinweis 2
Nutze den Umfang, um die Suche einzugrenzen, statt jede Anordnung der Seiten auszuprobieren.
Hinweis 3
Behalte nur a < b < c und überspringe Duplikate durch symmetrische Seitenwahl.
Erwartete Komplexität
Zeit O(n^2), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.