Hanoi mittels Erzeuger - Producer-Prinzip

bvdcomp

Aktives Mitglied
Hallo zusammen

Das rekursive Programm Türme von Hanoi ist hier gegeben.

Java:
public class Hanoi {

	static void hanoi(int anzahlScheiben, String start, String ziel, String ablage)
	{
	   if (anzahlScheiben <= 0) return;
	   hanoi(anzahlScheiben - 1, start, ablage, ziel);
	   zug(anzahlScheiben, start, ziel);
	   hanoi(anzahlScheiben - 1, ablage, ziel, start);
	}


	static void zug(int scheibe, String start, String ziel)
	{
	   System.out.println("Scheibe " + scheibe + " von " + start + " nach " + ziel);
	} 
	    public static void main (String[] args)
    {
	    	 hanoi(4, "A", "B", "C");
    }

}

Nun, der Code ist verständlich. Jetzt soll dieser aber mittels Producer-Consumer-Prinzip umgeformt werden.

Das Prinzip verstehe ich schon, aber wie kann ich es auf Hanoi umsetzen?

Java:
public class ProducerConsumer {
	public static void main(String[] args)
	{
		Buffer b = new Buffer();
		Consumer c = new Consumer(b);
		Producer p = new Producer(b,1);
		c.run();
		p.run();
	}
}
Java:
public class Producer extends Thread {
	private Buffer buffer;
	private int start;
	
	public Producer(Buffer b, int s)
	{
		buffer = b;
		start = s;
	}
	
	public void run()
	{
		for(int i = start; i < start+100; i++)
		{
			buffer.put(i);
		}
	}
}
Java:
public class Consumer {

	private Buffer buffer;
	
	public Consumer(Buffer b)
	{
		buffer = b;
	}
	
	public void run()
	{
		for(int i = 0; i < 100; i++)
		{
			int x = buffer.get();
			System.out.println("gelesen: "+ x);
		}
	}
}
Java:
public class Buffer {
	private boolean available = false;
	private int data;
	
	public synchronized void put(int x)
	{
		while(available)
		{
			try
			{
				wait();
			}
			catch(InterruptedException e)
			{
			}
		}
		data = x;
		available = true;
		notify();
	}
	
	public synchronized int get()
	{
		while(!available)
		{
			try
			{
				wait();
			}
			catch(InterruptedException e)
			{
			}
		}
		available = false;
		notify();
		return data;
	}
	
}

Kann ich hier ablage als Buffer verstehen?
Was ist hier Producer und was ist hier consumer?

Kann mir da jemand weiterhelfen?

Es währe gut, wenn ich die Aufgabe zusammen mit der Community lösen kann, ich "verlange" keine fertige Lösung, denn die hilft mir nicht beim verstehen des Prinzips.
 
S

SlaterB

Gast
bezeichnend:
Towers of Hanoi using Producer/Consumer Pattern

von java-forums.org
hier ist java-forum.org ..

die Aufgabe steht Producer/Consumer komplett entgegen, da gibt es nichts sinnvolles an Java zu lösen,
durch die Rekursion kann man nicht einmal allzu gut simpel die Arbeitschritte aufteilen..,
bevor ich weiter irgendwas komisches schreibe warte ich jetzt ab ob mein Posting neue Leserschaft generiert ;)



übrigens ruft man an Threads die start()-Methode auf, nicht run()!
 

Marco13

Top Contributor
Gelesen hatte ich das schon, aber ... mir war nicht klar, was dort Produced und was Consumed werden sollte. Züge? Scheiben? String-Consolenausgaben? :bahnhof:
 
J

JohannisderKaeufer

Gast
Ich hab mir mal die Aufgabe angeschaut.

Ich stell mir vor, dass Befehle / HanoiMessage produziert und konsumiert werden.

Ein Befehl hat den Inhalt:
from, to, over: Von wo über welche Zwischenstation wohin transportiert werden soll
mt, was Transportiert werden soll (einzelne Scheibe, oder Turm)
nr, Die Scheibennummer, bzw. ein nr Hoher Turm
game, um welches Spielbrett es sich handelt
nested, darin können weitere Befehle enthalten sein, die erst ausgeführt werden sollen, wenn dieser Befehl(this) abgearbeitet ist.

Java:
package hanoi;

import java.util.List;

public class HanoiMessage {
enum MT{
	TOWER,DISC
}
	String from;
	String to;
	String over;
	int nr;
	MT mt;
	String game;
	List<HanoiMessage> nested;
	public HanoiMessage(String from, String to, String over, int nr, MT mt,
			String game, List<HanoiMessage> nested) {
		super();
		this.from = from;
		this.to = to;
		this.over = over;
		this.nr = nr;
		this.mt = mt;
		this.game = game;
		this.nested = nested;
	}
}

Einen Buffer, HanoiBuffer, der die Befehle zwischenspeichert.

Java:
package hanoi;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import hanoi.HanoiMessage.MT;


public class HanoiBuffer {

	List<HanoiMessage> messages = new ArrayList<HanoiMessage>();
	
	public boolean hasNext() {
		return !messages.isEmpty();
	}

	public HanoiMessage next() {
		HanoiMessage first = messages.get(0);
		messages.remove(0);
		return first;
	}
 
	public void add(HanoiMessage hanoiMessage) {
		messages.add(hanoiMessage);
	}

Einen Consumer, der sich die Messages Holt und abarbeitet.
Handelt es sich um einen ein Scheiben Befehl. Erfolgt eine Ausgabe.
Hat dieser weitere Befehle (nested), dann wird ein neuer Befehl produziert, der aus dem ersten nested Befehl besteht, und die restlichen (also den tail) als eigene Befehlssequenz mitbekommt.

Soll ein Turm Bewegt werden.
So wird ein Befehl erstellt der den nächstkleineren Turm auf die zwischenstation bewegt.
Dieser Befehl bekommt zwei weitere Befehle mit. 1. die letzte Scheibe auf das Ziel zu setzen, 2. den kleineren Turm von der zwischenstation auf das Ziel zu setzen. Sowie weitere Befehle, die der Ursprüngliche Befehl als nested mitbringt.

Java:
package hanoi;

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

import hanoi.HanoiMessage.MT;

public class HanoiConsumer implements Runnable {

	HanoiBuffer buffer;
	String consumer;

	public HanoiConsumer(HanoiBuffer buffer, String consumer) {
		this.buffer = buffer;
		this.consumer = consumer;
	}

	@Override
	public void run() {
		while (true) {
			try {
				Thread.sleep(500);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			synchronized (buffer) {
				if (buffer.hasNext()) {
					HanoiMessage m = buffer.next();
					consume(m);
				}
			}
		}
	}

	void consume(HanoiMessage m) {
		if (m.mt == MT.DISC) {
			System.out
					.println("Game " + m.game + " " + consumer + " moves Disc "
							+ m.nr + " from " + m.from + " to " + m.to);
			if (!m.nested.isEmpty()) {
				HanoiMessage first = m.nested.get(0);
				m.nested.remove(0);
				first.nested.addAll(m.nested);
				produceMessage(first.mt, first.nr, first.from, first.to,
						first.over, first.game, first.nested);

			}
		}
		if (m.mt == MT.TOWER) {
			if (m.nr == 1) {
				produceMessage(HanoiMessage.MT.DISC, 1, m.from, m.to, m.over,
						m.game, m.nested);
			} else {
				List<HanoiMessage> nested = new ArrayList<HanoiMessage>();
				nested.add(new HanoiMessage(m.from, m.to, m.over, m.nr,
						HanoiMessage.MT.DISC, m.game,
						new ArrayList<HanoiMessage>()));
				nested.add(new HanoiMessage(m.over, m.to, m.from, m.nr - 1,
						HanoiMessage.MT.TOWER, m.game, m.nested));

				produceMessage(HanoiMessage.MT.TOWER, m.nr - 1, m.from, m.over,
						m.to, m.game, nested);
			}
		}
	}

	private void produceMessage(MT mt, int nr, String from, String to,
			String over, String game, List<HanoiMessage> nested) {
		buffer.add(new HanoiMessage(from, to, over, nr, mt, game, nested));
	}
}

Da es sich um einen rekursiven Algorithmus handelt, denke ich das es völlig in Ordnung ist, wenn der Consumer auch Producer von Teilaufgaben ist.

Einen Expliziten Producer habe weggelassen, da dessen Aufgaben auch im Main-Thread erledigt werden können.

Hier wird ein buffer erstellt sowie 4 Consumer (rechte/linke - hand/fuss)
Es werden nacheinander mehrere Spiele erstellt 1 .. 11.

Java:
package hanoi;

import java.util.ArrayList;

import hanoi.HanoiMessage.MT;

public class HanoiMain {
public static void main(String[] args) throws InterruptedException {
	HanoiBuffer buffer = new HanoiBuffer();
	
	new Thread(new HanoiConsumer(buffer, "right hand")).start();
	new Thread(new HanoiConsumer(buffer, "left hand")).start();
	new Thread(new HanoiConsumer(buffer, "right foot")).start();
	new Thread(new HanoiConsumer(buffer, "left foot")).start();
	
	buffer.add(new HanoiMessage("A","B","C",1,MT.TOWER, "1", new ArrayList<HanoiMessage>()));
	Thread.sleep(1000);
	buffer.add(new HanoiMessage("A","B","C",5,MT.TOWER, "2", new ArrayList<HanoiMessage>()));
	Thread.sleep(2000);
	buffer.add(new HanoiMessage("A","B","C",2,MT.TOWER, "3", new ArrayList<HanoiMessage>()));
	Thread.sleep(3000);
	buffer.add(new HanoiMessage("A","B","C",1,MT.TOWER, "4", new ArrayList<HanoiMessage>()));
	Thread.sleep(4000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "5", new ArrayList<HanoiMessage>()));
	Thread.sleep(5000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "6", new ArrayList<HanoiMessage>()));
	Thread.sleep(6000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "7", new ArrayList<HanoiMessage>()));
	Thread.sleep(7000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "8", new ArrayList<HanoiMessage>()));
	Thread.sleep(8000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "9", new ArrayList<HanoiMessage>()));
	Thread.sleep(9000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "10", new ArrayList<HanoiMessage>()));
	Thread.sleep(10000);
	buffer.add(new HanoiMessage("A","B","C",4,MT.TOWER, "11", new ArrayList<HanoiMessage>()));
  }
}

Was zu folgender Ausgabe führt:

Code:
Game 1 left hand moves Disc 1 from A to B
Game 2 right foot moves Disc 1 from A to B
Game 2 right hand moves Disc 2 from A to C
Game 2 left foot moves Disc 1 from B to C
Game 2 right foot moves Disc 3 from A to B
Game 2 left foot moves Disc 1 from C to A
Game 2 right foot moves Disc 2 from C to B
Game 2 left hand moves Disc 1 from A to B
Game 2 left foot moves Disc 4 from A to C
Game 3 right foot moves Disc 1 from A to C
Game 3 left hand moves Disc 2 from A to B
Game 2 left foot moves Disc 1 from B to C
Game 2 right hand moves Disc 2 from B to A
Game 3 left hand moves Disc 1 from C to B
Game 2 right foot moves Disc 1 from C to A
Game 2 right hand moves Disc 3 from B to C
Game 2 right foot moves Disc 1 from A to B
Game 2 right hand moves Disc 2 from A to C
Game 2 left foot moves Disc 1 from B to C
Game 2 right foot moves Disc 5 from A to B
Game 4 right foot moves Disc 1 from A to B
Game 2 left foot moves Disc 1 from C to A
Game 2 right foot moves Disc 2 from C to B
Game 2 left hand moves Disc 1 from A to B
Game 2 left foot moves Disc 3 from C to A
Game 2 left hand moves Disc 1 from B to C
Game 2 left foot moves Disc 2 from B to A
Game 2 right hand moves Disc 1 from C to A
Game 2 left hand moves Disc 4 from C to B
Game 2 left hand moves Disc 1 from A to B
Game 2 left foot moves Disc 2 from A to C
Game 2 right hand moves Disc 1 from B to C
Game 2 left hand moves Disc 3 from A to B
Game 2 right hand moves Disc 1 from C to A
Game 2 left hand moves Disc 2 from C to B
Game 2 right foot moves Disc 1 from A to B
Game 5 right hand moves Disc 1 from A to C
Game 5 left hand moves Disc 2 from A to B
Game 5 right foot moves Disc 1 from C to B
Game 5 right hand moves Disc 3 from A to C
Game 5 right foot moves Disc 1 from B to A
Game 5 right hand moves Disc 2 from B to C
Game 5 left foot moves Disc 1 from A to C
Game 5 right foot moves Disc 4 from A to B
Game 5 right foot moves Disc 1 from C to B
Game 5 right hand moves Disc 2 from C to A
Game 5 left foot moves Disc 1 from B to A
Game 5 right foot moves Disc 3 from C to B
Game 5 left foot moves Disc 1 from A to C
Game 5 right foot moves Disc 2 from A to B
Game 5 left hand moves Disc 1 from C to B
Game 6 right hand moves Disc 1 from A to C
Game 6 left hand moves Disc 2 from A to B
Game 6 right foot moves Disc 1 from C to B
Game 6 right hand moves Disc 3 from A to C
Game 6 right foot moves Disc 1 from B to A
Game 6 right hand moves Disc 2 from B to C
Game 6 left foot moves Disc 1 from A to C
Game 6 right foot moves Disc 4 from A to B
Game 6 right foot moves Disc 1 from C to B
Game 6 right hand moves Disc 2 from C to A
Game 6 left foot moves Disc 1 from B to A
Game 6 right foot moves Disc 3 from C to B
Game 6 left foot moves Disc 1 from A to C
Game 6 right foot moves Disc 2 from A to B
Game 6 left hand moves Disc 1 from C to B
Game 7 right hand moves Disc 1 from A to C
Game 7 left hand moves Disc 2 from A to B
Game 7 right foot moves Disc 1 from C to B
Game 7 right hand moves Disc 3 from A to C
Game 7 right foot moves Disc 1 from B to A
Game 7 right hand moves Disc 2 from B to C
Game 7 left foot moves Disc 1 from A to C
Game 7 right foot moves Disc 4 from A to B
Game 7 right foot moves Disc 1 from C to B
Game 7 right hand moves Disc 2 from C to A
Game 7 left foot moves Disc 1 from B to A
Game 7 right foot moves Disc 3 from C to B
Game 7 left foot moves Disc 1 from A to C
Game 7 right foot moves Disc 2 from A to B
Game 7 right hand moves Disc 1 from C to B
Game 8 left foot moves Disc 1 from A to C
Game 8 right hand moves Disc 2 from A to B
Game 8 right foot moves Disc 1 from C to B
Game 8 left foot moves Disc 3 from A to C
Game 8 right foot moves Disc 1 from B to A
Game 8 left foot moves Disc 2 from B to C
Game 8 left hand moves Disc 1 from A to C
Game 8 right foot moves Disc 4 from A to B
Game 8 right foot moves Disc 1 from C to B
Game 8 right hand moves Disc 2 from C to A
Game 8 left foot moves Disc 1 from B to A
Game 8 right foot moves Disc 3 from C to B
Game 8 left foot moves Disc 1 from A to C
Game 8 right foot moves Disc 2 from A to B
Game 8 left hand moves Disc 1 from C to B
Game 9 right hand moves Disc 1 from A to C
Game 9 left foot moves Disc 2 from A to B
Game 9 right foot moves Disc 1 from C to B
Game 9 right hand moves Disc 3 from A to C
Game 9 right foot moves Disc 1 from B to A
Game 9 right hand moves Disc 2 from B to C
Game 9 left hand moves Disc 1 from A to C
Game 9 right foot moves Disc 4 from A to B
Game 9 right foot moves Disc 1 from C to B
Game 9 right hand moves Disc 2 from C to A
Game 9 left hand moves Disc 1 from B to A
Game 9 right foot moves Disc 3 from C to B
Game 9 left hand moves Disc 1 from A to C
Game 9 right foot moves Disc 2 from A to B
Game 9 left foot moves Disc 1 from C to B
Game 10 left hand moves Disc 1 from A to C
Game 10 right hand moves Disc 2 from A to B
Game 10 right foot moves Disc 1 from C to B
Game 10 left hand moves Disc 3 from A to C
Game 10 right foot moves Disc 1 from B to A
Game 10 left hand moves Disc 2 from B to C
Game 10 left foot moves Disc 1 from A to C
Game 10 right foot moves Disc 4 from A to B
Game 10 right foot moves Disc 1 from C to B
Game 10 left hand moves Disc 2 from C to A
Game 10 left foot moves Disc 1 from B to A
Game 10 right foot moves Disc 3 from C to B
Game 10 left foot moves Disc 1 from A to C
Game 10 right foot moves Disc 2 from A to B
Game 10 right hand moves Disc 1 from C to B
Game 11 right hand moves Disc 1 from A to C
Game 11 left foot moves Disc 2 from A to B
Game 11 right foot moves Disc 1 from C to B
Game 11 right hand moves Disc 3 from A to C
Game 11 right foot moves Disc 1 from B to A
Game 11 right hand moves Disc 2 from B to C
Game 11 left hand moves Disc 1 from A to C
Game 11 right foot moves Disc 4 from A to B
Game 11 right foot moves Disc 1 from C to B
Game 11 right hand moves Disc 2 from C to A
Game 11 left hand moves Disc 1 from B to A
Game 11 right foot moves Disc 3 from C to B
Game 11 left hand moves Disc 1 from A to C
Game 11 right foot moves Disc 2 from A to B
Game 11 left foot moves Disc 1 from C to B

Hier sieht man, dass verschiedene Consumer, "parallel" auf verschiedenen Brettern die Türme von Hanoi spielen.

Eine schwierigkeit hierbei ist, dafür zu sorgen, dass Sub-Befehle, die aus einem Befehl entstehen, in der richtigen Reihenfolge abgearbeitet werden. Indem ein Befehl eine Sequenz von Befehlen mit sich führt, kann man dem entgegenwirken und Behält so die Kontrolle über die Reihenfolge.
 

bvdcomp

Aktives Mitglied
Ich habe den Code analysiert und finde es sehr verständlich.

Ich habe fast keine Ahnung gehabt wo ich anfangen hätte sollen.

Danke vielmals.

Allerdigs ist es ja noch nicht ganz fertig, denn beim er stappelt bis "B" und macht nicht weiter, eigentlich sollte er alles bis auf "C" rüber bringen.

Wenn ich folgendes laufen lasse:
Java:
public class MainHanoi {
public static void main(String[] args) throws InterruptedException {
    HanoiBuffer buffer = new HanoiBuffer();
    
    new Thread(new HanoiConsumer(buffer, "right hand")).start();
    new Thread(new HanoiConsumer(buffer, "left hand")).start();
    new Thread(new HanoiConsumer(buffer, "right foot")).start();
    new Thread(new HanoiConsumer(buffer, "left foot")).start();
    
    buffer.add(new HanoiMessage("A","B","C",3,MT.TOWER, "1", new ArrayList<HanoiMessage>()));

  }
}

Erhalte ich dann:
Zug 1 right foot bewegt Disc 1 von A nach B
Zug 1 left hand bewegt Disc 2 von A nach C
Zug 1 right hand bewegt Disc 1 von B nach C
Zug 1 right foot bewegt Disc 3 von A nach B
Zug 1 right hand bewegt Disc 1 von C nach A
Zug 1 right foot bewegt Disc 2 von C nach B
Zug 1 left foot bewegt Disc 1 von A nach B


Oder sehe ich das falsch?
 
Zuletzt bearbeitet:

Neue Themen


Oben