Lösungsansatz für dieses Rätsel?

...komplette Frage anzeigen

3 Antworten

Die Lösung Ist ganz simpel. Brauchst 1 int und 1 Array.

Lese Zeile für Zeile und schreibe alle in Werte per Split aufs Leerzeichen ins Array. Dann wende die sortiermethode aufs Array an und hol dir so den grössten Wert. Den addiert du zu deinem globalem int und wenn du fertig bist kannst du dir ja deinen globalen int ausgeben. Natürlich verfliegen (gewollt) alle Werte wieder nachdem ne neue Zeile beginnt

Antwort bewerten Vielen Dank für Deine Bewertung
Anton03 08.10.2017, 08:02

bin durch ein Kommentar vor dir bereits drauf gekommen aber trotzdem danke

0
Mikkey 08.10.2017, 11:02

Entweder verstehe ich nicht Deinen Ansatz (m.E. suchst Du das größte Element jeder Zeile), oder Du hast das Wort "adjacent" nicht berücksichtigt. Es geht um die beiden jeweils benachbarten Elemente.

Veränderst Du im Musterdreieck die Sechs zu einer Acht, bekommst Du mit Deinem Verfahren 26 heraus, tatsächlich ergibt die Lösungsroute 3-4-8-9 aber nur 24.

1
LeonardM 08.10.2017, 11:34

Du hast recht mit deiner Annahme.ich hab nur die Überschrift gelesen und mir die Grafik angesehen. mein Fehler. :-) naja das Problem ist ja scheinbar gelöst. trotzdem danke für die Info:D

0

#Routenfinder :) ("Pathfinder algorithm")

schließe schlechte Wege direkt aus, suche nach dem besten.

Antwort bewerten Vielen Dank für Deine Bewertung
Anton03 08.10.2017, 07:59

Danke! Ich stand grade irgendwie auf dem Schlauch.

1

Wenn Du die größte Summe sⱼ,ₙ für jedes Element eⱼ,ₙ in der letzten Zeile n kennst, ist das Problem trivial. Diese Summen lassen sich rekursiv berechnen:

    s₁,₁ = e₁,₁
                       ⎧  s,ₙ₋₁                             für j=1
    sⱼ,ₙ = eⱼ,ₙ + ⎨  max( sⱼ,ₙ₋₁ , sⱼ₋,ₙ₋₁ )  für 1<j<n
                       ⎩  sₙ₋₁,ₙ₋₁                         für j=n

Das ganze läuft in 𝓞(n²) Zeit mit 𝓞(n) Speicherplatz. Zum verifizieren kannst Du auch die entsprechenden Pfade protokollieren:

    p₁,₁ = ''
                       ⎧  'l'   falls sⱼ,ₙ₋₁ < sⱼ₋,ₙ₋
    pⱼ,ₙ = pⱼ,ₙ + ⎨  '-'   falls sⱼ,ₙ₋₁ = sⱼ₋,ₙ₋
                       ⎩  'r'   falls sⱼ,ₙ₋₁ > sⱼ₋,ₙ₋

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?