Zerlegen Sie ein Polynom ohne Verwendung integrierter Factoring- / Polynomfunktionen vollständig in irreduzible Zahlen über die ganzen Zahlen oder ein endliches Feld.
Eingang
Ihr Programm / Ihre Funktion erhält eine Primzahl (oder Null) n
als Eingabe. Das Feld / Ring ist das finite Feld dieser Reihenfolge (dh Z/nZ
), oder einfach nur , Z
wenn n
ist 0
. Ihr Programm kann fehlschlagen, wenn n
es nicht 0
oder eine Primzahl ist. Das Polynom wird in sein F[x]
.
Ihr Programm / Ihre Funktion erhält auch das Polynom als Eingabe.
Die Eingabe ist flexibel. Geben Sie unbedingt an, wie Sie Eingaben erhalten möchten. Zum Beispiel könnte das Polynom als eine Liste von Koeffizienten oder in der Form eingegeben werden, die die meisten Leute erwarten (z. B. 50x^3 + x^2
), oder in einer anderen vernünftigen Form. Oder das Format der Eingabe des Feldes / Rings kann auch unterschiedlich sein.
Ausgabe
Ihr Programm / Ihre Funktion gibt das vollständig faktorisierte Polynom aus. Sie können mehrere Wurzeln erweitert lassen (dh (x + 1)(x + 1)
anstelle von (x + 1)^2
). Sie können Leerzeichen zwischen Binäroperatoren entfernen. Sie können die Gegenüberstellung durch ersetzen *
. Sie können an seltsamen Stellen Leerzeichen einfügen. Sie können die Faktoren in beliebiger Reihenfolge neu anordnen. Der x
Begriff könnte einfach sein (x)
. x
kann geschrieben werden als x^1
; Der konstante Term kann jedoch nicht haben x^0
. Fremdzeichen +
sind zulässig. Möglicherweise haben Sie keine Klausel mit einem 0
vorne, sie müssen weggelassen werden. Der führende Term jedes Faktors muss positiv sein, negative Vorzeichen müssen außerhalb liegen.
In Testfällen sollte Ihr Programm in der Lage sein, in angemessener Zeit (z. B. <= 2 Stunden) für jeden dieser Fälle eine Ausgabe zu erstellen:
Eingang: 2, x^3 + x^2 + x + 1
Ausgabe: (x + 1)^3
Eingang: 0, x^3 + x^2 + x + 1
Ausgabe: (x + 1)(x^2 + 1)
Eingang: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30
Ausgabe: (3x + 2)(2x - 5)(x^2 + 3)
Eingang: 5, x^4 + 4x^3 + 4x^2 + x
Ausgabe: x(x + 4)(x + 4)(x + 1)
Eingang: 0, x^5 + 5x^3 + x^2 + 4x + 1
Ausgabe: (x^3 + 4x + 1)(x^2 + 1)
Besonderer Dank geht an Peter Taylor für die Kritik meiner Testfälle
p
hat die Elemente{0, 1, ... , p-1}
und befindet sich unter Addition / Multiplikation modp
. Reduziere im Grunde genommen jeden Koeffizienten um Modp
und du bist gut. Beachten Sie auch, dass , wenn es eine Wurzel hat, dh linearen Faktor, von{0, ... , p-1}
produzieren0
(modp
) , wenn es in das Polynom gesteckt.Z
besteht darin,Z/pZ
einen geeignetenp
und dann Hensel-Lift zu berücksichtigen . Der golffähige Ansatz ist jedoch wahrscheinlich (und dies ist sicherlich der Weg, den ich betrachte), eine einfache Grenze für die Höhe der Faktoren zu verwenden und sie brutal zu erzwingen.Antworten:
GolfScript (222 Bytes)
Online-Demo
Anmerkungen
n
folgt ein GolfScript-Array mit Koeffizienten von den höchsten bis zu den niedrigsten Werten. ZB0, x^5 + 5x^3 + x^2 + 4x + 1
sollte formatiert sein als0 [1 0 5 1 4 1]
.Z
. IchZ
gehe damit um, indem ich eine entspannte Form von Mignottes Höhenband benutze. Eine großartige Abhandlung über Größenbeschränkungen beim Factoring ist Bounds on Factors in Z [x] , John Abbott, 2009 (Link ist zum Vorabdruck von arxiv; sein Lebenslauf besagt, dass er vom Journal of Symbolic Computation akzeptiert wurde ). Die entspannteste Form gibt es in Bezug auf die L-2-Norm, aber um Bytes zu sparen, entspanne ich mich weiter und verwende stattdessen die L-1-Norm. Dann ist es ein Fall von Brute Forcing durch Prozessabteilung.Z
ist jedoch nur ein Ring und daher ist es notwendig, eine Testdivision durch nicht-monische Kandidatenfaktoren durchzuführen. Es gelingt mir, keine rationalen Zahlen zu implementieren, indem ich einen Leitfaktor-Divisionstest durchführe und ein "Fehler" -Flag anhäufee
.Z
Allgemeinen langsamer ist und nicht mit der Online-Demo getestet werden kann. Der langsamste der offiziellen Testfälle dauert jedoch 10 Minuten, was deutlich innerhalb des "angemessenen" Zeitlimits liegt.quelle