Informatik Aufgabe
-
Hallo, weiß jemand wie die Aufgabe 3 von der Seite geht? http://info10.arma-web.de/zusatzaufgaben.html
-
-
der link bringt mich jetzt auch nicht so viel weiter, kann mir jemand sagen mit welchem Ansatz man das lösen kann?
-
blslsllssl schrieb:
der link bringt mich jetzt auch nicht so viel weiter, kann mir jemand sagen mit welchem Ansatz man das lösen kann?
Na, denen in dem Link! Inwiefern war der für dich denn nicht hilfreich? Der hat doch sogar verschiedene Vorschläge zur Lösung mit Pro und Contra und weiterführenden Links. Zum Beispiel wird erklärt, wieso der einfache Wandverfolger bei deinem Labyrinth nicht funktionieren wird. Da dein Roboter, wenn ich das richtig sehe, Felder markieren kann, bietet sich der Trémaux-Algorithmus oder der Algorithmus von Gaston Tarry an.
-
Soweit ich das noch weiß, kann man den Ausgang eines Labyrinths wie dem in der Aufgabe dadurch finden, daß man immer an einer Seite lang läuft. Ob man nun den Ausgang sucht, oder eine andere bestimmte Stelle, dürfte egal sein.
-
redrew99:
Das klappt hier aber nicht. Das soll ja von jeder Stelle aus dem Labyrinth funktionieren und es gibt Mauerbereiche, die "schwimmen", also mit dem Außenrand nicht befestigt sind. Wenn man da an der Wand entlangläuft, läuft man ständig im Kreis herum.
-
Stimmt, da sind "Inseln" mit dabei. Das hatte ich nicht gesehen.
Dann muß man halt noch eine Methode mit einbauen, wie man die erkennen kann.
Also z.B. jedes Feld nummerieren und sobald man die, sagen wir, 2 (oder sicherheitshalber 3)mal betreten hat, muß man die Seite wechseln.
-
Das klappt auch nicht. Es gibt schon Erweiterungen für deine Vorgehensweise, siehe z.B. den Pledge-Algorithmus. Aber du löst das falsche Problem: Es geht nicht darum, einen Ausgang am Rand des Labyrinths zu finden, sondern einen Punkt innerhalb des Labyrinths. Dafür sind die von SeppJ genannten Algorithmen passend.
-
Ob man nun den Ausgang sucht, oder ein bestimmtes Feld, ist doch das gleiche.
-
Nicht wenn man annimmt, dass der Ausgang immer am Rand liegt.
-
Stimmt, ein Problem könnte darin bestehen, daß man sich mit 2 Inseln dauerhaft abwechselt. (also mit Feldern nummerieren, etc.)
-
redrew99 schrieb:
Stimmt, ein Problem könnte darin bestehen, daß man sich mit 2 Inseln dauerhaft abwechselt. (also mit Feldern nummerieren, etc.)
Du entwickelst gerade selbstständig die auf Wikipedia beschriebenen Algorithmen
. Aber lass dich nicht aufhalten, so etwas selber auszutüfteln ist spaßig und lehrreich 
.
-
Ich weiß nicht warum wir schon so schere aufgaben bekommen, wir haben gerade mal ein paar Java Grundlagen gelernt. Mein Lehrer hat gesagt die Aufgabe sei einfach.
-
Ist sie auch. Algorithmen von Wikipedia abschreiben ist ziemlich einfach.
-
ich hab so ein Labyrinth mal vom Ziel aus "geflutet": in alle angrenzenen Felder zum aktuellen eine Zahl reingsschrieben, die um eins höher als beim aktuellen Feld ist. Wenn ich dann beim Start war, konnt ich einfach den absteigenden Zahlen folgen (und wusste gleich, wie weit ich zu laufen habe)
-
zwutz schrieb:
ich hab so ein Labyrinth mal vom Ziel aus "geflutet": in alle angrenzenen Felder zum aktuellen eine Zahl reingsschrieben, die um eins höher als beim aktuellen Feld ist. Wenn ich dann beim Start war, konnt ich einfach den absteigenden Zahlen folgen (und wusste gleich, wie weit ich zu laufen habe)
Nennt sich Breitensuche. Klappt aber nur, wenn du die Zielposition schon vorher kennst
Könnte aber durchaus sein, dass das hier sogar gemeint ist.
-
Ja, aber ich war damals der Meinung, dass es was anderes ist
Aber stimmt, strenggenommen ist es das gleiche. Dafür hab ich aber von jedem Punkt aus dann jederzeit die Möglichkeit, ohne weiteren Aufwand zum Ziel zu kommen
-
Ok habs jetzt endlich mit dem Tremaux Algorithmus gelöst, der funktioniert super!
-
SeppJ schrieb:
redrew99 schrieb:
Stimmt, ein Problem könnte darin bestehen, daß man sich mit 2 Inseln dauerhaft abwechselt. (also mit Feldern nummerieren, etc.)
Du entwickelst gerade selbstständig die auf Wikipedia beschriebenen Algorithmen
. Aber lass dich nicht aufhalten, so etwas selber auszutüfteln ist spaßig und lehrreich .Programmieren hat schon ganz schön an Reiz verloren, seit alles immer Internet zu finden ist.
-
Auch deshalb, weil schon es schon so gut für jedes Problem eine Software gibt.
Ausnahmen gibt es vielleicht noch in hochspezialisierten Bereichen, aber sonst sieht es ziemlich mau aus.
