Moin zusammen,
ich habe heute morgen mit einem meiner Lehrer über das mathematische Problem zwei Zahlen zu finden, deren Summe der beiden Quersummen ein vielfaches von 2006 ist, da dies eine Aufgabe für die diesjährige Mathematikolympiade ist.
Er sagte mir, dass er die Aufgabe gelöst habe - auf herkömmlichen Wege - und ich sagte, da er auch recht Computerinteressiert ist - warum er nicht einfach ein Programm geschrieben habe.
Wir überlegten uns dann, das dies doch recht lange dauern könnte.
Ich entschloss mich also mal kurz so'n Programm zu machen et voilà:
Es funktioniert für kleine Zahlen, läuft aber bei großen sehr lange.
Ich frage mich, ob man jetzt noch Optimierungen, und zwar nur Java-technischer, nicht algorythmischer Seite vornehmen könnte.
Mir ist schon klar, dass es mit einem besseren Algorithmus schneller geht, aber wir wollen ja die minimale Zeit, die ein Rechner bei stumpfen ausprobieren braucht, ermitteln.
Die Hauptrechenzeit wird natürlich in der Schleife des Konstruktors und in der Methode quersumme verbracht.
Kann man da noch was optimieren?
Man könnte natürlich noch den Thread abschalten, aber ich möchte immer mal gerne zwischen durch wissen, wie weit er ist...
Wenn noch jemannd Ideen hat, wäre ich dankbar.
MfG
MPW
[edit:] Ich nehme nicht an dem Wettbewerb teil, nicht, dass da einer glauben würde, er würde mir helfen. Nebenbeigesagt hätten wir ja schon - wie oben beschrieben - eine Lösung. Es ist eine reine Interessenssache.
ich habe heute morgen mit einem meiner Lehrer über das mathematische Problem zwei Zahlen zu finden, deren Summe der beiden Quersummen ein vielfaches von 2006 ist, da dies eine Aufgabe für die diesjährige Mathematikolympiade ist.
Er sagte mir, dass er die Aufgabe gelöst habe - auf herkömmlichen Wege - und ich sagte, da er auch recht Computerinteressiert ist - warum er nicht einfach ein Programm geschrieben habe.
Wir überlegten uns dann, das dies doch recht lange dauern könnte.
Ich entschloss mich also mal kurz so'n Programm zu machen et voilà:
Code:
import java.math.BigInteger;
class Problem2006 implements Runnable {
BigInteger a;
BigInteger b;
boolean notready = true;
BigInteger eins = new BigInteger("1");
public Problem2006(int zahl) {
System.out.println("Zunächst wird die kleinstmögliche Zahl"+
"bestimmt, um die Rechenzeit zu verkürzen.");
int k = zahl/2-1;
int st = k/9;
String start = "";
for (int i = 0; i < st; i++) {
start += "9";
}
System.out.println("Die kleinstmögliche Zahl ist " + start + ".");
a= new BigInteger(start);
b = new BigInteger(a.add(eins).toString());
System.out.println("Beginn des Rechenvorgangs. Es wird einmal"+
"pro Minute eine Angabe über die aktuell berechneten Zahlen gemacht.");
new Thread(this).start();
while ((quersumme(a) + quersumme(b))%zahl != 0) {
a = a.add(eins);
b = b.add(eins);
}
System.out.println("Das kleinste Zahlenpaar, was die Bedinngungen erfüllt, wurde gefunden:");
System.out.println("Es sind die Zahlen " + a.toString() + " und " + b.toString() + ",");
System.out.println("denn die Summe der beiden Quersummen beträgt " + (quersumme(a) + quersumme(b)) + ",");
System.out.println("was " + (quersumme(a) + quersumme(b))/zahl + " mal " + zahl + " ist.");
notready = false;
}
long quersumme(BigInteger bi) {
String s = bi.toString();
long r = 0;
char c[] = s.toCharArray();
for (char b : c) {
r += Integer.parseInt(Character.toString(b));
}
return r;
}
public static void main(String args[]) {
try {
int number = Integer.parseInt(args[0]);
long s = System.currentTimeMillis();
new Problem2006(number);
long s2 = System.currentTimeMillis();
long t = s2-s;
long sus;
String time = "";
sus = t/1000/60/60/24;
time += sus + " d ";
t -= sus*1000*60*60*24;
sus = t/1000/60/60;
time += sus + " h ";
t -= sus*1000*60*60;
sus = t/1000/60;
time += sus + " min ";
t -= sus*1000*60;
sus = t/1000;
time += sus + " s ";
t -= sus*1000;
time += t + " ms";
System.out.println("Der Rechenvorgang hat " + time + " gedauert.");
} catch (NumberFormatException e) {
System.out.println("Die von Ihnen angegebene Zahl ist ungültig.");
} catch (ArrayIndexOutOfBoundsException e) {
System.out.println("Es wurde keine Zahl angegeben.");
}
}
public void run() {
while (notready) {
System.out.println("Der Computer ist gerade bei den Zahlen " + a.toString() + " und n+1.");
System.out.println("");
System.out.println("");
try {
for (int i = 0; i < 60; i++) {
Thread.sleep(1000);
if (notready == false) {
break;
}
}
} catch (InterruptedException e) {
}
}
}
}Es funktioniert für kleine Zahlen, läuft aber bei großen sehr lange.
Ich frage mich, ob man jetzt noch Optimierungen, und zwar nur Java-technischer, nicht algorythmischer Seite vornehmen könnte.
Mir ist schon klar, dass es mit einem besseren Algorithmus schneller geht, aber wir wollen ja die minimale Zeit, die ein Rechner bei stumpfen ausprobieren braucht, ermitteln.
Die Hauptrechenzeit wird natürlich in der Schleife des Konstruktors und in der Methode quersumme verbracht.
Kann man da noch was optimieren?
Man könnte natürlich noch den Thread abschalten, aber ich möchte immer mal gerne zwischen durch wissen, wie weit er ist...
Wenn noch jemannd Ideen hat, wäre ich dankbar.
MfG
MPW
[edit:] Ich nehme nicht an dem Wettbewerb teil, nicht, dass da einer glauben würde, er würde mir helfen. Nebenbeigesagt hätten wir ja schon - wie oben beschrieben - eine Lösung. Es ist eine reine Interessenssache.
