W dniu 2011-06-15 10:19, Wojciech "Spook" Sura pisze:
> 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.

No to mój algorytm działa.
A Piotrek podał bardzo podobny, tez wymaga 3*n
inkrementacji iteratorów.

pozdrawiam
bartekltg

do góry

W dniu 2011-06-15 17:14, Stachu 'Dozzie' K. pisze:
> 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?

Jak zdefiniujesz długość czegoś, co nie ma końca?

Chodziło mi tylko o nieprecyzyjne w tym kontekście użycie słowa
,,długość". Możesz znać ilość elementów w strukturze, ale znaczenie
słowa długość jest chyba trochę inne...

do góry

On 2011-06-15 09:18, Piotr Chamera wrote:
> Po liście od początku startuje dwóch biegaczy

To zadanie było na rozmowach kwalifikacyjnych Suna o czym można poczytać w:

http://tinyurl.com/6hhw6tj

Pozycje warto skonsumować ze względuy na zarozumialstwo autorów i
poboczne perełki historii tamtych czasów co kilka stron jak choćby
opowieśc o Billu i jego samochodzie ;)

do góry

On 2011-06-15, Piotr Chamera <p...@p...onet.pl> wrote:
> W dniu 2011-06-15 17:14, Stachu 'Dozzie' K. pisze:
>> 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?
>
> Jak zdefiniujesz długość czegoś, co nie ma końca?

Dla okręgu jest dość łatwo: \pi * d, gdzie d jest średnicą.

> Chodziło mi tylko o nieprecyzyjne w tym kontekście użycie słowa
> ,,długość". Możesz znać ilość elementów w strukturze, ale znaczenie
> słowa długość jest chyba trochę inne...

Nie jest powszechnie przyjęte żeby długość listy definiować jako coś
innego niż ilość elementów w niej zawartych.

Ciągnięcie tej gałęzi wątku nie ma specjalnego sensu poznawczego. Może
w tym miejscu skończymy?

--
Secunia non olet.
Stanislaw Klekot

do góry

On 2011-06-15, Sebastian Biały <h...@p...onet.pl> wrote:
> On 2011-06-15 09:18, Piotr Chamera wrote:
>> Po liście od początku startuje dwóch biegaczy
>
> To zadanie było na rozmowach kwalifikacyjnych Suna o czym można poczytać w:
>
> http://tinyurl.com/6hhw6tj

Zasadniczo ta technika wykrywania cyklu jest znana jako "giant-step
baby-step" w jednym z algorytmów wyznaczania logarytmu dyskretnego.

--
Secunia non olet.
Stanislaw Klekot

do góry

Dnia 15-06-2011 o 10:42:26 sielim <s...@t...tez.wp.pl> napisał(a):
> 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 :)

Nawet nie tyle listę, co stos, na którym są odkładane rekordy wywołań
rekurencyjnych funkcji, bo trzeba pamiętać, w jaki sposób odwrócić z
powrotem kolejność elementów listy. Czyli jednak zamaskowałem to
pamięciowe "n" całkiem sprytnie ;)

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

W dniu 15.06.2011 22:08, Stachu 'Dozzie' K. pisze:
> Nie jest powszechnie przyjęte żeby długość listy definiować jako coś
> innego niż ilość elementów w niej zawartych.
Jest za to dość powszechnie przyjęte, żeby listę definiować jako
strukturę o określonej "kolejności" z wyróżnioną głową i ogonem. Twór z
cyklem do tej definicji nie pasuje.

--
Pozdrawiam
Michoo

do góry