Ich bin bei Glassdoor auf diese Frage gestoßen und habe versucht, sie umzusetzen. Die Frage ist wie folgt -
Betrachte eine Zahl 123, das Produkt der Zahl mit seinen Ziffern (123 * 1 * 2 * 3 = 738) ist 738. Daher ist 123 der Grundstamm von 738. Schreibe ein Programm, um eine Zahl zu akzeptieren und alle zu finden mögliche Samenwurzeln. Wenn der Benutzer beispielsweise 4977 eingegeben hat, sollte die Antwort 79 und 711 lauten.
Ich dachte an einen Weg:
Finden Sie alle Ziffern von 2 bis 9, die die Zahl teilen.
Beginnen Sie dann mit der größten Ziffer (unter den in Schritt 1 gefundenen Ziffern) und suchen Sie die Zahlen, aus denen die Zahl besteht, und drucken Sie dann alle Permutationen dieser Zahlen.
Aber das setzt voraus, dass die Ziffern nicht wiederholt werden, und zweitens druckt es nicht alle Zahlen wie für 4977 kann es 79 finden, wird aber 711 nicht finden.
Gibt es einen besseren Ansatz?
Mein Ansatz wäre so etwas. Es ist ein rekursiver Algorithmus, der eine Menge S verwendet, die ein Multiset ist, das Ziffern von 2 bis 9 enthält, möglicherweise mehrere Male.
%Vor%dann für die ursprüngliche Nummer
%Vor%Ich denke, das wird funktionieren, aber ich habe vielleicht einige Grenzfälle übersehen.
Bei 4977 findet try(4977, empty, 9) , dass 4977 durch 9 teilbar ist, also ruft es try(553, {9}, 9) auf. Die innere try findet 553 ist teilbar durch 7, und 553/7 = 79; an diesem Punkt S '= {7, 9} und der Algorithmus überprüft, ob 79 aus den Ziffern {7, 9} besteht, was erfolgreich ist. Der Algorithmus läuft jedoch weiter. Schließlich werden wir zurück zum äußeren try gehen, was zu einem bestimmten Zeitpunkt d = 7 und 4977/7 = 711 versuchen wird, und wenn wir die Überprüfung durchführen, ist S '= {7} und 711 besteht aus 7 mit einigen 1, also auch eine Antwort.
BEARBEITEN: Ich habe eine vollständige C ++ Funktion hinzugefügt:
%Vor%Eine andere Lösung besteht darin, jeden Teiler von n zu prüfen und zu prüfen, ob dies ein Seed sein könnte. Um alle Teiler zu überprüfen, müssen Sie nur die Quadratwurzel von n überprüfen. Also läuft dieser Algorithmus in O (sqrt (n)). Könntest du es schneller machen?
Hier ist ein einfaches C ++ Programm, das diese Idee demonstriert.
%Vor%Finden Sie zuerst alle Möglichkeiten, um die Nummer zu faktorisieren:
100 - 2 * 50 - 4 * 25 - 2 * 2 * 25 - ... und so weiter ... - 2 * 2 * 5 * 5
Wenn die Zahl 1 Ziffern enthält, fügen Sie einige Faktoren hinzu:
Führe all diese Faktorisierungen durch und sieh nach, ob einige davon die richtige Form haben.
Die "richtige Form" ist eine Faktorisierung, die einen Faktor hat, der die gleiche Anzahl von Stellen hat wie die Anzahl der Faktoren (weniger eins) und diese anderen Faktoren entsprechen den Ziffern
Dies schlägt eine Möglichkeit vor, die Faktorisierungen so zu filtern, wie Sie sie finden, sobald Sie
gefunden habendiese Faktorisierung kann nicht funktionieren.
Hier ist ein Link zu einigen Möglichkeiten, eine Nummer zu faktorisieren: Ссылка
Hier ist ein Code, der das tut. Kein Versprechen, in allen Fällen korrekt zu sein. Brute Force verwendet zu faktorisieren und einige Filter, um den Prozess kurzzuschließen, wenn es nicht funktioniert.
%Vor%Eine andere Lösung besteht darin, jeden Teiler von n zu prüfen und zu prüfen, ob dies ein Seed sein könnte. Um alle Teiler zu überprüfen, müssen Sie nur die Quadratwurzel von n überprüfen. Also läuft dieser Algorithmus in O (sqrt (n)). Könntest du es schneller machen?
Hier ist ein einfaches C ++ Programm, das diese Idee demonstriert.
%Vor% Hier ist ein einfaches Programm. Unter 1 Sekunde, um die Basis von 176852740608 zu erhalten. Live-Demo .
Update: Es dauert 27 Sekunden, um 376.352.349 zu finden - & gt; 153 642 082 955 760. Was ist mit euch Leute? Ich habe keine Ahnung, ob das gut ist oder nicht.
Update2: @ajb hat eine schnellere Antwort, zumindest bei den Experimenten, die ich gemacht habe. Aber diese Antwort hat den Vorteil, einfacher zu sein!
%Vor%Ich bin bei Glassdoor auf diese Frage gestoßen und habe versucht, sie umzusetzen. Die Frage ist wie folgt -
Betrachte eine Zahl 123, das Produkt der Zahl mit seinen Ziffern (123 * 1 * 2 * 3 = 738) ist 738. Daher ist 123 der Grundstamm von 738. Schreibe ein Programm, um eine Zahl zu akzeptieren und alle zu finden mögliche Samenwurzeln. Wenn der Benutzer beispielsweise 4977 eingegeben hat, sollte die Antwort 79 und 711 lauten.
Ich dachte an einen Weg:
Finden Sie alle Ziffern von 2 bis 9, die die Zahl teilen.
Beginnen Sie dann mit der größten Ziffer (unter den in Schritt 1 gefundenen Ziffern) und suchen Sie die Zahlen, aus denen die Zahl besteht, und drucken Sie dann alle Permutationen dieser Zahlen.
Aber das setzt voraus, dass die Ziffern nicht wiederholt werden, und zweitens druckt es nicht alle Zahlen wie für 4977 kann es 79 finden, wird aber 711 nicht finden.
Gibt es einen besseren Ansatz?
Mein Ansatz wäre so etwas. Es ist ein rekursiver Algorithmus, der eine Menge S verwendet, die ein Multiset ist, das Ziffern von 2 bis 9 enthält, möglicherweise mehrere Male.
%Vor%dann für die ursprüngliche Nummer
%Vor%Ich denke, das wird funktionieren, aber ich habe vielleicht einige Grenzfälle übersehen.
Bei 4977 findet %code% , dass 4977 durch 9 teilbar ist, also ruft es %code% auf. Die innere %code% findet 553 ist teilbar durch 7, und 553/7 = 79; an diesem Punkt S '= {7, 9} und der Algorithmus überprüft, ob 79 aus den Ziffern {7, 9} besteht, was erfolgreich ist. Der Algorithmus läuft jedoch weiter. Schließlich werden wir zurück zum äußeren %code% gehen, was zu einem bestimmten Zeitpunkt %code% und 4977/7 = 711 versuchen wird, und wenn wir die Überprüfung durchführen, ist S '= {7} und 711 besteht aus 7 mit einigen 1, also auch eine Antwort.
BEARBEITEN: Ich habe eine vollständige C ++ Funktion hinzugefügt:
%Vor%Finden Sie zuerst alle Möglichkeiten, um die Nummer zu faktorisieren:
100 - 2 * 50 - 4 * 25 - 2 * 2 * 25 - ... und so weiter ... - 2 * 2 * 5 * 5
Wenn die Zahl 1 Ziffern enthält, fügen Sie einige Faktoren hinzu:
Führe all diese Faktorisierungen durch und sieh nach, ob einige davon die richtige Form haben.
Die "richtige Form" ist eine Faktorisierung, die einen Faktor hat, der die gleiche Anzahl von Stellen hat wie die Anzahl der Faktoren (weniger eins) und diese anderen Faktoren entsprechen den Ziffern
Dies schlägt eine Möglichkeit vor, die Faktorisierungen so zu filtern, wie Sie sie finden, sobald Sie
gefunden habendiese Faktorisierung kann nicht funktionieren.
Hier ist ein Link zu einigen Möglichkeiten, eine Nummer zu faktorisieren: Ссылка
Hier ist ein Code, der das tut. Kein Versprechen, in allen Fällen korrekt zu sein. Brute Force verwendet zu faktorisieren und einige Filter, um den Prozess kurzzuschließen, wenn es nicht funktioniert.
%Vor%Weniger als 1 Sekunde für 176852740608. Suchen Sie nach allen Faktoren und prüfen Sie dann, ob ein bestimmter Faktor der Grundstamm ist oder nicht.
%Vor%Weniger als 1 Sekunde für 176852740608. Suchen Sie nach allen Faktoren und prüfen Sie dann, ob ein bestimmter Faktor der Grundstamm ist oder nicht.
%Vor%Tags und Links algorithm