"Stack"-Problem
Verfasst: Mo Mai 05, 2014 3:51 pm
Tach!
Ich bin neulich auf ein Problem gestoßen, von dem ich nicht weiß, ob es sich programmieren lässt oder nicht. Darauf gekommen bin ich durch ein Buch, in dem es unter anderem um das Pfannkuchen Problem ging:
Der Kellner serviert x Pfannkuchen. Wie oft muss man die Pfannkuchen im schlimmsten Fall wenden, um sie der Größe nach zu sortieren (logischerweise sind die größeren unten). Die Anzahl, wie oft gewendet wird, beschreibt Pn.
Ich denke das lässt sich recht gut Vorstellen. Aber eigentlich geht es um ein ganz anderes Problem nämlich:
Man hat vor sich 3 Stäbe (ich hab sie einfach mal Stacks genannt). Auf dem linken sind 5 Scheiben übereinander gestapelt, in der Reihenfolge 1-2-3-4-5 (5 ganz unten).
Das Ziel ist es, die gleiche Formation der Blöcke auf einem anderen Stab anzuordnen mit der minimalen Anzahl an Zügen.
Nachdem ich beim ersten Programmierversuch gemerkt habe, dass es doch nicht ganz so einfach zu programmieren ist wie es aussieht, hab ich aufgeschrieben was wichtig ist und bin die einzelnen Züge durchgegangen.
Ich bin mir sicher, dass fast jeder das Problem schon mal gesehen hat. In erster Linie ist für mich wichtig, ob das Problem programmierbar ist. Vielleicht weiß da der ein oder andere mehr.
Danke!
PS: Bitte keine Spoiler
Ich bin neulich auf ein Problem gestoßen, von dem ich nicht weiß, ob es sich programmieren lässt oder nicht. Darauf gekommen bin ich durch ein Buch, in dem es unter anderem um das Pfannkuchen Problem ging:
Der Kellner serviert x Pfannkuchen. Wie oft muss man die Pfannkuchen im schlimmsten Fall wenden, um sie der Größe nach zu sortieren (logischerweise sind die größeren unten). Die Anzahl, wie oft gewendet wird, beschreibt Pn.
Ich denke das lässt sich recht gut Vorstellen. Aber eigentlich geht es um ein ganz anderes Problem nämlich:
Man hat vor sich 3 Stäbe (ich hab sie einfach mal Stacks genannt). Auf dem linken sind 5 Scheiben übereinander gestapelt, in der Reihenfolge 1-2-3-4-5 (5 ganz unten).
Das Ziel ist es, die gleiche Formation der Blöcke auf einem anderen Stab anzuordnen mit der minimalen Anzahl an Zügen.
Nachdem ich beim ersten Programmierversuch gemerkt habe, dass es doch nicht ganz so einfach zu programmieren ist wie es aussieht, hab ich aufgeschrieben was wichtig ist und bin die einzelnen Züge durchgegangen.
Ich bin mir sicher, dass fast jeder das Problem schon mal gesehen hat. In erster Linie ist für mich wichtig, ob das Problem programmierbar ist. Vielleicht weiß da der ein oder andere mehr.
Danke!
PS: Bitte keine Spoiler