Jesephus-Problem

Dr. Trommelfell · Gast

und zwar hab ich Probleme bei einer Informatikaufgabe von der Uni. Vielleicht hat ja von euch jemand Lust und Zeit mir da ein wenig zu helfen.

Und zwar geht es um die 2. Aufgabe bei der 6. Übung die ihr euch hier runterladen könnt:
http://www.allgemeineinformatik.de/SS2005/uebungen.php

Abgabeschluss ist schon Freitag abend um 24h.

Vielen Dank
Dr. Trommelfell

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Dann beschreib doch mal, wo genau jetzt dein Problem liegt...

Welche Teile hast du schon, welche fehlen noch? Verstehst du die Aufgabe prinzipiell oder weißt du überhaupt nicht, was du machen musst? Mit den Angaben, die du hier gemacht hast, könnte man dir zwar die Aufgabe lösen, aber das ist ja auch nicht Sinn der Sache. Du sollst das ja am Ende selber können...

Dr. Trommelfell · Gast

Das Josephus Prob. ist eigentlich nicht so dass Problem. Es geht eher um die Methode remove(). Die Methode insert laäuft, und die Methode Remove läuft für alle Zahlen !=1. Ich komm nur nicht drauf, wie mandas mit der 1 macht.

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Wie du ja sicher weißt löscht man in Java n Element aus ner Liste, indem man einfach alle Zeiger auf dieses Element entfernt und dann den Garbage Collector den Rest erledigen lässt.

Wenn nur noch ein Element in dieser Liste ist steht aber die einzige Referenz darauf im Attribut start. Du musst also nur noch start = null setzen und fertig.

Dr. Trommelfell · Gast

Ja, das ist alles klar. aber ich schaffe es nicht, wenn ich z.Bsp. 5 Personen eingefügt hab, die erste zu entfernen.
Mein ansatz wäre:

start=start.next;
Person x = start;
while(x.next!=start){
x=x.next}
x.next=start;

Da ist x das letzte Element, dann wäre x.next, ja das neue start, dass ja start.next. ist.
hab schon alle möglichen kombinationen ausprobiert. aber es läuft net

Crotaphytus · Anmeldungsdatum: 08.05.2005 Beiträge: 213

Wahrscheinlich schon zu spät, aber vielleicht hilfts dir ja auch nachträglich was... Augenzwinkern

Ich seh zumindest mal, was das Problem ist... Nämlich, dass bei dieser zirkulären Liste ja ein Verweis vom letzten auf das erste Element steht, der beim Löschen des ersten Elements ja noch angepasst werden muss.

Erst mal sollte man schauen, was dein Ansatz macht:

Die erste Zeile lässt das Attribut start auf das zweite (und nicht mehr auf das erste) Element der Liste zeigen.
Dann kopierst du die Referenz, die in start steht, in die Variable x, sprich du hast auch in x nen Verweis auf das zweite Element stehen.
Dann startest du eine Schleife, die solange laufen soll bis der Nachfolger von x auf start verweist, sprich x wäre dann das erste Element der Liste (und damit, das, das du löschen willst).
Dann setzt du dessen Nachfolger auf start. Der war es aber vorher schon, also bringt dir das ganze nicht sonderlich viel, gelöscht wird da auf jeden Fall nix...

Das Problem besteht in der Änderung von start gleich am Anfang. Diese Referenz brauchst du, um das letzte Element der Liste zu finden, die darf nicht gleich zu Beginn gelöscht werden. Das Löschen für das erste Element würde also richtig so aussehen:

// Letztes Element suchen
Person lastElem = start;
do {
lastElem = lastElem.next;
} while(lastElem.next != start);
// Anpassen der Referenz auf den Nachfolger des letzten Elements, dieses muss das zweite Element sein
lastElem.next = start.next;
// Anpassen des Attributs start
start = start.next;

Zuerst solltest du allerdings überprüfen, ob die Liste mehr als ein Element hat, ansonsten wird gelöscht, indem start = null gesetzt wird. Dies geht aber ganz einfach über die Zeile

if(start == start.next) start = null;