Eine Vampir-Nummer ist hier Ссылка definiert. Eine Zahl V ist eine Vampir-Nummer, wenn:
Ich habe eine Lösung gefunden,
%Vor%Eine andere mögliche Lösung besteht darin, die durch V repräsentierte Zeichenkette zu vertauschen und sie in zwei Hälften zu teilen und zu prüfen, ob es sich um eine Vampir-Nummer handelt. Welcher ist der beste Weg, dies zu tun?
Im Pseudocode:
%Vor%Es gibt eine Reihe von Optimierungen, die hier noch durchgeführt werden könnten, hauptsächlich um sicherzustellen, dass jedes mögliche Paar von Faktoren nur einmal versucht wird. Mit anderen Worten, wie überprüft man am besten die Wiederholungen bei der Auswahl von Permutationen?
Aber das ist der Kern des Algorithmus, den ich verwenden würde.
PS .: Sie suchen nicht nach Primzahlen, warum also einen Primzahltest? Es interessiert dich nur, ob es sich um Vampir Nummern handelt; Es gibt nur sehr wenige mögliche Faktoren. Keine Notwendigkeit, alle Zahlen bis zu sqrt (Nummer) zu überprüfen.
Der hier vorgeschlagene Algorithmus wird nicht alle Permutationen von Ziffern durchlaufen. Es wird Möglichkeiten so schnell wie möglich eliminieren, so dass nur ein Bruchteil von Permutationen tatsächlich getestet wird.
So funktioniert es anhand des Beispiels 125460. Wenn Sie den Code direkt lesen, können Sie diesen (langen) Teil überspringen:
Zuerst sind die zwei Zähne (d. h. Vampir-Faktoren) offensichtlich nicht bekannt, und das Problem kann wie folgt dargestellt werden:
%Vor% Für die linke Ziffer des ersten Faktors (markiert mit ? ) können wir eine der Ziffern 0,1,2,5,4 oder 6 wählen. Aber bei näherer Analyse wäre 0 keine praktikable Möglichkeit , da das Produkt niemals mehr als eine 5-stellige Nummer erreichen würde. Es wäre also eine Verschwendung von Zeit, alle Permutationen von Ziffern durchzugehen, die mit einer Null beginnen.
Für die linke Ziffer des zweiten Faktors (auch mit ? markiert) gilt das Gleiche. Wenn wir jedoch die Kombinationen betrachten, können wir wieder einige Paare herausfiltern, die nicht zum Erreichen des Zielprodukts beitragen können. Zum Beispiel sollte diese Kombination verworfen werden:
Die größte Zahl, die mit diesen Ziffern erreicht werden kann, ist 199x299 = 59501 (ohne die Tatsache, dass wir nicht einmal eine 9 haben), was nicht einmal die Hälfte der gewünschten Zahl ist. Also sollten wir die Kombination ablehnen (1, 2). Aus dem gleichen Grund kann das Paar (1, 5) verworfen werden, um diese Positionen einzunehmen. In ähnlicher Weise können die Paare (4, 5), (4, 6) und (5, 6) ebenso zurückgewiesen werden, da sie ein zu großes Produkt ergeben (& gt; = 200000). Ich nenne diese Art von Test - wo festgestellt wird, ob die Zielnummer für ein bestimmtes gewähltes Ziffernpaar, den "Reichweitentest", erreichbar ist.
In diesem Stadium gibt es keinen Unterschied zwischen dem ersten und dem zweiten Fangzahn, also sollten wir auch keine Paare untersuchen müssen, bei denen die zweite Ziffer kleiner ist als die erste, weil sie ein Paar spiegeln, das bereits untersucht worden wäre (oder abgelehnt).
Also von allen möglichen Paaren, die diese erste Position einnehmen könnten (es gibt 30 Möglichkeiten, 2 Ziffern aus einer Menge von 6 Ziffern zu nehmen), nur die folgenden 4 müssen untersucht werden:
%Vor%In einer ausführlicheren Schreibweise bedeutet dies, dass wir die Suche auf diese Zahlenmuster beschränken:
%Vor%Es ist klar, dass diese Reduzierung der Möglichkeiten, bevor man auch nur die anderen Positionen betrachtet, den Suchbaum stark reduziert.
Der Algorithmus wird jede dieser vier Möglichkeiten der Reihe nach angehen und für jeden die Möglichkeiten für die nächste Stelle prüfen. Also wird die erste Konfiguration A analysiert:
%Vor% Die Paare, die für die ? -markierten Positionen verfügbar sind, sind diese 12:
Auch hier können wir Paare eliminieren, indem wir den Bereichstest anwenden. Nehmen wir zum Beispiel das Paar (5, 4). Das würde bedeuten, dass wir die Faktoren 15 * und 64 * hatten (wobei * zu diesem Zeitpunkt eine unbekannte Ziffer ist). Das Produkt dieser beiden wird mit 159 * 649 maximiert, d. H. 103191 (wieder ignorierend die Tatsache, dass wir nicht einmal eine 9 verfügbar haben): Dies ist zu niedrig, um das Ziel zu erreichen, so dass dieses Paar ignoriert werden kann. Durch die weitere Anwendung des Reichweitentests können alle diese 12 Paare verworfen werden, so dass die Suche in der Konfiguration A hier aufhört: dort gibt es keine Lösung.
Dann bewegt sich der Algorithmus zu Konfiguration B:
%Vor%Erneut wird der Bereichstest auf die möglichen Paare für die zweite Position angewendet, und wieder stellt sich heraus, dass keines dieser Paare den Test besteht: zum Beispiel (5, 6) kann niemals ein größeres Produkt als 259 * 469 = darstellen 121471, was (nur gerade) zu klein ist.
Dann bewegt sich der Algorithmus zu Option C:
%Vor%Von allen 12 möglichen Paaren überleben nur die folgenden den Bereichstest: (4, 0), (4, 1), (6, 0), (6, 1). Jetzt haben wir die folgenden Konfigurationen der zweiten Ebene:
%Vor%In der Konfiguration Ca gibt es kein Paar, das den Bereichstest besteht.
In der Konfiguration Cb passiert das Paar (6, 0) und führt zu einer Lösung:
%Vor%An diesem Punkt stoppt der Algorithmus die Suche. Das Ergebnis ist klar. Insgesamt betrachtet ist die Anzahl der betrachteten Konfigurationen im Vergleich zu einem Brute-Force-Permutationsüberprüfungsalgorithmus sehr klein. Hier ist eine Visualisierung des Suchbaums:
%Vor% Die Varianten unter / dienen nur dazu, zu zeigen, was der Algorithmus sonst noch getan hätte, wenn keine Lösung gefunden worden wäre. Aber in diesem Fall wurde dieser Teil des Suchbaums eigentlich nie befolgt.
Ich habe keine klare Vorstellung von der zeitlichen Komplexität, aber es scheint für größere Zahlen ziemlich gut zu laufen, was zeigt, dass die Eliminierung von Ziffern in einem frühen Stadium die Breite des Suchbaums ziemlich schmal macht.
Hier ist eine Live-JavaScript-Implementierung, die auch einige Testfälle ausführt, wenn sie aktiviert ist (und sie hat ein paar andere Optimierungen - siehe Code-Kommentare).
Da JavaScript eine 64-Bit Gleitkommadarstellung verwendet, akzeptiert das obige Snippet nur Zahlen bis zu 2 53 -1. Oberhalb dieser Grenze würde es zu einem Verlust an Präzision und damit zu unzuverlässigen Ergebnissen kommen.
Da Python keine solche Einschränkung hat, habe ich auch eine Python-Implementierung auf eval.in installiert. Für diese Site gibt es eine Beschränkung der Ausführungszeiten. Sie müssen sie also woanders ausführen, wenn dies zu einem Problem wird.
Hier sind einige Vorschläge:
Zuerst eine einfache Verbesserung: wenn die Anzahl der Stellen & lt; 4 oder ungerade return false (oder wenn v auch negativ ist).
Sie müssen v nicht sortieren, es reicht aus zu zählen, wie oft jede Ziffer O (n) auftritt.
Sie müssen nicht jede Nummer prüfen, sondern nur die Kombinationen, die mit den Ziffern möglich sind. Dies kann durch Zurückverfolgen erfolgen und reduziert die Anzahl der zu überprüfenden Zahlen erheblich.
Die letzte Sortierung, um zu überprüfen, ob alle Ziffern verwendet wurden, wird ebenfalls nicht benötigt. Addieren Sie einfach die verwendeten Ziffern beider Zahlen und vergleichen Sie sie mit den Vorkommen in v .
Hier ist der Code für eine JS-ähnliche Sprache mit Ganzzahlen, die niemals überlaufen, der Parameter V ist eine Ganzzahl-Zeichenkette ohne führende 0s:
Bearbeiten: Wie sich herausstellt, ist der Code nicht nur JS wie , sondern auch gültiger JS-Code und es war kein Problem zu entscheiden, dass 1047527295416280 tatsächlich eine Vampirnummer ist ( jsfiddle ).
%Vor%Tags und Links algorithm numbers number-theory