class Hanoi {

 // Prozedur "bewege" bewegt REKURSIV n Scheiben von Turm a nach Turm b und
 // benutzt als Zwischenspeicher Turm z.
 // Hierbei muss in Teilschritte zerlegt werden, da nach den Spielregeln
 // 1. immer nur eine Scheibe bewegt werden darf,
 // 2. immer nur eine kleinere auf eine größere Scheibe abgelegt werden darf.

 static long zaehler = 0;

 static void bewege (char a, char b, char c, int n) {
  if (n == 1)
   System.out.println("Zug " + (++zaehler) +
                      ": Bewege Scheibe von Turm " + a + " auf Turm " + b);
  else {
   bewege (a, c, b, n-1); // die oberen n-1 Scheiben von a nach c...
   bewege (a, b, c, 1);   // die größte Scheibe von a nach b...
   bewege (c, b, a, n-1); // die oberen n-1 Scheiben von c nach b.
  }
 }

 public static void main (String[] args) {
   java.util.Scanner sc = new java.util.Scanner(System.in);
   System.out.print("Bitte Anzahl von Scheiben eingeben: ");
   int anzahl = sc.nextInt();
   // Gib die notwendigen Züge für einen Stapel der angegebenen Höhe
   bewege('1', '2', '3', anzahl);
 } // main

} // Hanoi