Iteratives Querprodukt < Praxis < Informatik < Vorhilfe
|
Hallo liebe Gemeinde,
wenn ich das Querprodukt einer Zahl bilde, erhalte ich eine neue Zahl, aus der ich nun wieder das Querprodukt bilde. Nach einer bestimmten Anzahl von Schritten komme ich auf eine einstellige Zahl.
Die Anzahl der Schritte wird als multiplikative Ziffernwurzel der Zahl bezeichnet. Öfters auch als Beharrlichkeit einer Zahl bezeichnet.
Ich soll nun einen schnellen Algorithmus entwickeln, der die kleinstmögliche Zahl findet, bei der man 11 Schritte benötigt. Das Ergebnis findet sich bei Wikipedia und ist 277777788888899 (iteratives Querprodukt).
Ich habe nun ein Programm geschrieben, welches alle Zahlen, beginnend bei 10 durchgeht und die Ziffernwurzel sucht. Dabei gibt es die Ziffernwurzel aus und die zugehörige kleinstmögliche Zahl.
Hier mal die Ausgabe, damit ihr wisst, um was es geht.
table init: 0.002 sec
1: 10 (0.004 sec)
2: 25 (0.004 sec)
3: 39 (0.004 sec)
4: 77 (0.004 sec)
5: 679 (0.004 sec)
6: 6788 (0.005 sec)
7: 68889 (0.01 sec)
8: 2677889 (0.056 sec)
9: 26888999 (0.435 sec)
10: 3778888999 (49.025 sec)
Ich schreibe die Querprodukte erst mal in eine Tabelle und fange dann an zu testen. Die kleinstmögliche Zahl mit der multiplikativen Ziffernwurzel 10 wird bei mir nach etwa 50 Sekunden gefunden. War schon ziemlich froh darüber, weil die Tabellenlösung gegenüber der Lösung ohne Tabelle etwa 3mal schneller ist.
Die kleinstmögliche Zahl mit der multiplikativen Ziffernwurzel 11 wird bei mir auch nach einigen Stunden nicht gefunden. Ist halt nicht so schnell, der I7-Prozessor.
Jetzt kommt also meine Frage:
Gibt es eine Methode, diese kleinstmöglichen Zahlen schneller zu finden?
Eine Optimierung habe ich schon eingebaut: Wenn eine Ziffer 0 ist, ist das Ergebnis 0 und ich brauche mit dem Querprodukt nicht mehr weiter zu machen.
Heute hat mir nämlich jemand gesagt, dass die multiplikative Ziffernwurzel 10 sich auf einem handelsüblichen Laptop bereits nach 3 Sekunden finden lässt und ich frage mich wie.
Viele Grüße und danke für die Hilfe
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
Es gibt da drei Arten der Optimierung.
Einmal kann man mathematische Tricks, wie das mit der Ziffer 0 anwenden. Vielleicht gibt es da noch andere pfiffige Dinge, ich bin darin aber nicht wirklich bewandert.
Dann kann man den Algorithmus selber trimmen. Wenn man jede neue Zahl zusammen mit ihrer Beharrlichkeit in eine Liste schreibt, muß man für jede neue Zahl nur die erste Quersumme berechnen. Die sich ergebende Zahl sollte kleiner als die ursprüngliche sein, und damit bereits in der Liste stehen. Allerdings hast du hier extrem große Zahlen. Will man jede davon in die Liste packen, gibt es bald ein speicherproblem Die Zahl
277.777.788.888.899
lässt sich mit einem LONG LONG darstellen, belegt dann also 8 Byte. Um alle Zahlen bis da hin zu speichern, benötigst du um die 2 Petabyte Speicherplatz. Etwas viel...
Zu guter Letzt ist die Frage, wie dein Code aussieht, welche Sprache du verwendest, welche Optimierung usw.
Wenn du I7 sagst, hat der sicher vier Kerne. Wenn du die alle vier beschäftigst, vervierfachst du auch schon halbwegs die Geschwindigkeit.
Ein Programm in C kann ganz erheblich beschleunigt werden, wenn es mit der Option -O3 kompiliert wird, während andere Sprachen wie Python ggf. zu langsam sind. Computeralgebrasysteme sind ziemlich langsam, die kann man vergessen.
Vielleicht zeigst du einfach mal den Code, und wir schauen, was man machen kann?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:45 Sa 15.11.2014 | | Autor: | felixf |
Moin!
> Es gibt da drei Arten der Optimierung.
>
> Einmal kann man mathematische Tricks, wie das mit der
> Ziffer 0 anwenden. Vielleicht gibt es da noch andere
> pfiffige Dinge, ich bin darin aber nicht wirklich
> bewandert.
Nun, eine sehr einfache Sache ist noch: wenn man die Ziffern vertauscht, bleibt das Querprodukt gleich. Somit kann man die Ziffern auch immer absteigend sortieren -- vor allem um auf das kleinste passende Querprodukt zu kommen.
Das sieht man ja auch bei dem Ergebnis 277.777.788.888.899. Am schnellsten ist man vermutlich mit einer Hybrid-Strategie: bis zu einem gewissen Punkt berechnet man Tabellen vor, und ab diesen Punkt rechnet man anders weiter. Das Querprodukt aus obiger Zahl ist z.B. 4'996'238'671'872. Wenn man diese faktorisiert und alle möglichen Produkte aufschreibt mit Faktoren [mm] $\le [/mm] 9$, kann man daraus vermutlich recht schnell die kleinste Zahl finden, deren Querprodukt gerade 4'996'238'671'872 ist.
Diese Zahl 4'996'238'671'872 muss weiterhin [mm] $\ge$ [/mm] der kleinsten Zahl sein, bei der man genau 10 Schritte braucht um auf eine einstellige Zahl zu kommen.
Mit solchen (und vielen weiteren solchen) Überlegungen kommt man meist viel weiter, weil man damit die Suche stark reduzieren kann.
LG Felix
|
|
|
| |
|
// Hier der Java-Code. Was könnte man denn da machen?
// Ohne HilfsTabellen
public class Quer {
private static String Error = "Bitte eine positive ganze Zahl als Argument angeben.";
public static void main(String[] args) {
if(args.length>0) {
if( args[0].matches("[0-9]{1,2}") ) {
long startTime = System.currentTimeMillis();
double time = (System.currentTimeMillis()-startTime)/1000.0;
// Get the commandline-argunents a and b
long maxtest = Long.parseLong(args[0]); // argument <=11
long test = 0;
long number = 10;//277777788888899l;
while(test<maxtest)
{
long newtest = beharrlichkeit(number);
if(newtest>test)
{
test = newtest;
time = (System.currentTimeMillis()-startTime)/1000.0;
System.out.println(test+": " + number+" ("+time+" sec)") ;
}
number++;
}
// Error-Handlers
} else System.out.println(Error); // if first argument is not Integer
} else System.out.println(Error); // if less then two Arguments
}
private static long beharrlichkeit(long x)
{
int persistance = 1;
while((x = querProduktRecursive(x))>9) persistance++;
return persistance;
}
private static long querProduktRecursive(long x)
{
int digit = (int)(x%10);
switch(digit)
{
case 0: return 0;
default: return (x<10) ? x : querProduktRecursive(x/10) * digit;
}
}
}
|
|
|
| |
|
Hi!
Da warst du ja schon recht fleißig.
Ich sehe, daß du das Querprodukt rekursiv berechnest, was durchaus bemerkenswert ist. Nicht viele Leute kommen damit so gut klar, daß sie es häufig verwenden. Leider kommt auch ein Computer mit rekursiven Funktionen nicht sonderlich gut klar: Für jeden Aufruf muß er den Wert aller Variablen erstmal irgendwo speichern, und später wieder hervor kramen. Das heißt, rekursive Funktionen können ganz schön Speicher fressen, und Zeit geht auch noch drauf. Daher ein Tipp: Wenn es zeitkritisch ist, solltest du auf Rekursion verzichten. Und grade diese Funktion wird bei dir exzessiv genutzt!
Ich habe hier mal eine nicht rekursive Form (in C geschrieben), die die Quersumme aller 10-stelliger Zahlen berechnen kann:
| 1: |
| | 2: | long querProdukt(long x){
| | 3: | long nenner=1000000000;
| | 4: | long ganzzahl;
| | 5: | long quer=1;
| | 6: | int start=0;
| | 7: |
| | 8: | while(nenner != 0){
| | 9: | ganzzahl= x/nenner;
| | 10: | if(ganzzahl != 0){
| | 11: | quer *= ganzzahl;
| | 12: | start=1;
| | 13: | }
| | 14: | else if(start == 1){
| | 15: | return 0;
| | 16: | }
| | 17: | x = x % nenner;
| | 18: | nenner /= 10;
| | 19: | }
| | 20: | return quer;
| | 21: | } |
Lässt man damit alle Quersummen von 1 bis 1000000000! berechnen, benötigt mein Rechner 22 Sekunden, während er für deine rekursive Methode 48 Sekunden benötigt. Man kann meinen Code sicher noch optimieren, denn er weiß nicht, wie lang die Zahl wirklich ist, und geht immer von 10 Stellen aus. Jetzt ist noch die Frage, wie der Zeitunterschied bei Java aussieht.
Ansonsten hat felixf ja ne geniale Sache beschrieben. Im Prinzip mußt du nur Zahlen untersuchen, bei denen von links nach rechts jede Zahl größergleich der vorherigen ist. Um rauszufinden, ob eine Zahl das erfüllt, könntest du meine Funktion als Basis nehmen, und daraus ne entsprechende Funktion erstellen. Ich hab das gemacht und herausgefunden, daß von den Zahlen 1...1000000000 nur 7,7% dies erfüllen. Das heißt, nur 7,7% müssen dann durch die "beharrlichkeitsberechnung", was dir ganz gewaltig Zeit einspart.
Grade bei den großen Zahlen, die ne tendenziell hohe Beharrlichkeit haben, fällt der größte Teil weg.
Nunja, wenn man jede Zahl erstmal darauf testet, ob sie überhaupt untersucht werden muß, zählt man immernoch alle Zahlen durch. Noch besser wäre es, wenn man von vornherein nur Zahlen generiert, deren Beharrlichkeit man berechnen muß. Das spart nochmal sehr viel Zeit.
|
|
|
| |
|
Hallo!
Ich habe, weils mir Spaß macht, mich auch nochmal damit auseinandergesetzt.
Dabei habe ich die Zahlen zu untersuchenden Zahlen "zu Fuß" berechnet. Das heißt, ich habe mir ein Array erstellt, dessen Elemente die Ziffern der Zahl enthalten. Für jede neue Zahl wird 1 addiert, und überprüft, ob es zu Überträgen kommt. Wenn ja, wird die Ziffer der höchsten Stelle, die einen Übertrag erhalten hat, auch in die niedrigeren Stellen kopiert. Damit erreicht man, daß man nach 1599 direkt erhält 1666. Es gibt also keine Zahlen, die man gar nicht erst ausprobieren muß.
Das Resultat:
Deine kleinste Zahl finde ich nach 1,3 Sekunden, alle max. 20-stelligen Zahlen mit Beharrlichkeit 11 in 9 Sekunden. Die größte, die ich gefunden habe, ist
13334444444446777777
Zur Berechnung der Quersummen verwende ich dann doch wieder ne normale Variable. Die größte einfachste Variable ist in C ein unsigned long long, das fasst maximal die 21-stellige Zahl 18446744073709551615.
|
|
|
|
