# Türme von Hanoi - Iterator



## bvdcomp (28. Feb 2011)

Hallo zusammen,

Kann mir jemand sagen wie ich Daten von einer ArrayList in einer anderem Methode iterativ aufrufen kann?

```
public class Hanoi{
	public Hanoi(){
		ArrayList<String> dataL = new ArrayList<String>();
		dataL.add("A");
		dataL.add("B");
		dataL.add("C");
	}
```

Ich habe folgendes versucht:

```
System.out.println("Verschiebe disk von  " + dataL.get(von) + " nach " + dataL.get(nach));
```
Als Meldung kommt: dataL cannot be resolved


----------



## Gast2 (28. Feb 2011)

dataL ist nur innerhalb des Konstruktors gültig.
Lege die List als Klassenvariable an, dann kannst du auch außerhalb des Konstruktors drauf zugreifen.


----------



## bvdcomp (28. Feb 2011)

OK das habe ich gemacht:

```
class Stangen{
	public Stangen(){
		ArrayList<String> dataL = new ArrayList<String>();
		dataL.add("A");
		dataL.add("B");
		dataL.add("C");
	}
}
...
...
System.out.println("Verschiebe disk von  " + Stangen.dataL.get(von) + " nach " + Stangen.dataL.get(nach));
		}
```

Aber es geht ja nicht, wie kann ich nun drauf zugreifen?


----------



## bvdcomp (28. Feb 2011)

ahhh, ok. ich hab nohc was geändert.


```
public static void main(String []args){
		private int n = 4;
		Iterator<Hanoi> iter = Stangen.start();
        while (iter.hasNext()){
            iter.next().start(n);
        }
	}
}
class Stangen{
	public static Iterator<Hanoi> start(){
		ArrayList<String> dataL = new ArrayList<String>();
		dataL.add("A");
		dataL.add("B");
		dataL.add("C");
		
		return dataL;
	}
}
```

Aber drauf zu greifen geht immer noch nicht. muss ich einen Cast machen?

```
System.out.println("Verschiebe disk von  " + ((ArrayList<String>) Stangen.start()).get(von) + " nach " + dataL.get(nach));
		}
```


----------



## Volvagia (28. Feb 2011)

```
class Stangen{
	private ArrayList<String> dataL;

	public Stangen(){
		dataL = new ArrayList<String>();
		dataL.add("A");
		dataL.add("B");
		dataL.add("C");
	}
}
```

Klassenvariablen stehen innerhalb der Klassen außerhalb von Methoden.

Edit: Du hast im Rückgabewert geschrieben, du willst einen Iterator zurückgeben, gibts aber eine ArrayList zurück. Versuche mal "return(dataL.iterator());"


----------



## bvdcomp (28. Feb 2011)

OK, aber wie greife ich nun auf den Konstruktor Stangen?


```
System.out.println("Verschiebe disk von  " + Stangen.dataL.get(von) + " nach " + Stangen.get(nach);
		}
	}
	
	public static void main(String []args){
		int n = 4;
		Iterator<Hanoi> iter = Stangen.Stangen();
        while (iter.hasNext()){
            iter.next().start(n);
        }
	}
}
class Stangen{
    private ArrayList<String> dataL;

    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }
}
```

Ich möchte ja auf dataL zugreifen un über diese Arraylist zu iterieren.


----------



## Gast2 (28. Feb 2011)

Um dem elend mal ein ende zu bereiten 


```
import java.util.ArrayList;
import java.util.List;

class Stangen{
    private List<String> dataL;
 
    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }
    
    public List<String> getDataL() {
    	return dataL;
    }
}
```


```
import java.util.List;

public class Main {
 
  
    public static void main(String[] args) {
       Stangen stangen = new Stangen();
       List<String> data = stangen.getDataL();
       
       for (String s : data) {
    	   System.out.println(s);
       }
       
    }
 
}
```


----------



## Volvagia (28. Feb 2011)

Ein Tipp, ließ dir die Basics zu OOP in Java durch. Da wir aber wohl beide wissen, dass du das nicht machen wirst:


```
public static void main(String []args)
    {
        Stangen stangen = new Stangen();
        ArrayList<String> dataL = stangen.getData();
        
        System.out.println("Hallo, ich bin die ArrayList " + dataL.toString() + ", und habe " + dataL.size() + " eintraege. :D";
    }
}
class Stangen{
    private ArrayList<String> dataL;
 
    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }
    public ArrayList<String> getData()
    {
        return(dataL);
    }
}
```


----------



## bvdcomp (28. Feb 2011)

An beide

Danke vielmals für eure Hilfe. Ich möchte dies aber mittels while Schleife machen:


```
public static void main(String []args){
        int n = 4;
        Iterator<Hanoi> iter = (Iterator<Hanoi>) Stangen.getData();
        while (iter.hasNext()){
            iter.next().start(n);
        }
    }
```
Ich erhalte dann aber eine NullPointerException


----------



## Volvagia (28. Feb 2011)

Zeig die untere Klasse auch mal.
Du kannst eine ArrayList nicht in einen Iterator casten, benutze iterator().

AbstractList (Java 2 Platform SE v1.4.2)


----------



## Shulyn (1. Mrz 2011)

doppelpost -.-


----------



## Shulyn (1. Mrz 2011)

Da du schon eine List bzw. ArrayList hast, solltest du den Iterator benutzen den diese besitzt.


```
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Stangen {
    private List<String> dataL;
    
    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }
    
    public List<String> getDataL() {
        return dataL;
    }

}

class Main {

    public static void main(String[] args) {
       Stangen stangen = new Stangen();
       List<String> data = stangen.getDataL();
       

       ListIterator<String> iIterator = data.listIterator();
           while (iIterator.hasNext()) {
            String deinText = (String) iIterator.next();
            System.out.println(deinText);
        }
    }
 
}
```


----------



## bvdcomp (1. Mrz 2011)

An alle,
 Danke für euere Einträge.

Ich bin nun schon relativ weit gekommen. Nun ist mir nicht ganz klar was ich als { return  ; } geben muss. Die Methode iterator() muss meines Wissens einen hasNext() ,next() und remove() haben:

```
System.out.println("Verschiebe disk von  " + Stangen.dataL.get(von) + " nach " + Stangen.dataL.get(nach));
			}
	}
	public static void main(String []args){
        int n = 4;
        Iterator<Hanoi> iter = Stangen.iterator();
        while (iter.hasNext()){
            iter.next().start(n);
        }
    }
}

class Stangen{
    static ArrayList<String> dataL;
 
    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }
    public static Iterator<Hanoi> iterator()
    {
        return new Iterator<Hanoi>(){
            public boolean hasNext()
            { return  ; }

            public Hanoi next()
            {
                if (!hasNext())
                    throw new InvalidOperationException();
                return next();
            }
            
            public void remove() {}
        };
    }
}
```

Ansonsten sollte es eigentlich nicht so schlecht sein,.


----------



## Volvagia (1. Mrz 2011)

Gib doch einfach dataL.iterator() zurück. ;(
Übrigens sollte man von einer Instanzmethode/Konstruktor nicht in einer statische Variable schreiben. Nimm dafür am Besten nen static konstructor.


----------



## bvdcomp (1. Mrz 2011)

Das geht ja nicht. Wenn ich das mache, heist es:

```
Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	Type mismatch: cannot convert from Iterator<String> to boolean
```


----------



## Volvagia (1. Mrz 2011)

```
public static Iterator<Hanoi> iterator()
{
     return(dataL.iterator());
}
```


----------



## bvdcomp (1. Mrz 2011)

Das geht leider immer noch nicht:

```
Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
	Type mismatch: cannot convert from Iterator<String> to Iterator<Hanoi>
```


----------



## Volvagia (1. Mrz 2011)

Ups, mein Fehler. Hab den Blödsinn übersehen.


```
public static Iterator<String> iterator()
{
     return(dataL.iterator());
}
```


----------



## Aldimann (1. Mrz 2011)

Oh mein Gott!

Also lieber Themenstarter, von dir möchte ich eigentlich mal in knappen worten gesagt bekommen warum du um Gottes willen unbedingt einen Iterator haben möchtest?!

Oben wurde die JavaDoc zu ArrayList gepostet da kann man gut nachlesen wie man sonst noch so auf ArrayLists zugreifen kann...

Und dann doch bitte über ein for each oder doch zumindest eine for Schleife, wenn es schon keinen guten Grund für dieses Mords Iterator Konstrukt gibt.

Dann muss ich meinem Vorredner recht geben, du solltest dir die Grundkonzepte von OOP erklären lassen. Ob du nun willst oder nicht aber wenn du über deinen 10 Zeiler hinaus kommen willst bleibt dir nichts anderes übrig.

Google am besten mal nach "java ist auch eine insel"...


----------



## bvdcomp (1. Mrz 2011)

Aldimann:
Ich will diesen Iterator da es in der Aufgabenstellung steht!
Aufgabenstellung:Schreiben Sie das rekursive Programm zum Turm von Hanoi aus Abschnitt 3.1.4 um in ein rein iteratives Programm; verwenden Sie dazu die Technologien aus 3.2.4 (Eben mittels Iterator)


----------



## Aldimann (1. Mrz 2011)

In dem Fall nehm ich es natürlich zurück.

In der Praxis ist es so, dass man eben Iteratoren nur noch relativ selten her nimmt, da es einfachere Konstrukte gibt um eben über Listen o.ä. drüber zu laufen. (for und foreach Schleifen z.B.)


----------



## alpiman (1. Mrz 2011)

Aldimann hat gesagt.:


> In dem Fall nehm ich es natürlich zurück.
> 
> In der Praxis ist es so, dass man eben Iteratoren nur noch relativ selten her nimmt, da es einfachere Konstrukte gibt um eben über Listen o.ä. drüber zu laufen. (for und foreach Schleifen z.B.)



Und was ist mit Datenstrukturen, die keine indizierten Zugriff auf ihre Elemente erlauben...z.B. bei Map, Set, Tree usw. So pauschal lässt sich das nicht sagen.


----------



## xehpuk (2. Mrz 2011)

alpiman hat gesagt.:


> Und was ist mit Datenstrukturen, die keine indizierten Zugriff auf ihre Elemente erlauben...z.B. bei Map, Set, Tree usw. So pauschal lässt sich das nicht sagen.


Also da tuts auch eine foreach. Aber Iteratoren sind schon nützlich.


----------



## bvdcomp (2. Mrz 2011)

Also soll ich jetzte einen Iterator verwenden oder nicht?
lieber währe es mir nicht, da ich es nicht ganz fertig kriege 

Mein Code:

```
import java.util.ArrayList;
import java.util.Iterator;
public class Hanoi{
	
	public void start(int n){
		System.out.println("Türme von Hanoi - Iterativ");
		System.out.println("_________________________________________");
		move(n);//N-Ringe werden im Array angelegt
	}
		
	public static void move(int n) {
		
		int bewegungen = 1; // 2 **n-1 berechnen
		for(int i = 0; i < n; ++i) {
			bewegungen *= 2;
		}
		for(int aktuelleB = 1; aktuelleB <= bewegungen; ++aktuelleB) {
			int i = aktuelleB;
			int scheibe = 1;
			while (i % 2 == 0) {
				i /= 2;
				++scheibe;
			}
			int bewegungenDerScheibe = i / 2;
		
			int schritt = 2 - (n + scheibe) % 2;
			int von = (bewegungenDerScheibe * schritt) % 3;
			int nach = (von + schritt) % 3;
			System.out.println("Verschiebe disk von  " + Stangen.dataL.get(von) + " nach " + Stangen.dataL.get(nach));
			}
	}
	public static void main(String []args){
        int n = 4;
        Iterator<Hanoi> iter = Stangen.iterator();
        while (iter.hasNext()){
            iter.next().start(n);
        }
    }
}

class Stangen{
    static ArrayList<String> dataL;
 
    public Stangen(){
        dataL = new ArrayList<String>();
        dataL.add("A");
        dataL.add("B");
        dataL.add("C");
    }

   public static Iterator<Hanoi> iterator()
   {
       return new Iterator<Hanoi>(){
    	   private int i = 0;
    	   public boolean hasNext() { return i < dataL.size(); }
           public Hanoi next()
           {
               if (!hasNext())
                   throw new InvalidOperationException();
               return next();
           }
           
           public void remove() {}
       };
   }
}

class InvalidOperationException extends IllegalStateException
{

    public InvalidOperationException(String message)
    { super(message); }

    public InvalidOperationException()
    { super(); }
}
```

Beim kompilieren erhalte ich folgenden Fehler.

```
Exception in thread "main" java.lang.NullPointerException
	at Stangen$1.hasNext(Hanoi.java:69)
	at Hanoi.main(Hanoi.java:47)
```


----------



## Volvagia (2. Mrz 2011)

Willst du es nicht richtig machen? Ich habe schon zig mal geschrieben, wies geht.
Du greifst auf eine Variable zu, der keine Referenz zugewiesen ist, und in die dementsprechend "auf null zeigt".

btw. Wird bei einer for each nicht auch ein Iterator benutzt? Muss ja ein ensprechendes Interface implementieren, ich glaube Iteratable oder so ähnlich.  (Zu müde zum nachsehen.)


----------



## hanoiii (2. Mrz 2011)

bvdcomp hat gesagt.:


> ```
> public static void move(int n) {
> ```



bist du sicher, das du weißt, was du da tust? Die Methode hat ja hat eine Ganzzahl als Argument, keinen Rückgabewert und gibt nur etwas auf der Ausgabe aus oder verändert Klassenvariablen? Für Hanoi gibt es doch einen "einfacheren" iterativen Algorithmus...


----------



## alpimanhanoiii (2. Mrz 2011)

Volvagia hat gesagt.:


> btw. Wird bei einer for each nicht auch ein Iterator benutzt? Muss ja ein ensprechendes Interface implementieren, ich glaube Iteratable oder so ähnlich.  (Zu müde zum nachsehen.)



genau richtig...Allerdings "sieht" man keine Variablendeklaration usw.


----------



## bvdcomp (2. Mrz 2011)

hanoiii hat gesagt.:


> Für Hanoi gibt es doch einen "einfacheren" iterativen Algorithmus...



Und der währe??

Ich habe mich bislang auf diesen konzentriert, aber wenn Du etwas besseres kennst, währe ich sehr froh mehr darüber zu erfahren.


----------



## Aldimann (2. Mrz 2011)

Um das nochmal richtig zu stellen. Man sollte nicht NIEMALS einen Iterator verwenden, sondern nur dann wenn er wirklich notwendig ist.

So ganz spontan fällt mir gerade kein Beispiel ein, aber es gibt aufjedenfall welche ...


----------



## Andi_CH (2. Mrz 2011)

3 Sekunden googeln - na ja, den Link mit dem hässlichsten Code poste ich mal.

das ist hier

2. Seite oben links - so richtig zum Abgewöhnen

EDIT: und bei einer geraden Anzahl von Scheiben so richtig inneffizient


----------



## Shulyn (2. Mrz 2011)

bvdcomp hat gesagt.:


> Aldimann:
> Ich will diesen Iterator da es in der Aufgabenstellung steht!
> Aufgabenstellung:Schreiben Sie das rekursive Programm zum Turm von Hanoi aus Abschnitt 3.1.4 um in ein rein iteratives Programm; verwenden Sie dazu die Technologien aus 3.2.4 (Eben mittels Iterator)



Du hast da etwas falsch verstanden.
Eure Lösung ist "Rekursiv" und soll jetzt "Iterativ" werden. Das hat erstmal NICHTS mit einem Java "Iterator" zu tun.

Schau mal hier http://www.java-forum.org/java-basics-anfaenger-themen/29606-iterativ-rekursiv-java.html

Das erläutert dir etwas was dein/euer Lehrer mit "Iterativ" meint.


----------



## Landei (2. Mrz 2011)

Korrekt. Jeder Iterator arbeitet "iterativ", aber nicht jedes iterative Programm muss einen Iterator benutzen. Standardbeispiel:


```
//rekursive Fakultäts-Funktion
public static long fakR(int n){
   if(n < 2) {
      return 1L;
   } else {
      return n*fakR(n-1); //Selbstaufruf -> rekursiv
   }  
}

//iterative Fakultäts-Funktion
public static long fakI(int n){
    long f = 1L;
    for(int i = 1; i <= n; i++) { //Schleife -> iterativ
       f = f*i; 
    }
    return f;
}
```


----------



## Aldimann (2. Mrz 2011)

Shulyn hat gesagt.:


> Du hast da etwas falsch verstanden.
> Eure Lösung ist "Rekursiv" und soll jetzt "Iterativ" werden. Das hat erstmal NICHTS mit einem Java "Iterator" zu tun.
> 
> Schau mal hier http://www.java-forum.org/java-basics-anfaenger-themen/29606-iterativ-rekursiv-java.html
> ...



ROFL! Das mal n guter Hinweis 

So genau hab ich den Text gar nicht gelesen


----------



## Andi_CH (2. Mrz 2011)

Was Stiften im 2. Lehrjahr (ja, wir sagen immer noch so zu den Azubis) so können - ich staune - Lernt Mediamatiker und weil sein Chef die ganze Arbeit an unseren Routern alleine gemacht hat, tippselte er mal schnell ein Programm.
Wärend dem Mittagessen haben wir mit 4 Münzen iterativ Hanoi gespielt und jetzt ist das Programm fertig.

Nein, ich poste es (noch) nicht - erst noch etwas mehr Kommentar rein und dann landet es bei den Codeschnipseln zusammen mit einer rekursiven Lösung.

So nebenei - wollen wir jetzt schon alle Versionen von Tannenbaum zeichnen sammeln? Nächste Weihnacht kommt bestimmt :lol: oder kommen erst die Ostereier?


----------



## alpimanhanoiii (2. Mrz 2011)

bvdcomp hat gesagt.:


> Und der währe??
> 
> Ich habe mich bislang auf diesen konzentriert, aber wenn Du etwas besseres kennst, währe ich sehr froh mehr darüber zu erfahren.



Wikipedia?

Türme von Hanoi ? Wikipedia


> Solange sich auf wenigstens einem der beiden Stäbe A und B Scheiben befinden, wird erst die kleinste Scheibe (S1) im Uhrzeigersinn und anschließend, sofern dies möglich ist, eine von S1 verschiedene Scheibe verschoben. Als Pseudocode notiert ergibt sich also folgender Algorithmus:
> 
> 
> ```
> ...



Der Beweis, dass die optimale Zugfolge generiert wird, ist "schwerer" als der Algorithmus...


----------



## Marco13 (2. Mrz 2011)

Aldimann hat gesagt.:


> In der Praxis ist es so, dass man eben Iteratoren nur noch relativ selten her nimmt, da es einfachere Konstrukte gibt um eben über Listen o.ä. drüber zu laufen. (for und foreach Schleifen z.B.)





xehpuk hat gesagt.:


> Also da tuts auch eine foreach. Aber Iteratoren sind schon nützlich.



Foreach kann man (neben Arrays) nur auf Objekte anwenden, die "Iterable" sind - und "Iterable" ist ein Interface, das einen Iterator zurückgeben kann. Für sowas wie

```
for (String zug : meinHanoiDing) System.out.println(zug);
```
muss "meinHanoiDing" eben Iterable sein, d.h. einen Iterator zurückliefern können.


----------



## xehpuk (2. Mrz 2011)

Dass dabei dann "intern" ein Iterator Verwendung findet, ist schon klar. Wenn es jetzt darum ginge, gar keine Iteratoren zu verwenden, dann dürfte man ja auch kein foreach benutzen. Hier ging es aber wohl darum, dass man ihn nicht explizit verwendet.


----------



## hanoiii (2. Mrz 2011)

Ist zwar etwas unübersichtlich, weil Stab bei mir Deque ist und keine eigene Klasse, aber so würde das implementiert sein:


```
public static void hanoi(Deque<Integer> a, Deque<Integer> b, Deque<Integer> c) {
        while (a.size() > 1 || b.size() > 1) {
            if (a.getFirst() < b.getFirst() && a.getFirst() < c.getFirst()) {
                move(a, b);
                if (a.getFirst() < c.getFirst()) {
                    move(a, c);
                } else if (c.getFirst() < a.getFirst()) {
                    move(c, a);
                }
            } else if (b.getFirst() < c.getFirst()) {
                move(b, c);
                if (a.getFirst() < b.getFirst()) {
                    move(a, b);
                } else if (b.getFirst() < a.getFirst()) {
                    move(b, a);
                }
            } else {
                move(c, a);
                if (b.getFirst() < c.getFirst()) {
                    move(b, c);
                } else if (c.getFirst() < b.getFirst()) {
                    move(c, b);
                }
            }
        }
    }

    public static void move(Deque<Integer> from, Deque<Integer> to) {
        System.out.println("from: " + from + " -> to: " + to);
        to.addFirst(from.removeFirst());
    }

    public static void main(String[] args) {
        hanoi(new ArrayDeque<Integer>(Arrays.asList(new Integer[]{1, 2, 3, Integer.MAX_VALUE})),
                new ArrayDeque<Integer>(Arrays.asList(new Integer[]{Integer.MAX_VALUE})),
                new ArrayDeque<Integer>(Arrays.asList(new Integer[]{Integer.MAX_VALUE})));
    }
```

Hab auch das Problem, dass für ungerade Anzahl an Scheiben auf Stab a er alle Scheiben zuerst auf b platziert und dann auf c. Das lässt sich aber anscheinend nicht vermeiden^^


----------



## Andi_CH (3. Mrz 2011)

Hier die versprochene Lösung von gestern (Die vom "Stift" ;-) ) geändert habe ich gar nichts ausser zwei oder drei Tippfehlerchen welche aber keinen Einfluss auf die Funktion hatten:


```
/**
 * Dieses Programm löst das Problem "Türme von Hanoi" iterativ
 * Das schwierigste war den iterativen Alogrithmus zu finden - ich wäre nicht auf
 * die Idee gekomment, dass es auch so lösbar ist.
 * 
 * Der Code steht unter der WTFPL-Lizenz
 *  
 * @author MH
 * @version 2011-03-02
 */
public class HanoiIterativ {

	private final int anzahlScheiben;
	int[][] feld;

	public HanoiIterativ(int anzahl) {
		anzahlScheiben = anzahl;
		feld  = new int[3][anzahlScheiben];
		init();
	}

	public void init() {
		for (int i=0; i<anzahlScheiben; i++) {
			feld[0][i] = i+1;
			feld[1][i] = 0;
			feld[2][i] = 0;
		}
	}

	private void printFeld() {
		final String format = "%2d  %2d  %2d";
		for (int i=0; i<anzahlScheiben; i++) {
			System.out.println(String.format(format, feld[0][i], feld[1][i], feld[2][i]));
		}
		System.out.println("----------");
	}

	/**
	 * Gibt den Wert der obersten Scheibe auf einer bestimmten Position zurück
	 * @param position
	 * @return Wert
	 */
	private int topValue(int pos) {
		for(int i=0; i<anzahlScheiben; i++) {
			if(feld[pos][i] !=0 )
				return feld[pos][i]; 
		}
		return 0;
	}

	/**
	 * bestimmten den ersten freien Level auf einer bestimmten Position
	 * @param pos
	 * @return level (-1 wenn kein Platz frei ist)
	 */
	private int freierLevel(int pos) {
		for (int i=anzahlScheiben-1; i>=0; i--) {
			if (feld[pos][i] == 0)
				return i;
		}
		return -1;
	}

	/**
	 * bestimmten den letzten belegten Level auf einer bestimmten Position
	 * @param pos
	 * @return level (-1 wenn alle frei sind)
	 */
	private int belegterLevel(int pos) {
		for (int i=0; i<anzahlScheiben; i++) {
			if (feld[pos][i] != 0)
				return i;
		}
		return -1;
	}

	/**
	 * Sucht die nächste Position auf die die oberste Scheibe von start verschoben werden kann
	 * Wenn nicht geschoben werden kann wird -1 zurückgegeben
	 * @param start
	 * @return mögliche Zielposition
	 */
	private int nextAvailable(int start) {
		int wertVon = topValue(start);
		if (wertVon==0)
			return -1;
		int i = (start+1)%3;
		while (i != start) {
			int wertNach = topValue(i);
			if ((wertVon<wertNach) || (wertNach==0))
				return i;
			i = (++i)%3;
		}
		return -1;
	}

	/**
	 * Entfernt die oberste Scheibe einer position (setzt wert auf 0)
	 * @param pos
	 */
	private void eraseTop(int pos) {
		feld[pos][belegterLevel(pos)] = 0;
	}

	/**
	 * Setzt die oberste Scheibe einer Position - überprüft wird nichts!
	 * @param positon
	 * @param wert
	 */
	private void setTop(int pos, int wert) {
		int freierLevel = freierLevel(pos); 
		feld[pos][freierLevel] = wert;
	}

	/**
	 * Schiebt eine Scheibe von nach ...
	 * überprüft wir nichts!
	 * @param von
	 * @param nach
	 */
	private void schiebe(int von, int nach) {
		setTop(nach, topValue(von));
		eraseTop(von);
	}

	private boolean fertig() {
		for (int i=1; i<3; i++) {
			if(freierLevel(i)==-1)
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		HanoiIterativ hi = new HanoiIterativ(5);
		hi.printFeld();
		int von = 0;
		while(!hi.fertig()) {
			int nach = hi.nextAvailable(von);
			if (nach != -1) {
				System.out.println("Schiebe von " + von + " nach " + nach);
				hi.schiebe(von, nach);
				hi.printFeld();
				von = (nach+1)%3;
			} else {
				von = (von+1)%3;
			}
		}
		System.out.println("Fertig!");
	}
}
```


----------



## Andi_CH (3. Mrz 2011)

... und als Ergänzung bzw. zum Vergleich noch die rekursive Lösung


```
public class TowersOfHanoiRecursive {
	private static final int anzScheiben = 10;
	private static final int[] platzA = new int[anzScheiben];
	private static final int[] platzB = new int[anzScheiben];
	private static final int[] platzC = new int[anzScheiben];
	private static int counter = 0;

	private static void init() {
		for(int i=0; i<anzScheiben; i++) {
			platzA[i] = anzScheiben-i;
			platzB[i] = 0;
			platzC[i] = 0;
		}
	}
	private static void showPlaces() {
		System.out.println("Zug Nummer " + counter);
		System.out.println(" A  B  C");
		for(int i=anzScheiben-1; i>=0; i--) {
			String output = "%2d %2d %2d";
			System.out.println(String.format(output, platzA[i], platzB[i], platzC[i]));
		}
		System.out.println("");
	}
	private static int firstFree(int[] pArr) {
		for(int i=0; i<anzScheiben; i++)
			if (pArr[i]==0) return i;
		return anzScheiben;
	}
	private static void schiebeEineScheibe(int[] pVon, int[] pNach) {
		counter++;
		pNach[firstFree(pNach)] = pVon[firstFree(pVon)-1];
		pVon[firstFree(pVon)-1]=0;
		showPlaces();
	}
	private static void schiebe(int pAnz, 
			int[] pVon, int[] pNach, int[] pHilf) {
		if (pAnz==1) {
			schiebeEineScheibe(pVon, pNach);
		} else {
			schiebe(pAnz-1, pVon, pHilf, pNach);
			schiebeEineScheibe(pVon, pNach);
			schiebe(pAnz-1, pHilf, pNach, pVon);
		}
	}
	public static void main(String[] args) {
		int value = anzScheiben;
		System.out.println("Die Türme von Hanoi");
		if (args.length > 0) {
			try {
				value = Integer.parseInt(args[0]);
			} catch (Exception e) {
				value = anzScheiben;
			}
		}
		System.out.println("Die Berechnung erfolgt mit " + value + " Scheiben");
		init();
		showPlaces();
		schiebe(value, platzA, platzB, platzC);
	}
}
```


----------



## Landei (3. Mrz 2011)

Ein geradezu unglaublicher Aufwand, wenn man das mit Haskell vergleicht (rekursive Lösung):


```
hanoi n = solve n 1 2 3

solve 0 _ _ _ = []
solve n from help to = (solve (n-1) from to help) ++ [(from,to)] ++ (solve (n-1) help from to)
```

([c]hanoi 3[/c] ergibt z.B. die Zugfolge [c][(1,3),(1,2),(3,2),(1,3),(2,1),(2,3),(1,3)][/c], wobei (x,y) "von Stab x nach Stab y" bedeutet.


----------



## Marco13 (3. Mrz 2011)

Nun, du weißt, dass man es auch in Java kürzer schreiben kann, vergleiche 99 Bottles of Beer | Language Java (und unten die "Alternative Versions") - und 99 Bottles of Beer | Language Scala ist sogar noch länger als die kürzeste Java-Version :bae:


----------



## SlaterB (3. Mrz 2011)

wenn man auf Rekursion setzt, kann man in diesem Fall doch in Java bleiben,
wieso mit anderen Sprachen so drastisch vergleichen?

```
public class Test {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(solve(n, 1, 2, 3));
    }

    static String solve(int n, int from, int help, int to) {
        if (n == 0) return "";
        return solve(n - 1, from, to, help) + "(" + from + "," + to + ")" + solve(n - 1, help, from, to);
    }
}
```
bis auf Syntax-Blahblah dasselbe


----------



## Landei (3. Mrz 2011)

Nicht ganz. Versuche mal, in Java eine [c]List<Integer[]>[/c] oder so statt [c]String[/c] zurückzuliefern.


----------



## SlaterB (3. Mrz 2011)

dann erzeugt man bei 0 eine Liste und fügt ansonsten die Listen + neue Elemente zusammen, 
kein Problem oder beschwerst du dich über die Komplexität der Syntax dafür?
na wenn das das entscheidende ist..

Skriptsprachen wie SQL haben in ihren speziellen Kontext immer Vorteile, da muss man auch keine Variable für die Ergebnisliste anlegen..,
aber Word kann man darin nicht programmieren

Gegenfrage: kann man in den Haskel-Beispiel dort zwischen ArrayList- und LinkedList-Implementierung umschalten?


----------



## hanoiii (3. Mrz 2011)

SlaterB hat gesagt.:


> Gegenfrage: kann man in den Haskel-Beispiel dort zwischen ArrayList- und LinkedList-Implementierung umschalten?



Natürlich nicht, wie Listen intern umgesetzt werden, darauf hat man keinen Einfluss.



SlaterB hat gesagt.:


> dann erzeugt man bei 0 eine Liste und fügt ansonsten die Listen + neue Elemente zusammen,
> kein Problem oder beschwerst du dich über die Komplexität der Syntax dafür?
> na wenn das das entscheidende ist..



Die Liste muss lediglich als Argument "mitgeschleppt" werden und verlängert werden, vor/nach/während der rekursiven Aufrufe...


----------



## Landei (3. Mrz 2011)

SlaterB hat gesagt.:


> Gegenfrage: kann man in den Haskel-Beispiel dort zwischen ArrayList- und LinkedList-Implementierung umschalten?



Haskell hat unveränderliche Listen, die stack-artig arbeiten. Natürlich kann man stattdessen auch Queues, Vektoren und andere Strukturen verwenden (und auch darüber abstrahieren, z.B. über die Typklasse Foldable). Die Arbeit mit veränderlichen Datenstrukturen ist (etwas umständlicher) möglich, wird aber wenn möglich vermieden.

Man beachte, dass meine Lösung bereits über den Typ der "Stäbe" abstrahiert: Man könnte genausogut [c]hanoi n = solve n 'A' 'B' 'C'[/c] schreiben, ohne an solve etwas ändern zu müssen.


----------



## hanoiii (3. Mrz 2011)

Aber das ändert alles nichts daran, dass die iterative Variante - sie ist mit Haskell nicht möglich - viel(!) speicherschonender ist, als jedes Haskell-Programm, egal, wie sehr man die verkürzte Programmlänge aufgrund der Abstraktion schön reden mag.


----------



## Landei (3. Mrz 2011)

hanoiii hat gesagt.:


> Aber das ändert alles nichts daran, dass die iterative Variante - sie ist mit Haskell nicht möglich - viel(!) speicherschonender ist, als jedes Haskell-Programm, egal, wie sehr man die verkürzte Programmlänge aufgrund der Abstraktion schön reden mag.



Natürlich ist die iterative Variante in Haskell möglich:


```
hanoi n = map rep $ solve [1..n] [] [] where
          rep (x,y) | odd n = ([1,3,2] !! (x-1), [1,3,2] !! (y-1))
                    | otherwise = (x,y) 
             
solve from help to = head $ mapMaybe ready $ iterate step (from,help,to,[]) where
   step (1:xs,ys,zs,sol) = let (xs',zs',sol') = try xs zs 1 3 ((1,2):sol)
                           in (xs',1:ys,zs',sol')
   step (xs,1:ys,zs,sol) = let (xs',ys',sol') = try xs ys 1 2 ((2,3):sol)
                           in (xs',ys',1:zs,sol')
   step (xs,ys,1:zs,sol) = let (ys',zs',sol') = try ys zs 2 3 ((3,1):sol)
                           in (1:xs,ys',zs',sol')
   try [] [] _ _ sol = ([],[], sol)                            
   try (x:xs) [] a b sol = (xs,[x], (a,b):sol)                            
   try [] (y:ys) a b sol = ([y],ys, (b,a):sol)                            
   try (x:xs) (y:ys) a b sol | x < y = (xs,x:y:ys, (a,b):sol)
                             | y < x = (y:x:xs,ys, (b,a):sol)          
   ready ([],[],_,sol) = Just $ reverse sol
   ready ([],_,[],sol) = Just $ reverse sol
   ready _ = Nothing
```

iterate funktioniert hier ähnlich wie eine while-Schleife oder ein Iterator in Java, und wird mapMaybe "durchgegangen", bis die ready-Funktion ein Abbruchkriterium liefert. Sicher nicht die eleganteste Lösung (dafür bin ich in Haskell noch viel zu unerfahren), aber trotzdem einigermaßen verständlich und schon recht kompakt.


----------



## hanoiii (3. Mrz 2011)

Landei hat gesagt.:


> iterate funktioniert hier ähnlich wie eine while-Schleife oder ein Iterator in Java



wie soll das möglich sein, wenn es keine Kontrollstrukturen dort gibt... - nur mit Rekursion


----------



## Landei (3. Mrz 2011)

Ich habe den "iterativen" Algorithmus von Buneman und Levy ( Türme von Hanoi ? Wikipedia ) umgesetzt, und dabei keine rekursiven Aufrufe benutzt. Natürlich kann iterate ebenfalls rekursiv umgesetzt sein (und ist es wahrscheinlich auch), aber prinzipiell könnte es auch iterativ programmiert sein - genau wie man in Java eine Methode schreiben könnte, die [c]while[/c] "simuliert", aber intern rekursiv arbeitet. Aber dieses Detail ist für die Arbeitsweise des Algorithmus völlig irrelevant - genauso, wie es beim Algorithmus zur Berechnung von Binomialkoeffizienten keinen Unterschied macht, ob ich die dazu benötigte Fakultät nun rekursiv oder iterativ berechne - man sieht es der Zahl am Ende nicht mehr an.

Ich denke aber, dass man auch in Haskell eine "wirklich" iterative Kontrollstruktur (mit lokal veränderlicher Zählvariable) schreiben kann, z.B. unter Verwendung der State-Monade. Es wäre vermutlich ziemlich unhandlich und kompliziert, aber prinzipiell spricht nichts dagegen.

[Edit]

Hier ist eine Implementierung einer "while-Schleife" als Monaden-Transformer: Control.Monad.LoopWhile

Und hier als Funktion über einer Monade (die aber intern rekursiv realisiert ist): Haskell While Loop  It Seemed Like a Good Idea at the Time


----------

