home
Der schrullige Graf Rüdeger ist bekannt für seine spleenigen Ideen, mit denen er die Besucher auf seiner Burg in Lüne immer wieder überrascht. Jetzt hat er sich für seine Eingangspforten verspielte, aufwändige Schließanlagen konstruieren lassen. Eine Schließanlage besteht aus N Riegeln, deren Stellungen (auf oder zu) von außen sichtbar sind. Sie können einzeln nur nach den folgenden Regeln bewegt werden:
  1. Riegel 1 kann immer bewegt werden.
  2. Riegel 2 kann nur bewegt werden, wenn Riegel 1 auf ist.
  3. Jeder andere Riegel kann genau dann bewegt werden,
    wenn der Riegel mit der nächst kleineren Nummer auf
    ist und alle mit noch kleineren Nummern zu sind.
  4. Der Riegel N kann außerdem noch bewegt werden,
    wenn alle Riegel 1 bis N-1 zu sind.
Eine Pforte lässt sich nur öffnen, wenn alle Riegel auf sind. Beispiel für N=4 (in der letzten Zeile der Tabelle bedeutet Ri, dass Riegel i bewegt wurde):
Graf Rüdeger hat mehrere Schließanlagen mit unterschiedlich vielen Riegeln bauen lassen. Leider kommt es häufig vor, dass Besucher einige Riegel bewegen, die Pforte aber nicht öffnen können und die Schließanlage unordentlich hinterlassen. Für Graf Rüdeger ist eine Pforte nur dann ordentlich geschlossen, wenn alle Riegel zu sind. Jeden Abend muss deshalb der Diener von Graf Rüdeger durch die Burg gehen und an allen Pforten die Riegel schließen. Du sollst ihm helfen.
Aufgabe
Schreibe ein Programm, das für ein beliebiges N und einen beliebigen Zwischenzustand einer Schließanlage die Folge derjenigen Riegel ausgibt, die der Diener bewegen muss, um die Pforte ordentlich zu schließen. Erzeuge für drei verschiedene Schließanlagen mit N > 4 und je zwei Zwischenzustände solche Bewegungsfolgen. Eine Bewegungsfolge
davon soll für N = 6 und den Zwischenzustand (zu,zu,zu,auf,auf,zu) erzeugt werden.