Hi,
Habe folgende Aufgabe, bei der ich nicht weiterkomme.
Das kleingeschriebene sind die genauen Anweisungen, sind aber zum Verständnis nicht unbedingt notwendig.
Aus einer Gruppe von n Kindern soll ein Gewinner ermittelt werden, indem sie sich im Kreis aufstellen und wiederholt mittels eines Reims von m Takten einen Ausscheider abzählen. Jedes ausgezählte Kind verlässt den Kreis, der sich daraufhin wieder schließt. Im neu geschlossenen Kreis beginnt das Abzählen an der Position nach dem ausgeschlossenen Kind.
Gewinner ist das Kind, das als letztes übrig ist.
Beispiel:
Die ersten 4 Auszählschritte für n = 9, m = 5. Die komplette Folge lautet: 5, 1, 7, 4, 3, 6, 9, 2, 8. Der Gewinner steht an
Stelle 8 des ursprünglichen Kreises.
Ziel dieser Aufgabe ist es für gegebenes n und m diejenige Position im ursprünglichen Kreis der Größe n zu bestimmen, an
der das letzte übrigbleibende Kind steht.
Um das Abzählen im Kreis möglichst einfach zu gestalten, benutzen wir eine einfach verkettete zirkuläre Liste. Dies
bedeutet, dass der letzte Knoten nicht auf null, sondern zurück auf den ersten Knoten der Liste zeigt.
Zur Navigation in der Liste benutzen wir einen Zeiger (pointer), der die aktuelle Position in der Liste anzeigt.
Die Liste erlaubt (unter anderem) diese Operationen, die folgendermaßen umzusetzen sind:
· Einfügen: Ein neu einzufügender Knoten wird als Nachfolger des Knotens eingefügt, auf den pointer zeigt.
Nach dem Einfügen des neuen Knotens zeigt pointer auf diesen.
· Abfragen: Liefert das Inhaltselement des aktuellen Knotens. Der Zeiger pointer bleibt unverändert.
· Löschen: Gelöscht wird der Knoten auf den pointer zeigt. Nach dem Löschen eines Elements bewegt sich
pointer auf den Vorgänger des gelöschten Knotens.
· Zeigerbewegung: Der Zeiger pointer wird um eine angegebene Anzahl von Knoten weiterbewegt.
Definieren Sie für den ADT „Zirkuläre Liste“ zunächst ein Java-Interface datenstrukturen. IZirkulaereListe mit folgenden Methoden:
Methode: void addElement(Object element)
Fügt das übergebene Objekt in die Liste an der aktuellen Position ein.
Methode: Object getElement()
Liefert das Inhaltselement des Knotens zurück, auf den pointer verweist.
Methode: Object removeNode()
Entfernt den aktuellen Knoten aus der Liste, und gibt dessen Inhaltselement zurück. Bei einer leeren Liste wird null zurückgeliefert. Methode: void
movePointer(int n)
Bewegt den Zeiger auf das aktuelle Element um n Positionen weiter. Für n < 1 bleibt der Point unverändert.
Methode: int getSize()
Gibt die Anzahl der Elemente in der Liste zurück.
Methode: boolean isEmpty()
Gibt zurück, ob die Liste leer ist.
Erstellen Sie nun eine Klasse datenstrukturen.ZirkulaereListe, die obige Schnittstelle implementiert und folgende Attribute und weiteren Methoden aufweist:
Attribut head: Typ Node
Zeigt auf den ersten Knoten der zirkulären Liste.
Attribut pointer: Typ Node
Zeigt auf den aktuellen Knoten der zirkulären Liste.
Hilfsmethode: Node getPreviousNode(Node node)
Sucht den Vorgänger zu übergebenem Knoten node und gibt diesen zurück.
Überschriebene Methoden: String toString()
Erzeugt eine textuelle Repräsentation der Knoten der Liste, analog zur toString()-Methode der verketteten Liste aus dem Skript. Bei head beginnend wird die Liste durchlaufen, bis jeder Knoten einmal besucht wurde.
Hinweise:
1. Sichtbarkeiten: Attribute und Hilfsmethoden sollen private, Methoden public sein.
2. Benutzen Sie die in der Vorlesung definierte Hilfsklasse Node (Skript 09-38). Kopieren Sie ihn in das gleiche Paket wie die zirkuläre Liste.
3. Eine alternative Behandlung des Head-Knotens (anders als in der verketteten Liste des Skripts) könnte sich einfacher gestalten. Dieser kann in der zirkulären Liste bereits das erste Inhaltselement tragen (sofern vorhanden). Die leere zirkuläre Liste bestünde dann aus 0 Knoten: leere Liste nach Einfügen von Siggi nach Einfügen von Harry Sie können jedoch auch das aus der Vorlesung bekannte Verfahren anwenden. Implementieren Sie abschließend eine Klasse spiele.KinderReim mit folgender Methode: public static int abzaehlen(int kinder, int takte) Gibt die Position des Gewinners bei kinder Kindern und einem Reim der Länge takte zurück. Benutzen Sie obige zirkuläre Liste zur Bestimmung der Gewinnerposition. Liefern Sie für ungültige Werte für kinder oder takte den Rückgabewert -1 zurück.
Das sind meine bisherigen Klassen:
meine Fragen:
1. Was macht dieses Interface? Stehen da nur die Methoden drin oder muss da noch was rein? Ruf ich diese Methoden dann über das interface auf?
2. Wie setze ich den pointer immer an die richtige Stelle? Bei meinem Code ist der ja am Anfang nicht gesetzt, und müsste einen Nullpointer-Fehler erzeugen.
3. Wie kann ich mir Java am Besten selber beibringen? Gibts da irgendwelche empehlenswerte Video2Brain-Folgen oder irgendwelche Bücher?
