Hallo,
im Rahmen des Studiums soll ein Programm geschrieben werden welches die kleinsten Zahlen berechnet welche jeweils eine multiplikative Beharlichkeit (Solange das Querprodukt vom Querprodukt bilden bis es einstellig ist) von 2-9 hat (soweit so gut). Der kniff ist dass dies in maximal 5 Sekunden passieren soll (auch soweit so gut).
Zusatzaufgabe ist, dass man es so optimieren/verändern soll dass auch die Zahlen für Beharlichkeit 10 und 11 berechnet werden (in maximal 10 Sekunden!).
Ich habe folgendes Programm, welches etwa 2 Sekunde benötigt um das Problem für 2-10 zu lösen:
(Funktionen habe ich bewusst vermieden, um die Geschwindigkeit zu erhöhen).
Ich will nicht unbedingt ein 1A-Top Programm vorgesetzt bekommen, aber hat vielleicht jemand einen Tipp oder einen Denkanstoß wie man das ganze performanter bekommt? (Das Problem für 11 rödelt nun schon wesentlich länger als 10 Sekunden und hat noch keine Lösung).
Danke und Gruß
Lolwis111
im Rahmen des Studiums soll ein Programm geschrieben werden welches die kleinsten Zahlen berechnet welche jeweils eine multiplikative Beharlichkeit (Solange das Querprodukt vom Querprodukt bilden bis es einstellig ist) von 2-9 hat (soweit so gut). Der kniff ist dass dies in maximal 5 Sekunden passieren soll (auch soweit so gut).
Zusatzaufgabe ist, dass man es so optimieren/verändern soll dass auch die Zahlen für Beharlichkeit 10 und 11 berechnet werden (in maximal 10 Sekunden!).
Ich habe folgendes Programm, welches etwa 2 Sekunde benötigt um das Problem für 2-10 zu lösen:
(Funktionen habe ich bewusst vermieden, um die Geschwindigkeit zu erhöhen).
Ich will nicht unbedingt ein 1A-Top Programm vorgesetzt bekommen, aber hat vielleicht jemand einen Tipp oder einen Denkanstoß wie man das ganze performanter bekommt? (Das Problem für 11 rödelt nun schon wesentlich länger als 10 Sekunden und hat noch keine Lösung).
Java:
public class Quer
{
public static void main(String[] args)
{
long startTime = System.currentTimeMillis(); // Startzeit bestimmen
long lastResult = 0; // Ergebnis der letzen Berechnung (als Startwert fuer die neue Berechnung)
int N = Integer.parseInt(args[0]); // Zahl von der Kommandozeile einlesen
int VB = 1024 * 1024; // Querprodukte cachen
long[] S = new long[ VB ];
for(int i = 0; i < VB; i++) // Beharlichkeiten vorberechnen
{
long z = i;
long s = 0;
while(z > 9) // Solange Ziffern uebrig sind
{
long q = 1; // Querprodukt bestimmen
while(z > 0)
{
q *= z % 10; // mit jeder Ziffer multiplizieren
z /= 10;
}
z = q;
s++; // Schritte zaehlen
}
S[i] = s; // Schritte zur Zahl speichern
}
for(int n = 2; n <= N; n++) // Fuer jede Schrittanzahl bestimmen
{
int found = 0; // Wert gefunden?
long z = lastResult; // Startwert festlegen
while(found == 0)
{
long i = z; // Wert kopieren
long t = i % 10; // Vortests
long t2 = (i / 10) % 10; //
if(n > 4 && !(t == 8 || t == 9) && !(t2 == 7 || t2 == 8 || t2 == 9)) // die letzen Stellen der Zahl sind 7, 8 oder 9
{
long t3 = i % 100; // bei allen ueber 8 sind die letzen beiden Stellen 9
if(n > 8 && i != 99)
{
z += 99 - t3 - 1; // alle Werte ueberspringen die definitiv nicht auf 99 enden
}
z++;
continue; // "false" Zahlen garnicht erst berechnen
}
long s = 0; // Anzahl Schritte
while(i / 10 > 0) // Solange die Quersumme mehr als eine Ziffer hat rechnen
{
if(i < VB) // gecached?
{
s += S[(int)i]; // Aus der Vorberechnung nehmen
i = 1;
}
else
{
long q = 1; // sonst Querprodukt berechnen (vgl. oben)
while(i > 0)
{
q *= i % 10;
i /= 10;
}
i = q;
s++;
}
}
if(s == n) // wurde eine Zahl mit entsprechender Schrittanzahl gefunden, diese Ausgeben
{
System.out.println(Long.toString(n) + " Schritte: " + Long.toString(z));
if(n < 4) lastResult = (z * (n - 1)) - 1; // Startwert der naechsten Berechnung anpassen (wegen 25,39 und 77
else lastResult = (z * n); // sonst einfach z * n)
found = 1; // Wert wurde gefunden!
}
z++; // naechste Zahl probieren
}
}
long endTime = System.currentTimeMillis(); // Endzeit
long time = endTime - startTime; // Zeitdifferenz in Millisekunden bestimmen
System.out.println(Long.toString(time) + "ms");
}
}Danke und Gruß
Lolwis111
