[JAVA] Bloodys Mathe-/Optimierungsrunde

  • Hallo,


    nachdem ich mir bereits die letzten Tage etwas den Kopf zerbrochen hab, dachte ich mir, dass vielleicht jemand hier in der Gemeinschaft noch schlauer ist als ich. Ganz kurz zum Thema: Es gilt einen Java-Algorithmus zu entwickeln, der ein mathematisches Problem löst; und das so schnell wie möglich.


    Folgendes Problem wird betrachtet:


    Man nehme eine Zahl a aus den Stellen ab, die folgende Eigenschaft erfüllt: a^a + b^b = ab. In anderen Worten: Die Summe aller Ziffern mit sich selbst potenziert ergibt wieder unsere ursprüngliche Zahl. Folgendes definieren wir außerdem: 0^0 = 0.


    Neben der Zahl 1 gibt es noch die Zahl 3435, die diese Eigenschaften erfüllt sowie noch eine weitere Zahl. Wir brauchen also einen Algorithmus, der per Schleife von 1 anfängt (von mir aus auch 3436) und uns die dritte (und letzte existierende) Zahl, die das erfüllt ausgibt.



    Soviel vorne weg: Ich habe einen Algorithmus, der aber relativ langsam ist (55 Sekunden auf einem zentralen Testserver, auf dem ich den Code auf Geschwindigkeit prüfe). Leute behaupten, das ganze in 4-5 Sekunden hinzukriegen. Da die Zahl im mittleren neunstelligen Bereich liegt, haben wir also milliarden Rechenoperationen - Ziel muss es daher sein, Zahlen, die es aus irgendwelchen Mathematischen Gründen nicht sein können, so schnell wie möglich auszuschließen.


    Sollte jemand zufällig zu viel Zeit haben, würde ich doch sehr darum bitten, sich darüber mal etwas Gedanken zu machen, einen groben Code zu schreiben, die Zahl (die ich euch von mir aus auch nennen kann) zu finden und danach das Ganze auf Geschwindigkeit zu optimieren.


    Wer irgendwas hinkriegt, was auf meiner zentralen Testmaschine in weniger als 10 Sekunden läuft und tatsächlich erstmal alle Zahlen irgendwie ansieht, bekommt...uhm...überleg ich mir dann. ;)



    Benutzt werden darf: Grundrechenarten, Schleifen, break/continue, Bitoperationen, IF-Abfragen. Kein Multithreading/SuperCheat/Weißichwas

  • Das mit der Quersumme ist hirnrissig, habs ausprobiert funkt nur für 1:


    Wie meinste das mit a^a+b^b = ab? was soll da B sein?

  • Ach ne, das hab ich wohl gecheckt nur, was ist in dem beispiel B?
    wie wäre es mit 356
    9 + 25 + 36 oder was?



    Funkt, ich find aber 3435 und nicht 3436 oO
    :

    Einmal editiert, zuletzt von rEViDE ()

  • do.de - Domain-Offensive - Domains für alle und zu super Preisen
  • Dein Code (sofern er noch derselbe von oben ist) kann die Zahl aber nicht finden, da sie eine Null enthält, und die Standard-Mathe-Power Funktion für hoch 0 Eins ausgibt.


    Wir haben aber oben gesagt, 0^0 soll ebenfalls 0 sein :P

  • Stimmt, einen moment :D:D


    //Edit: wei soll man das denn noch optimieren, die schleife an sich dauert ja solange bis zum 9 stelligen bereich, optimierumg hin oder her oO
    oder kann man das irgendwie "rückwärtsrechnen oO" :D?


    //Edit 2:


    //Edit 3:
    Schick mir mal die auflösung per pn ;)

    //EDIT 4 ICH HAB SIE :D
    NACH ca. 5-6 MIN: a^a+b^b| 438579088
    Mein Konsolen Output:
    a^a+b^b| 0
    a^a+b^b| 1
    a^a+b^b| 3435
    a^a+b^b| 438579088

    Einmal editiert, zuletzt von rEViDE ()

  • Du kannst bei der dritten Zahl (die mit der 4 vorne) abbrechen. ;)


    Das ermitteln haste also, jetzt geht es also darum, das ganze zu optimieren. Und:


    o = "" + w.charAt(s);
    r = Integer.parseInt(o);


    das hier ist nicht erlaubt, lass dir dafür mal was anderes einfallen. ;)

  • Jap, eine ähnliche Lösung wie ReVide habe ich auch schon rausbekommen... Jetzt geht es ans überlegen.


    //edit: Neuer Ansatz, auch nicht besser: enthält zusätzlich % und ist nur unwesentlich schneller:
    Checken aller Zahlen zwischen: 1,1000000 mit String-Integer Gedöns: 14858 millisek. und mit meiner neuen Variante: 14287 millisek. | Auf meinen schrabbelligen Laptop. :P
    //edit: Und mit Konsolenausgabe nach jeder Zahl, richtige Ergebnisse kommen gleich.


    2 Mal editiert, zuletzt von rejooh ()

  • Ah, tatsächlich.


    Aber du berechnest damit jede Zahl in dieser Funktion? Ich vermute jetzt einfach mal, dass der Funktionsaufruf (plus das zusätzliche erstellen der Variablen bei jedem Durchgang) enooorm viel Zeit frisst :P



    Am schnellsten ging bei mir alles in der main-Funktion. Und dann noch einige weitere Optimierungen...