Hallo,
wir haben in der Uni eine Aufgabe zu lösen.
"Schreiben Sie ein Java Programm, welches für positive ganze Zahlen (in Dezimalschreibweise) ermittelt, ob sie gleich
der Summe all Ihrer Ziffern jeweils mit sich selbst potenziert sind "
Beispiel: 3435 = 3^3 + 4^4 +3^3 + 5^5
Ferner wurde definiert, dass 0^0 = 0 ist. Weiter wurde uns gesagt, dass es genau 3 Zahlen gibt. Die größte hat 9 Stellen.
Die Aufgabe habe ich gelöst, allerdings möchte ich gerne die Laufzeit verkürzen. (Es gibt Zusatzpunkte) 🙂
Hier mein kommentierter Quelltext:
Das Programm terminiert bei mir nach etwas über 2 Minuten. Wie kann ich die Laufzeit verkürzen?
Meine Ideen:
- Uns wurde gesagt, dass es genau drei Zahlen gibt, also könnte ich noch eine weiter Zählvariable einführen, die
wenn sie ==3 die for-Schleife mit einem break verlässt, ich werde es auch gleich testen, aber ich vermute, dass das nicht viel Einsparung bringt
- ein Knackpunkt könnte die for-Schleife sein (lineare Suche)..... es wurde angedeutet man könne dies optimieren,
aber wie????
Habt ihr vielleicht ein paar Denkanstöße? 🙂 Gibt es noch weitere möglich Optimierungen?
Danke
wir haben in der Uni eine Aufgabe zu lösen.
"Schreiben Sie ein Java Programm, welches für positive ganze Zahlen (in Dezimalschreibweise) ermittelt, ob sie gleich
der Summe all Ihrer Ziffern jeweils mit sich selbst potenziert sind "
Beispiel: 3435 = 3^3 + 4^4 +3^3 + 5^5
Ferner wurde definiert, dass 0^0 = 0 ist. Weiter wurde uns gesagt, dass es genau 3 Zahlen gibt. Die größte hat 9 Stellen.
Die Aufgabe habe ich gelöst, allerdings möchte ich gerne die Laufzeit verkürzen. (Es gibt Zusatzpunkte) 🙂
Hier mein kommentierter Quelltext:
Java:
public class Xxxx {
public static void main (String []args){
long[] pot = {0 , 1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489};
// die Zahlen 0 - 9 mit sich selber multipliziert
long zahl; //die zu untersuchende Zahl
long zahl2; // zahl 2 wird verglichen mit zahl
int stelle; // die ziffer innerhalb der zahl
for(long i = 1; i < 999999999; ++i ){ // untersuche alle Zahlen von 1 bis 999999999
zahl = i;
zahl2 = 0;
//System.out.println("=> i = " + i);
while (zahl != 0){
stelle = (int)(zahl % 10); // 1. berechne die jeweiligen Stellen
zahl = zahl / 10; // 2. und dividiere die Zahlen anschließend durch 10
// wiederhole 1. und 2. solange zahl != 0
switch (stelle){
case 0: zahl2 += pot[0]; break;
case 1: zahl2 += pot[1]; break;
case 2: zahl2 += pot[2]; break;
case 3: zahl2 += pot[3]; break;
case 4: zahl2 += pot[4]; break;
case 5: zahl2 += pot[5]; break;
case 6: zahl2 += pot[6]; break;
case 7: zahl2 += pot[7]; break;
case 8: zahl2 += pot[8]; break;
case 9: zahl2 += pot[9]; break;
}
// die entsprechende Stelle i (0-9) wird mit sich selbst potenziert
// und zur zahl2 addiert
}
if(i == zahl2){ // wenn i == zahl2 ->Ausgabe
System.out.print(i + " ");
}
}
}
}Das Programm terminiert bei mir nach etwas über 2 Minuten. Wie kann ich die Laufzeit verkürzen?
Meine Ideen:
- Uns wurde gesagt, dass es genau drei Zahlen gibt, also könnte ich noch eine weiter Zählvariable einführen, die
wenn sie ==3 die for-Schleife mit einem break verlässt, ich werde es auch gleich testen, aber ich vermute, dass das nicht viel Einsparung bringt
- ein Knackpunkt könnte die for-Schleife sein (lineare Suche)..... es wurde angedeutet man könne dies optimieren,
aber wie????
Habt ihr vielleicht ein paar Denkanstöße? 🙂 Gibt es noch weitere möglich Optimierungen?
Danke
