Code vereinfachen

[javabeginner]

Hallo,

ich habe ein Problem, ich soll folgende Code vereinfachen bzw die Lösung ermitteln:

public class berechnen {
  static long rechts(long a, long b) {
    return (a < 1 || b < 1) ? 1 : rechts(a - 1, b) + links(b - 2, a - 1);
  }
  static long links(long a, long b) {
    return (a < 1 || b < 1) ? 1 : rechts(b, a - 1) + links(a, b - 1);
  }
  public static void main(String[] args) {
    char ergebnis[] = ("°. NE'0459" + Long.toString(rechts(42, 42))).toCharArray();
    for (int k : new int[] {3,2,7,9,0,2,8,11,1,15,13,21,5,2,4,2,6,6,9,0,2,6,22,1,24,18,16,5})
      System.out.print(ergebnis[k]);
  }

kann mir jemand helfen?
was kommt als ergebnis raus?
bzw wie ist der code zu vereinfachen, dass er in "normaler" zeit ausführbar ist?

danke für eure hilfe

[ChrisB]

Hi,

was kommt als ergebnis raus?

Das solltest du doch selber ermitteln können, wenn du dir erst mal veranschaulichst, was die einzelnen Methoden machen und in welcher Reihenfolge sie auf die Daten angewendet werden.

bzw wie ist der code zu vereinfachen, dass er in "normaler" zeit ausführbar ist?

Das kannst du dir dann überlegen, wenn du erst mal das zu erwartende Ergebnis kennst.

MfG ChrisB

[javabeginner]

hallo,

genau da liegt mein problem; ich versteh den code nicht so ganz ;(

[Encoder]

genau da liegt mein problem; ich versteh den code nicht so ganz ;(

Da bist du nicht alleine.
Woher ist der Code? Was macht er, wofür ist er gut?
Irgendwie erinnert es mich an die Ackermannfuntion, was sehr rekursives und somit schnell ziemlich aufwendig werdendes.
Aber ich seh den Sinn nicht, in Verbindung mit Koordinaten?

[MudGuard]

Hi,

ich habe ein Problem, ich soll folgende Code vereinfachen bzw die Lösung ermitteln:

Vereinfachen? Weiß nicht. Vielleicht gibt es eine Formel, um aus a und b direkt das Ergebnis zu ermitteln. Ich seh im Moment nichts derartiges.

(Deutlich) Beschleunigen ginge:

Lege für die Ergebnisse von rechts eine Map an, key ist a + "_" + b.
Guck als erstes in die Map, ob bereits ein Wert vorhanden ist für a + "_" + b.
Wenn ja, gib ihn zurück.
Wenn nein: berechne den Wert, stecke ihn in die Map, und gib ihn zurück.

Gleiches Spiel für links: zweite Map, key ist wieder a + "_" + b.

Damit erhältst Du das Ergebnis von rechts(42,42) sehr schnell!

bei rechts(20,20) kommt es (wenn man die map-Treffer ignoriert) zu

rechtscount: 24171004
linkscount: 24171003
Aufrufen,
die Maps enthalten nur
rechtsmap: 126
linksmap: 119
verschiedene a-b-Kombinationen.

Nimmt man, wenn vorhanden, die Treffer aus der Map, ergeben sich diese Zahlen:
rechtscount: 219
linkscount: 218
rechtsmap: 126
linksmap: 119

Also statt ca. 24 Millionen Aufrufen nur noch etwas über 200.

Bei rechts(42,42) mit Map-Treffer-Berücksichtigung:
rechtscount: 981
linkscount: 980
rechtsmap: 539
linksmap: 497

(die Aufrufzahlen bei Nicht-Berücksichtigung der Map-Treffer hab ich nicht ermittelt - ich brauch meinen Rechner noch für andere Dinge)

bzw wie ist der code zu vereinfachen, dass er in "normaler" zeit ausführbar ist?

Für eine Beschleunigung wird der Code nicht notwendigerweise einfacher, sondern komplizierter.

cu,
Andreas