Schrittfolge

[BLUEblue]

ich stehe irgendwie auf der leitung, weil mir die angabe nicht ganz klar ist. muss ich alle schrittfolgen gehen. wenn ich z.B. n=6 habe und das ziel mit 6 nach osten, 5 nach norden und 4 nach werten erreichen kann, muss ich noch die restlichen schrittfolgen machten bis n= 0.

wie schliesse ich unmögliche schrittkombinationen aus?

Danke an alle die licht ins dunkel bringen!!

[cokker]

Ich würde es so verstehen, dass du genau auf dem Ziel landen musst. Es dürfen also keine Bewegungen mehr übrig bleiben.

Gruß
Sven

[Firefall]

Ich denke 2 mal in dieselbe Himmelsrichtung gilt als "unmögliche Schrittkombination". Der typische rekursive Algorihtmus dürfte ohne das Ausschliessen dieser Möglichkeit arbeiten.

[DarkTom]

Ich denke 2 mal in dieselbe Himmelsrichtung gilt als "unmögliche Schrittkombination". Der typische rekursive Algorihtmus dürfte ohne das Ausschliessen dieser Möglichkeit arbeiten.Da würde ich dir widersprechen. Das würde ich eher als "verbotene Schrittkombination" bezeichnen.
Es geht hier eher darum, das Prüfen auf die Existenz einer erlaubten Komination zu beschleunigen. Und da kann man sich durchaus ein paar Eigenschaften überlegen, nach denen man bestimmte rekursive Aufrufe von vorne herein auschliessen kann, im positiven wie im negativen Fall.

[Firefall]

Da würde ich dir widersprechen. Das würde ich eher als "verbotene Schrittkombination" bezeichnen.
Es geht hier eher darum, das Prüfen auf die Existenz einer erlaubten Komination zu beschleunigen. Und da kann man sich durchaus ein paar Eigenschaften überlegen, nach denen man bestimmte rekursive Aufrufe von vorne herein auschliessen kann, im positiven wie im negativen Fall.
Mir fiel dazu spontan nichts ein... Man könnte höchstens sagen wenn die Entfernung zum Ziel grösser ist als die Anzahl Schritte, die man zurücklegen darf, dann ein Laufen zurück. Aber ob das Effizienzgewinne erzielt... Denke das dürfte nur der Fall sein, wenn n 100 oder mehr ist.

[butterkeks]

es macht beispielsweise keinen Sinn, sich vom Ziel wegzubewegen (weil man den WEg nicht mehr "einholen" kann) und muss so höchstens 2 Himmelsrichtungen pro Rekursionsschritt "ausprobieren" (hoffentlich hab ich nicht zu viel verraten)

[Firefall]

es macht beispielsweise keinen Sinn, sich vom Ziel wegzubewegen (weil man den WEg nicht mehr "einholen" kann) und muss so höchstens 2 Himmelsrichtungen pro Rekursionsschritt "ausprobieren" (hoffentlich hab ich nicht zu viel verraten)
Sicher muss man sich jenachdem vom Ziel wegbewegen - ist ja im Beispiel gezeigt!

[butterkeks]

aber es macht keinen Sinn, sich im Beispiel beim ersten Schritt nach Rechts oder unten zu bewegen oder so

[Firefall]

aber es macht keinen Sinn, sich im Beispiel beim ersten Schritt nach Rechts oder unten zu bewegen oder so
Okay, aber ob das für jede Situation zutrifft? Beispiel: Start liegt direkt unter Ziel, n=6. Wenn ich mir das so auf meinem Blatt ansehe müsste man 6O, 5N, 4W, 3S, 2W, 1S. Dann ist man beim Ziel, hat sich aber am Anfang davon entfernt.

[butterkeks]

ok, da hast du Recht

[Mr.Homm]

...
wie schliesse ich unmögliche schrittkombinationen aus?
...
Wenn du dir alle möglichen Schrittkombinationen für ein kleines n mal aufmalst, wirst du feststellen, dass sich sowas wie ein "Schachbrettmuster" bildet. Sagen wir, die möglichen Schrittkombinationen (die Felder auf die man zum stehen kommt) sind die schwarzen Felder, die unmöglichen die weißen Felder. Für n=1 sind es alle direkt am Startfeld anliegenden Felder erreichbar. Das Startfeld ist also ein weißes Feld. Bei n=2 kommen die "Springerfelder" (also ein Schach-Springer-Abstand) dazu. Das Startfeld ist also immernoch ein weißes. Bei n=3 liegt der Startpunkt auf einer schwarzen "Diagonalen", also die nächstgelegenen möglichen Schrittkombinationen sind jetzt nicht mehr direkt anliegend, sonder die diagonal anliegenden Felder. Das Startfeld ist also ein schwarzes Feld (obwohl es nicht erreichbar ist).

Wenn du die Gesamtstrecke berechnest, die du mit n, n-1, n-2,..., 2, 1 zurücklegst, kommst du auf die altbekannte Formel f(n) = n*(n+1)/2. Du kannst dich zwar in vier (oder meistens nur drei) Richtungen bewegen, aber ein Schachbrettmuster ist in alle Richtungen symetrisch, also kommt es nur auf die Gesamtlänge an. Wenn die Gesamtlänge gerade ist, dann ist das Startfeld ein schwarzes Feld. Bei ungeraden f(n) ist das Startfeld ein weißes Feld.

Wenn du die Farbe des Startfeldes kennst, kannst du zwar nicht auf die möglichen Felder schließen, aber du weißt, dass alle weißen Felder nicht erreichbar sind. Wenn gefragt ist, ob das Feld (x, y) erreichbar ist, kannst du nun einfach die Summe aus x und y berechnen und weißt die Farbe diese Feldes, denn wenn x+y gerade ist, dann hat das Feld die gleiche Farbe wie das Startfeld (0, 0) oder bei ungeraden x+y hat es die andere Farbe.

Am Beispiel Zielfeld (-1, 2) und n = 5 ergibt sich, dass f(5) = 15. 15 ist ungerade, also ist das Startfeld weiß. x+y = -1 + 2 = 1. 1 ist ungerade also hat das Feld (-1, 2) nicht die Farbe des Startfeldes, folglich ist das Feld schwarz. Schwarz heißt, dass Feld ist "möglicherweise mit einer Schrittfolge erreichbar". Das müsste dann dein rekursiver Algorithmus prüfen. Weiß hieße "das Feld kann mit keiner Schrittfolge erreicht werden".

So kannst du schonmal die Hälfte aller möglichen Felder als unerreichbar ausschließen.

Wie weit kann man maximal in eine Richtung gehen? n + (n-2) + (n-4) + (n-6)...
Man darf ja nicht zweimal hintereinander in die gleiche Richtung gehen. Wenn man dazwischen nicht zurück geht, kannst du so die maximale Entfernung in eine Richtung bestimmen. Für ungerades n ist das 1 + 3 + 5 + ... + (n-2) + n. Die Formel ist: u(n) = ((n+1)/2)^2. Für gerades n ist es 2 + 4 + 6 + ... + (n-2) + n. Die Formel dafür ist g(n) = (n/2)*(n/2+1). Wenn der Abstand einer der Koordinaten des Zielfeldes größer als der maximale Abstand vom Startfeld für das gegebene n ist, so ist dieser Punkt auch nicht zu erreichen.

[BLUEblue]

danke für die Antworten, so langsam verstehe ich das ganze.....