Zyklensuche

[Clawg]

Wie kann man denn bitte einen Zyklus in einer einfach-verketteten Liste finden, wenn man weder dynamisch Speicher alloziieren darf, noch die Länge der Liste bekannt ist, noch die Liste verändern darf?
Beschäftigt mich seit gestern und ich komme nicht drauf wie. Ich vermute, dass es nicht möglich ist. Markieren/Löschen usw. geht ja nicht und da man die Länge nicht kennt, hat man kein Abbruchkriterium um die Elemente einzeln zu vergleichen...
Man kann ja nicht mal die Länge mittels binärer Suche abschätzen, da man dazu ja log n Speicherplatz benötigen würde...

 

[ROOT]

Naja die Länge kannst du doch abzaehlen per durchlaufen?
Sobald kein Pointer aufs naechste Element mehr da ist, ist die Liste halt zuende.

Wie kommst du denn auf das Problem?

 

[Clawg]

Naja die Länge kannst du doch abzaehlen per durchlaufen?
Sobald kein Pointer aufs naechste Element mehr da ist, ist die Liste halt zuende.

Und wie speicherst du die abgezählte Länge? Auch ein 64bit Integer ist irgendwann zu klein und du musst Speicher dynamisch, d.h. in Abhängigkeit von der Länge der Liste, alloziieren.

Wie kommst du denn auf das Problem?

Theoretische Prüfungsaufgabe.

 

[killerchicken_inaktiv]

Ne, kriegste nicht hin wenn du keine Maximalbeschränkungen gegeben hast, ausser du machst abstruse Annahmen (zB dass die Liste nicht mehr Elemente haben kann, als es Speicheradressen gibt, du aber nen Int haben darfst, der groß genug ist alle Speicheradressen zu zählen zB)

 

[Clawg]

Gut, dann hatte ich es richtig beantwortet ("geht nicht"), vielen Dank

 

[killerchicken_inaktiv]

hrm damn, theoretisch sollte es nicht gehen, aber jetzt fällt mir was ein...

Du hast: 1 Pointer

Den setzt du auf Element 1, läufst die Liste durch bis ans Ende, wenn du Pointer 1 nochmal wiederfindest => Kreis. Wenn nicht läufst du vom Pointer ein Element weiter, setzt den Pointer neu, und startest von neuem. Sobald du durch bist weisst du, dass kein Kreis drin ist.

Und jetzt erklär mir einer, wieso der Ansatz nicht funktioniert, bitte.

 

[Clawg]

Was ist denn bitte das Ende einer zyklenbehafteten Liste unbekannter Länge?
Man kann sich ein künstliches Abbruchkriterium schaffen und einfach nach m Schritten abbrechen und dann nochmal durchlaufen und dann nach 2*m Schritten abbrechen usw. bis man entweder das Ende der Liste oder einen Zyklus findet. Dazu muss man aber diesen Zähler speichern...


Dein Algorithmus läuft hier einfach unendlich lange:
o_1 -> o_2 -> o_3 -> ... 2^64 Einträge ... -> o_(n-1) <-> o_(n)


Dagegen bei dieser Liste:
o_1 -> o_2 -> o_3 -> ... 2^64 Einträge ... -> o_(n-1) -> o_(n) -> o_1 -> ...
wird z.B. bei 2^64 als Abbruchkriterium kein Zyklus gefunden und es läuft unendlich...

 

[TheScorpion]

Ich habe zwar nicht wirklich lange darüber nachgedacht, aber:
1. Wenn man keine Variablen anlegen kann/darf, eignet sich eine rekursive Aufrufstruktur, da lässt Du die "Speicherung" den Aufrufstack machen. Und der ist in theo Inf unendlich groß
2. Theoretische Informatik läuft oft auf Rekursionen hinaus
3. Wenn ich mich recht erinnere, habe ich was Ähnliches mal in PL/SQL programmiert (Test auf Zyklen in Verweisen)
4. Oder habe ich aus Zeitmangel möglicherweise das Problem nicht richtig verstanden?

 

[Clawg]

Aufrufstack ist nicht unendlich groß, sondern nur konstant groß Das ist dynamisch alloziierter Speicher, darfste nicht verwenden, das wäre cheating

 

[killerchicken_inaktiv]

Daran hab ich auch gedacht von wegen Abbruchbedingung, aber mein Algorithmus bricht ab. Entweder beim Kreis, oder am Ende der Liste. Einzige Vorraussetzung: Die Liste darf nicht unendlich lang sein. Das dürfte man aber als gegeben betrachten können.

 

[Clawg]

Daran hab ich auch gedacht von wegen Abbruchbedingung, aber mein Algorithmus bricht ab. Entweder beim Kreis, oder am Ende der Liste. Einzige Vorraussetzung: Die Liste darf nicht unendlich lang sein. Das dürfte man aber als gegeben betrachten können.

Aber der Kreis kann doch irgendwo auch in der Mitte der Liste sein, der muss ja nicht ans erste Element zurückführen. Wo bricht dein Algorithmus bei einer 100-elementigen Liste ab, wenn das letzte Element der Liste auf das 50. zeigt?

Mit einer Breitensuche wäre es wohl möglich, also wenn man von n Elementen gleichzeitig startet und dann nacheinander jeweils ein Schritt macht. Dann braucht man aber wieder Speicher...

 

[killerchicken_inaktiv]

ah, danke, genau da war der Denkfehler bei mir :-) Ich wusste doch dass es nicht gehen können sollte

 

[Clawg]

Bin jetzt mal auf die Antwort der Firma gespannt (nein, das hier war keine Hausaufgabe, den Test habe ich ja gestern schon geschrieben)

 

[Clawg]

Ok, es geht doch

...
2 Pointer, einer doppelt so schnell wie der andere. Wenn der eine den anderen überholt -> Zyklus.

Mmh ^_^