Hej!

Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
czasie liniowym?

Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
umiem zejść do stałego. Macie jakieś pomysły?

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

W dniu 2011-06-15 08:19, Wojciech "Spook" Sura pisze:
> Hej!
>
> Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
> jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
> czasie liniowym?


Ale odnaleźć cykl oznacza wypisać wszystkie elementy cyklu,
rownoważnie znaleźć jakikolwiek element cyklu, czy
znaleźć element 'wejściowy'?

Jeśli to pierwsze, to:

Masz dwa iteratory, biegacza i wartownika.

ustalasz wartownika na pierwszym elemencie,
nastepnie w pętli k =1,2...
Niech biagacz przeiteruje 2^k elementów liczac
od wartownika. Jesli natrafił na wartownika
(petla) lub koniec listy, kończymy pętle.
Jeśli nie, ustawiamy wartownika na ostatniej
pozycji biegacza.

Jeśli nie było ślepego końca, biegniemy
ostatni raz w kolko po cyklu wypisując składowe.


Wartownika postawimy na cyklu po co najwyzej 2n ruchach
biegacza. Dodatkowe n na ostatnie przejście cyklu,
łącznie zrobimy 3*n operacji przesuniecie biegacza + test warunku.

Jak wyznaczyć 'pierwszy' element cyklu liniowo w stałej pamięci
nie mam pomysłu.

> Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
> umiem zejść do stałego. Macie jakieś pomysły?

Podejrzewam, że to ten sam tylko założyłeś od razu trudniejszą
wersje problemu.

pozdrawiam
bartekltg

do góry

Użytkownik "Wojciech "Spook" Sura"
<wojciech.sura_no@spam_poczta.medi.com.pl> napisał w wiadomości
news:op.vw3s6w1gppa1dq@l3.medicom.local...

>Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
>jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
>czasie liniowym?
>
>Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
>umiem zejść do stałego. Macie jakieś pomysły?
>
>Pozdrawiam -- Spook.

Tak na mój pierwszy rzut oka, to jeśli nie znamy z góry rozmiaru
listy to się nie da. W czasie liniowym i przy z góry założonym maksymalnym
zużyciu pamięci to nie da sięnawet ze 100% pewnością stwierdzić, czy
lista w ogóle ma cykl. To tak jak chodzić po labiryncie i mieć wiaderko
z ograniczoną liczbą okruchów chleba do zaznaczania odwiedzonych
komnat. Ja tu widzę co najmniej potrzebę pamięci rzędu o(log(n)) do
zaznaczania obszarów już odwiedzonych, czy też 'stawiania wartowników'.
Imo sprawa się uprości, jeśli założymy, że cykl może mieć nie więcej niż
k. Wtedy da się zastosować algorytm systematycznego 'zamykania' obszarów
listy które na pewno nie należą do cyklu i potrzeba pamięciowa
jest wtedy stała o(k).

do góry

W dniu 2011-06-15 08:19, Wojciech "Spook" Sura pisze:
> Hej!
>
> Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
> jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
> czasie liniowym?
>
> Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
> umiem zejść do stałego. Macie jakieś pomysły?

Google rządzi :) znalazłem coś takiego:

Po liście od początku startuje dwóch biegaczy, z których jeden jest
dwukrotnie szybszy (pierwszy idzie co 1 element, drugi co dwa) -
jeśli kiedykolwiek się spotkają, to lista ma cykl (jeśli ma to spotkają
się po max n krokach).

do góry

Użytkownik "Piotr Chamera" <p...@p...onet.pl> napisał w
wiadomości news:it9md2$o1d$1@news.onet.pl...
>W dniu 2011-06-15 08:19, Wojciech "Spook" Sura pisze:
>> Hej!
>>
>> Kolega zaproponował zadanie: w jaki sposób odnaleźć cykl w liście
>> jednokierunkowej nie niszcząc jej, zachowując stałe zużycie pamięci i w
>> czasie liniowym?
>>
>> Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
>> umiem zejść do stałego. Macie jakieś pomysły?
>
> Google rządzi :) znalazłem coś takiego:
>
> Po liście od początku startuje dwóch biegaczy, z których jeden jest
> dwukrotnie szybszy (pierwszy idzie co 1 element, drugi co dwa) -
> jeśli kiedykolwiek się spotkają, to lista ma cykl (jeśli ma to spotkają
> się po max n krokach).

:))) Niezła jatka ... I rzeczywiście zadziała :)

do góry

Dnia 15-06-2011 o 08:42:48 bartekltg <b...@o...pl> napisał(a):
>> Mam pewien pomysł, ale niestety przy liniowym zużyciu pamięci, nijak nie
>> umiem zejść do stałego. Macie jakieś pomysły?
>
> Podejrzewam, że to ten sam tylko założyłeś od razu trudniejszą
> wersje problemu.

Chodziło tylko o stwierdzenie istnienia cyklu.

Wpadłem na pomysł rekurencyjnego odwrócenia listy. Jeśli algorytm dojdzie
do końca, z powrotem przywracamy oryginalną listę i zwracamy false; jeśli
zaś algorytm wróci do głowy, znów przywracamy oryginalną listę i zwracamy
true.

> pozdrawiam
> bartekltg

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry

Użytkownik "Wojciech "Spook" Sura"
<wojciech.sura_no@spam_poczta.medi.com.pl> napisał w wiadomości
news:op.vw3yp12mppa1dq@l3.medicom.local...

> Chodziło tylko o stwierdzenie istnienia cyklu.

> Wpadłem na pomysł rekurencyjnego odwrócenia listy. Jeśli algorytm dojdzie
> do końca, z powrotem przywracamy oryginalną listę i zwracamy false; jeśli
> zaś algorytm wróci do głowy, znów przywracamy oryginalną listę i zwracamy
> true.

Tak na pierwszy rzut oka (:) - rekurencja potrzebuje pamięci (na stosie).

Na drugi rzut oka: pomysł jest ciekawy, do zrobienia 'iteracyjnie' - tyle,
że próbujesz
chyłkiem wykorzystać listę jako ukrytą pamięć o rozmiarze n :)

do góry

Dnia Wed, 15 Jun 2011 10:19:03 +0200, Wojciech "Spook" Sura napisał(a):

> Chodziło tylko o stwierdzenie istnienia cyklu.

Jeśli znasz długość listy to:
1. startujesz od początku i idziesz z krokiem co jeden
2. liczysz ile elementów odwiedziłeś
3. jeśli liczba odwiedzonych jest większa niż liczba elementów w liście to
masz cykl

--
Tomek

do góry

W dniu 2011-06-15 16:05, Tomasz Sowa pisze:
> Dnia Wed, 15 Jun 2011 10:19:03 +0200, Wojciech "Spook" Sura napisał(a):
>
>> Chodziło tylko o stwierdzenie istnienia cyklu.
>
> Jeśli znasz długość listy to:
> 1. startujesz od początku i idziesz z krokiem co jeden
> 2. liczysz ile elementów odwiedziłeś
> 3. jeśli liczba odwiedzonych jest większa niż liczba elementów w liście to
> masz cykl

Jeśli znasz długość listy, to ona na pewno nie ma cyklu :)

do góry

On 2011-06-15, Piotr Chamera <p...@p...onet.pl> wrote:
> W dniu 2011-06-15 16:05, Tomasz Sowa pisze:
>> Dnia Wed, 15 Jun 2011 10:19:03 +0200, Wojciech "Spook" Sura napisał(a):
>>
>>> Chodziło tylko o stwierdzenie istnienia cyklu.
>>
>> Jeśli znasz długość listy to:
>> 1. startujesz od początku i idziesz z krokiem co jeden
>> 2. liczysz ile elementów odwiedziłeś
>> 3. jeśli liczba odwiedzonych jest większa niż liczba elementów w liście to
>> masz cykl
>
> Jeśli znasz długość listy, to ona na pewno nie ma cyklu :)

Erm. Dziesięcioelementowa lista nie może mieć cyklu?
Może zna długość bo liczył operacje dodania/usunięcia elementu?

--
Secunia non olet.
Stanislaw Klekot

do góry