Inspiriert von Cheap, Fast, Good werden wir einen Algorithmus implementieren, der genau zwei davon enthält.
Die Mathematik
Bei zwei Ganzzahlen ungleich Null a und b ist der GCF d die größte Ganzzahl, die a und b ohne Rest teilt . Bézout-Koeffizienten sind Paare von ganzen Zahlen (x, y), so dass ax + by = d ist . Bézout-Koeffizienten sind nicht eindeutig. Zum Beispiel gegeben:
a = 15, b = 9
Wir haben
d = 3
x = 2
y = -3
Seit 15*2 + 9*(-3) = 30 - 27 = 3
.
Eine übliche Methode zur Berechnung des GCF und eines Paares von Bézout-Koeffizienten ist die Verwendung des Euklid-Algorithmus , aber keineswegs die einzige.
Der Code
Ihr Programm sollte zwei Ganzzahlen als Eingaben verwenden. Es sollte den größten gemeinsamen Faktor und ein Paar Bézout-Koeffizienten ausgeben / zurückgeben.
Beispieleingabe:
15 9
Beispielausgabe
3 (2, -3)
Die Ausgabe kann in beliebiger Reihenfolge und in beliebigem Format erfolgen, es sollte jedoch klar sein, welches der GCF und welche die Koeffizienten sind.
Die Hinterhältigen
Ihr Programm hat das Potenzial, billig, schnell und gut zu sein. Leider können es nur zwei davon gleichzeitig sein.
- Wenn es nicht billig ist , sollte das Programm eine übermäßige Menge an Systemressourcen verwenden.
- Wenn es nicht schnell ist , sollte das Programm zu lange dauern.
- Wenn es nicht gut ist , sollte die Programmausgabe falsch sein.
Das Programm sollte in der Lage sein, alle drei zu erledigen (naja, nicht zu tun). Was ist, wenn es nach Ihnen geht - es könnte auf der Zeit, dem Compiler, der größeren Eingabe usw. basieren. Einige zusätzliche Hinweise:
- Ihr Programm sollte nicht offensichtlich hinterhältig sein und eine flüchtige Prüfung bestehen. Ich wäre etwas misstrauisch, wenn Sie drei separate Algorithmen implementieren würden.
- Im billigen Fall ist "übermäßige Menge an Systemressourcen" alles, was andere Programme verlangsamen würde. Es kann Speicher, Bandbreite usw. sein.
- Im schnellen Fall bedeutet "übermäßige Zeit" relativ dazu, wie es in den billigen und guten Fällen läuft . Das Programm sollte noch beendet sein. Je näher man "unglaublich frustrierend, aber nicht frustrierend genug, um das Programm zu stoppen" kommen kann, desto (lustiger und) besser.
- Im guten Fall sollte die Ausgabe nicht offensichtlich falsch sein und eine flüchtige Prüfung bestehen. Ich wäre sehr misstrauisch, wenn es mir einen GCF von "2 anna half" geben würde.
Dies ist ein Beliebtheitswettbewerb, daher gewinnen die meisten Upvotes!
BEARBEITEN
Zur Verdeutlichung suche ich nach Programmen, die in verschiedenen Fällen "schnell und billig" und "billig und gut" und "schnell und gut" sein können, nicht nach Programmen, die nur eines davon ausführen.
quelle
Antworten:
C.
Es ist billig und schnell. Sie erhalten gcd im Handumdrehen. Der Typ, der es tat, hatte jedoch keine Ahnung von diesem "Bézier-Co-Etwas", also teilte er einfach a und b durch gcd. (Um die Sache noch schlimmer zu machen, sind a und b zu diesem Zeitpunkt aufgrund des von ihm mit Bedacht gewählten Algorithmus ziemlich weit von ihrem Anfangswert entfernt)
quelle
C #
Dies berechnet die Bézout-Koeffizienten. Ich habe den Extended Euclidean Algorithmus verwendet .
quelle
Perl 5
Nicht billig: main () wird rekursiv aufgerufen (den Stapel füllen), bis eine Perl-Warnung "Deep Recursion" von Perl ausgelöst wird, die die Anwendung aufgrund des __WARN__ -Handlers beendet.
Nicht schnell: Wenn der gcf () -Algorithmus korrekte Ergebnisse zurückgibt, bleibt der Code nur einige Sekunden lang bestehen (select () in main ()).
Nicht gut: Alle Ergebnisse über 99 (oder unter -99) sind falsch.
Alles in allem nicht so kreativ; Ich freue mich auf elegantere Antworten.
quelle
Python
Dies ist billig und schnell, aber es ist schlecht, dass der Bereich auf den größten Eingang begrenzt ist, sodass möglicherweise kein Koeffizientenpaar gefunden wird.
Gutes Puzzle.
quelle
Javascript
Nicht billig
Verwendet viele Systemressourcen.
Nicht schnell
Verwenden Sie einen Rückruf als zusätzliche Ausfallsicherheit.
Nicht gut
Strikte Begrenzung von
gcf(10, 10)
, nur um Speicherplatz zu sichern.quelle