Türme von Hanoi - Iterator

[bvdcomp]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

doppelpost -.-

 

[Shulyn]

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]

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]

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]

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]

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

 

[bvdcomp]

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]

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

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

 

[Aldimann]

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]

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]

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]

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]

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]

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]

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]

	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]

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]

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]

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]

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]

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]

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]

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.

ROFL! Das mal n guter Hinweis

So genau hab ich den Text gar nicht gelesen

 

[Andi_CH]

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]

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:

solange (Stab A oder B enthalten Scheiben) {
    Verschiebe S1 im Uhrzeigersinn um einen Platz;
    falls (eine von S1 verschiedene Scheibe ist verschiebbar)
        Verschiebe eine von S1 verschiedene Scheibe;
}

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

 

[Marco13]

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.)

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]

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]

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]

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]

... 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]

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]

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]

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]

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

 

[SlaterB]

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]

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.

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]

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]

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]

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]

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