Rozumiem, że spotkanie Żółwia i Zająca kończy istnienie pętli, ale w jaki sposób przeniesienie żółwia na początek połączonej listy przy jednoczesnym utrzymaniu zająca w miejscu spotkania, a następnie przesuwanie obu krok po kroku sprawia, że spotykają się w punkcie początkowym cyklu?
algorithm
linked-list
cycle
floyd-cycle-finding
Zapalony programista
źródło
źródło
Odpowiedzi:
To jest algorytm Floyda do wykrywania cykli . Pytasz o drugą fazę algorytmu - po znalezieniu węzła będącego częścią cyklu, jak znaleźć początek cyklu?
W pierwszej części algorytmu Floyda zając porusza się o dwa kroki na każdy krok żółwia. Jeśli żółw i zając kiedykolwiek się spotkają, istnieje cykl, a miejsce spotkania jest częścią cyklu, ale niekoniecznie pierwszym węzłem w cyklu.
Kiedy żółw i zając spotykają się, znaleźliśmy najmniejsze i (liczbę kroków podjętych przez żółwia) takie, że X i = X 2i . Niech mi reprezentuje liczbę kroków do przejścia od X 0 do początku cyklu, a lambda niech reprezentuje długość cyklu. Wtedy i = mu + a lambda, i 2i = mu + b lambda, gdzie a i b są liczbami całkowitymi oznaczającymi, ile razy żółw i zając przeszli przez cykl. Odejmowanie pierwszego równania od drugiego daje i = (ba) * lambda, więc i jest całkowitą wielokrotnością lambda. Dlatego X i + mu = X mu . X i reprezentuje miejsce spotkania żółwia i zająca. Jeśli przesuniesz żółwia z powrotem do węzła początkowego X0 , i pozwól żółwiowi i zającowi kontynuować z tą samą prędkością, po dodatkowych krokach żółw osiągnie X mu , a zając osiągnie X i + mu = X mu , więc drugie miejsce spotkania oznacza początek cykl.
źródło
X_mu
początku cyklu (zgodnie z definicją mi). Następnie, jeśli wykonasz i więcej kroków, gdzie i jest wielokrotnością długości cyklu, kończysz z powrotem na początku cyklu:X_mu + i
=X_mu
. Ale dodawanie jest przemienne, więc jest to równoważne z podjęciem kroków, aby dostać się od początku do pierwszego miejsca spotkaniaX_i
, a następnie dodatkowych kroków, aby wrócić doX_mu
początku cyklu.i
znajduje się w pewnym punkcie cyklu, myślę, że równanie powinno byći = mu + k + a*lambda
i2i = mu + k + b*lambda
, gdziek
jest liczba kroków od początku cyklu do punktu spotkania. Jednak odjęcie obu równań daje ten sam wynik.Spróbuję wyjaśnić własnymi słowami algorytm wykrywania cykli, który znajduje się pod adresem http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare .
Jak to działa
Niech żółw i zając (nazwa wskaźników) wskazują na początek listy cyklem, jak na powyższym schemacie.
Postawmy hipotezę, że jeśli przesuniemy żółwia o 1 krok na raz i zając o 2 kroki na raz, w końcu spotkają się w pewnym momencie. Pokażmy, że przede wszystkim ta hipoteza jest prawdziwa.
Rysunek przedstawia listę z cyklem. Cykl ma długość
n
i początkowom
oddalamy się od niego o kilka kroków. Powiedzmy również, że miejsce spotkania jestk
kilka kroków od początku cyklu, a żółw i zając spotykają się, gdy żółw zrobii
całkowite kroki. (Hare podjąłby wtedy2i
totalne kroki).Muszą być spełnione następujące 2 warunki:
Pierwsza mówi, że żółw porusza się po
i
krokach iw tychi
krokach najpierw dostaje się do cyklu. Następnie przechodzi przezp
czasy cyklu dla pewnej liczby dodatniejp
. W końcu przechodzi przezk
kolejne węzły, aż napotka zająca.Podobnie jest z zającem. Porusza się
2i
krokami iw tych2i
krokach najpierw dostaje się do cyklu. Następnie przechodzi przezq
czasy cyklu dla pewnej liczby dodatniejq
. W końcu przechodzi przezk
więcej węzłów, aż napotka żółwia.Ponieważ zając podróżuje z podwójną prędkością żółwia, a czas jest stały dla obu, kiedy docierają do miejsca spotkania.
Używając prostej zależności prędkości, czasu i odległości,
Spośród m, n, k, p, q, pierwsze dwie są właściwościami podanej listy. Jeśli potrafimy wykazać, że istnieje co najmniej jeden zbiór wartości k, q, p, który sprawia, że to równanie jest prawdziwe, to pokażemy, że hipoteza jest poprawna.
Jeden taki zestaw rozwiązań wygląda następująco:
Możemy sprawdzić, czy te wartości działają w następujący sposób:
W tym zestawie
i
jestOczywiście powinieneś zobaczyć, że niekoniecznie jest to najmniejsze możliwe. Innymi słowy, żółw i zając mogły się już spotkać wiele razy. Ponieważ jednak pokazujemy, że spotykają się one przynajmniej raz, możemy powiedzieć, że hipoteza jest poprawna. Więc musieliby się spotkać, gdybyśmy przesunęli jeden z nich o 1 stopień, a drugi o 2 stopnie naraz.
Teraz możemy przejść do drugiej części algorytmu, czyli znaleźć początek cyklu.
Początek cyklu
Gdy żółw i zając spotkają się, umieśćmy żółwia z powrotem na początku listy i trzymajmy zająca w miejscu, w którym się spotkali (czyli o k kroków od początku cyklu).
Hipoteza jest taka, że jeśli pozwolimy im poruszać się z tą samą prędkością (1 krok dla obu), pierwszy raz spotkają się ponownie, będzie to początek cyklu.
Udowodnijmy tę hipotezę.
Załóżmy najpierw, że jakaś wyrocznia mówi nam, czym jest m.
Następnie, jeśli pozwolimy im poruszać się m + k kroków, żółw musiałby dotrzeć do punktu, w którym pierwotnie się spotkali (k kroków od początku cyklu - patrz rysunek).
Wcześniej to pokazaliśmy
m + k = (q - 2p) n
.Ponieważ m + k kroków jest wielokrotnością długości cyklu n, zając w międzyczasie przeszedłby cykl (q-2p) razy i wróciłby do tego samego punktu (k kroków od początku cyklu).
Teraz, zamiast pozwolić im poruszać się m + k kroków, jeśli pozwolimy im poruszać się tylko m kroków, żółw przybyłby na początek cyklu. Zającowi brakłoby k kroków do wykonania obrotów (q-2p). Ponieważ zaczynał k kroków przed początkiem cyklu, zając musiałby dojść do początku cyklu.
W rezultacie wyjaśnia to, że musieliby spotkać się na początku cyklu po pewnej liczbie kroków po raz pierwszy (za pierwszym razem, ponieważ żółw właśnie przybył do cyklu po m krokach i nigdy nie widział zająca, który był już w cykl).
Teraz wiemy, że liczba kroków, które musimy przesunąć, aż się spotkają, okazuje się być odległością od początku listy do początku cyklu, m. Oczywiście algorytm nie musi wiedzieć, czym jest m. Po prostu poruszy zarówno żółwia, jak i zająca, krok po kroku, aż się spotkają. Punktem spotkania musi być początek cyklu, a liczba kroków musi być odległością (m) do początku cyklu. Zakładając, że znamy długość listy, możemy również obliczyć długość cyklu odejmowania m od długości listy.
źródło
m + k = (q - 2p) n
można dodatkowo uprościć dom + k = q*n
. Dzieje się tak, ponieważ liczba pętli, które wykonuje żółw, zawsze będzie wynosić zero, ponieważ zając nigdy nie może wyprzedzić żółwia bez jego spotkania. Pomyśl o tym.Zobacz ten obraz:
Odległość przebyta przez slowPointer przed spotkaniem = x + y
Odległość przebyta przez fastPointer przed spotkaniem = (x + y + z) + y = x + 2y + z
Ponieważ fastPointer porusza się z dwukrotnie większą prędkością niż slowPointer, a czas jest stały dla obu, gdy dotrze do miejsca spotkania.
Czyli używając prostej zależności prędkości, czasu i odległości 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
W związku z tym, przesuwając slowPointer na początek połączonej listy i sprawiając, że zarówno slowPointer, jak i fastPointer przenoszą jeden węzeł na raz, oba mają tę samą odległość do pokonania .
Dotrą do punktu, w którym zaczyna się pętla na połączonej liście.
źródło
Prosta i niedoceniana odpowiedź Old Monka wyjaśnia znalezienie cyklu, gdy szybki biegacz wykonuje tylko jeden pełny cykl. W tej odpowiedzi wyjaśniam przypadek, w którym szybki biegacz wykonał pętlę wiele razy, zanim powolny biegacz wejdzie w pętlę.
Używając tego samego obrazu:
Powiedzmy, że szybki biegacz pokonał pętlę m razy przed spotkaniem wolnego i szybkiego. To znaczy że:
Ponieważ szybkie biegi z dwukrotnie większą prędkością niż wolne i że biegły one w tym samym czasie, oznacza to, że jeśli podwoimy dystans pokonany przez wolne, otrzymamy dystans pokonany szybko. A zatem,
Rozwiązywanie dla x daje,
W prawdziwym scenariuszu oznaczałoby to, x = (m - 1) cała pętla + dodatkowy dystans z .
Stąd, jeśli umieścimy jeden wskaźnik na początku listy, a drugi zostawimy w miejscu spotkania, to przesunięcie ich z tą samą prędkością spowoduje, że wskaźnik w pętli ukończy m - 1 przebiegów pętli, a następnie napotka drugi wskaźnik bezpośrednio na początku pętli.
źródło
To bardzo proste. Możesz myśleć w kategoriach prędkości względnej. Jeśli królik porusza się o dwa węzły, a żółw przesuwa się o jeden węzeł, w stosunku do żółwia, królik porusza się o jeden węzeł (załóżmy, że żółw odpoczywa). Tak więc, jeśli przesuniemy jeden węzeł na liście połączonej cyklicznie, z pewnością spotkamy się ponownie w tym miejscu.
Po znalezieniu punktu połączenia wewnątrz listy połączonej kołowo problem sprowadza się teraz do znalezienia punktu przecięcia dwóch połączonych list.
źródło
W czasie pierwszego zderzenia żółw wykonał m + k kroków, jak pokazano powyżej. Zając porusza się dwa razy szybciej niż żółw, co oznacza, że zając wykonał 2 (m + k) kroki. Z tych prostych faktów możemy wyprowadzić następujący wykres.
W tym momencie przenosimy żółwia z powrotem na początek i deklarujemy, że zarówno zając, jak i żółw muszą poruszać się o jeden krok na raz. Z definicji, po m krokach, żółw będzie na początku cyklu. Gdzie będzie zając?
Zając również będzie na początku cyklu. Wynika to jasno z drugiego wykresu: kiedy żółw cofnął się do początku, zając przeszedł k kroków do ostatniego cyklu. Po m krokach zając zakończy kolejny cykl i zderzy się z żółwiem.
źródło
Podejście:
Istnieją dwie wskazówki:
Jeśli te dwa wskaźniki spotykają się, oznacza to, że istnieje pętla. Gdy się spotkają, jeden z węzłów wskaże głowę, a następnie oba węzły przejdą do jednego węzła na raz. Spotkają się na początku pętli.
Uzasadnienie: Gdzie spotykają się, kiedy dwoje ludzi idzie okrężnym torem, jeden z nich z dwukrotnie większą prędkością od drugiego? Dokładnie tam, gdzie zaczęli.
Teraz załóżmy, że szybki biegacz ma przewagę na starcie
k
kroków nan
okrążeniu krokowym. gdzie się spotkają Dokładnie pon-k
krokach. Gdy biegacz wolny pokonywałby(n-k)
kroki, biegacz szybki pokrywałbyk+2(n-k)
kroki. ( tj.k+2n-2k
kroki, czyli2n-k
kroki ). tj.(n-k)
kroki (ścieżka jest okrężna i nie interesuje nas liczba rund, po których się spotykają; interesuje nas tylko pozycja, w której się spotykają).W jaki sposób szybki biegacz uzyskał przewagę na początku
k
kroków? Ponieważ powolnemu biegaczowi zajęło tyle kroków, aby dotrzeć do początku pętli. Zatem początek pętli to k kroków od węzła głównego.Uwaga: Węzeł, w którym spotkały się oba wskaźniki, jest
k
oddalony o kilka kroków od początku pętli (wewnątrz pętli), a węzeł główny jestk
oddalony o kilka kroków od początku pętli. Więc kiedy wskaźnik przesuwa się w równym tempie 1 kroku od bota, te węzły spotkają się na początku pętli.Uważam, że jest to proste. Daj mi znać, jeśli jakaś część jest niejednoznaczna.
źródło
Okej, załóżmy więc, że zając i żółw spotykają się w punkcie oddalonym o k kroków od początku cyklu, liczba kroków przed rozpoczęciem cyklu wynosi mi, a długość cyklu to L.
Więc teraz w miejscu spotkania ->
Odległość pokonana przez żółwia = mu + a * L + k - Równanie 1
(Kroki podjęte w celu osiągnięcia początku cyklu + kroki podjęte w celu pokrycia iteracji `` a '' cyklu + k kroków od początku cyklu) (gdzie a jest pewną dodatnią stałą)
Odległość pokonana przez zająca = mu + b * L + k - Równanie 2
(Kroki podjęte w celu osiągnięcia początku cyklu + kroki podjęte w celu pokrycia iteracji `` b '' cyklu + k kroków od początku cyklu) (gdzie b jest pewną dodatnią stałą, a b> = a)
Zatem dodatkowa odległość pokonana przez zająca to = Równanie 2 - Równanie 1 = (ba) * L
Należy pamiętać, że ta odległość jest również równa odległości żółwia od punktu wyjścia, ponieważ zając porusza się 2 razy szybciej niż żółw. Można to przyrównać do „mu + k”, które jest również odległością miejsca spotkania od początku, jeśli nie uwzględnimy wielu przejść cyklu.
Zatem mu + k = (ba) * L
Zatem mi kroki od tego punktu prowadziłyby z powrotem do początku cyklu (ponieważ k kroków od początku cyklu zostało już zrobionych, aby dotrzeć do punktu spotkania). Może się to zdarzyć w tym samym cyklu lub w dowolnym z kolejnych cykli. Tak więc, jeśli teraz przeniesiemy żółwia na początek połączonej listy, zajmie to kilka kroków, aby dotrzeć do punktu początkowego cyklu, a zając zrobi wiele kroków, aby również dotrzeć do początku cyklu, a zatem obaj spotkają się na punkt początkowy cyklu.
PS Szczerze mówiąc, miałem w głowie to samo pytanie, co oryginalny plakat i przeczytałem pierwszą odpowiedź, wyjaśnili kilka rzeczy, ale nie mogłem jasno dojść do końcowego wyniku, więc starałem się zrobić to po swojemu i łatwiej było to zrozumieć.
źródło
kredyt obrazu
Odległość wywołania liczba łączy, po których podąża wskaźnik, oraz czas, przez ile iteracji algorytm przesuwa powolny wskaźnik o jedno łącze, a szybki wskaźnik o dwa łącza. Istnieje N węzłów przed cyklem o długości C, oznaczonych jako przesunięcie cyklu od k = 0 do C-1.
Aby dotrzeć do początku cyklu, zwolnienie zajmuje N czasu i odległości. Oznacza to, że szybkie zajmuje N dystansu w cyklu (N aby się tam dostać, N aby obrócić). Tak więc w czasie N, powolny jest przy przesunięciu cyklu k = 0, a szybki przy przesunięciu cyklu k = N mod C.
Jeśli N mod C jest równe zero, teraz pasują powoli i szybko, a cykl znajduje się w czasie N i pozycji cyklu k = 0.
Jeśli N mod C nie wynosi zero, to szybko musi teraz dogonić wolne, które w momencie N jest odległością C- (N mod C) w tyle w cyklu.
Ponieważ szybkie ruchy 2 za każde 1 wolnego, zmniejszając odległość o 1 w każdej iteracji, zajmuje to tyle samo dodatkowego czasu, co odległość między szybkimi i wolnymi w czasie N, czyli C- (N mod C). Ponieważ powolne porusza się od przesunięcia 0, jest to również przesunięcie, w którym się spotykają.
Tak więc, jeśli N mod C wynosi zero, faza 1 zatrzymuje się po N iteracjach na początku cyklu. W przeciwnym razie faza 1 zatrzymuje się po iteracjach N + C- (N mod C) z przesunięciem C- (N mod C) do cyklu.
Ok, więc faza 2: powolne zajmuje N więcej kroków, aby dostać się do cyklu, w którym to momencie szybki (teraz ruch 1 na krok czasu) jest na (C- (N mod C) + N) mod C = 0. Więc się spotykają na początku cyklu po fazie 2.
Aby uzyskać kompletność, faza 3 oblicza długość cyklu, przechodząc jeszcze raz przez cykl:
źródło
Zredukuj problem do problemu z pętlą, a następnie wróć do pierwotnego problemu
Poniższe wyjaśnienie wydaje mi się bardziej intuicyjne.
Weź dwie wskazówki ( 1 = żółw i 2 = zając), które zaczynają się od głowy ( O ), 1 ma długość kroku 1 , 2 ma długość kroku 2 . Pomyśl o chwili, w której 1 osiąga węzeł początkowy tego cyklu ( A ).
Chcemy odpowiedzieć na pytanie „Gdzie jest 2, gdy 1 jest w A?” .
Czyli
OA = a
jest liczbą naturalną (a >= 0
). Ale można to zapisać w następujący sposób:,a = k*n + b
gdziea, k, n, b are natural numbers
:n
= długość cykluk >= 0
= stała0 <= b <= n-1
To znaczy, że
b = a % n
.Np .: jeśli
a = 20
in = 8
=>k = 2
ib = 4
ponieważ20 = 2*8 + 4
.Odległość pokonana przez 1 to
d = OA = a = k*n + b
. Ale w tym samym czasie 2 okładkiD = 2*d = d + d = OA + d = OA + k*n + b
. Oznacza to, że gdy 2 jest w A, musi się pokrywaćk*n + b
. Jak widać,k
jest to liczba okrążeń, ale po tych okrążeniach 2 będzie b daleko od A. Więc znaleźliśmy gdzie 2 jest, gdy 1 jest w A. Nazwijmy ten punktB
, gdzieAB = b
.Teraz sprowadzamy problem do koła. Pytanie brzmi: „Gdzie jest miejsce spotkania?” . Gdzie to jest C ?
Z każdym krokiem 2 zmniejsza odległość od 1 o
1
(powiedzmy metr), ponieważ 1 oddala się od 2 z1
, ale jednocześnie 2 zbliża się do 1 o2
.Zatem przecięcie będzie miało miejsce, gdy odległość między 1 a 2 będzie wynosić zero. Oznacza to, że 2 zmniejsza
n - b
odległość. Aby to osiągnąć, 1 zrobin - b
kroki, a 2 zrobi2*(n - b)
kroki.Tak więc punkt przecięcia będzie
n - b
daleko od A (zgodnie z ruchem wskazówek zegara), ponieważ jest to odległość pokonywana przez 1, aż do spotkania 2 . => odległość między C i A wynosiCA = b
, ponieważAC = AB + BC = n - b
iCA = n - AC
. Nie myśl, żeAC = CA
ponieważAC
odległość nie jest trywialną odległością matematyczną, jest to liczba kroków między A i C (gdzie A to punkt początkowy, a C to punkt końcowy).Teraz wróćmy do początkowego schematu.
Wiemy o tym
a = k*n + b
iCA = b
.Możemy wziąć 2 nowe wskaźniki 1 ' i 1' ' , gdzie 1' zaczyna się od głowy ( O ), a 1 '' zaczyna się od punktu przecięcia ( C ).
Podczas gdy 1 ' przechodzi z O do A , 1' ' przechodzi z C do A i kontynuuje kończenie
k
okrążeń. Więc punkt przecięcia jest .źródło
Jeśli wskaźniki spotkały się w punkcie P, jak pokazano na rysunku, odległość Z + Y jest punktem P, a X + Y jest również punktem P, co oznacza Z = X. Dlatego utrzymywanie ruchu jednego wskaźnika od punktu P i przesuwanie drugiego od początku (S) do ich spotkania, co oznacza przesunięcie równej odległości (Z lub X) do tego samego punktu M (odległość Z od P i X od S) będzie rozpoczęcie pętli. Prosty!
źródło
Biorąc pod uwagę całą powyższą analizę, jeśli jesteś osobą uczącą się na przykładzie, próbowałem napisać krótką analizę i przykład, które pomogą wyjaśnić matematykę, którą wszyscy próbowali wyjaśnić. No to ruszamy!
Analiza:
Jeśli mamy dwa wskaźniki, jeden szybszy od drugiego, i przesuniemy je razem, ostatecznie spotkają się one ponownie, aby wskazać cykl lub wartość zerową, aby wskazać brak cyklu.
Aby znaleźć punkt początkowy cyklu, pozwól ...
m
być odległością od głowy do początku cyklu;d
być liczbą węzłów w cyklu;p1
być prędkością wolniejszego wskaźnika;p2
być prędkością szybszego wskaźnika, np. 2 oznacza przejście przez dwa węzły naraz.Obserwuj następujące iteracje:
Na podstawie powyższych przykładowych danych możemy łatwo stwierdzić, że ilekroć spotykają się szybsze i wolniejsze wskaźniki, są one oddalone o
m
kilka kroków od początku cyklu. Aby rozwiązać ten problem, umieść szybszą wskazówkę z powrotem w głowicy i ustaw jej prędkość na prędkość wolniejszej wskazówki. Kiedy spotykają się ponownie, węzeł jest początkiem cyklu.źródło
powiedzmy,
mamy 2 wskaźniki A i B, A biegnie z prędkością 1x, B z prędkością 2x, oba zaczynają się od początku.
kiedy A osiągnie N [0], B powinno już być w N [m]. (Uwaga: A używa m kroków, aby osiągnąć N [0], a B powinno być m kroków dalej)
Następnie A wykonuje k kolejnych kroków, aby zderzyć się z B, tj. A jest w punkcie N [k], B jest w punkcie N [m + 2k] (Uwaga: B powinien przebiegać przez 2k kroków zaczynając od N [m])
Zderzenie A z B odpowiednio w N [k] i N [m + 2k] oznacza k = m + 2k, czyli k = -m
Tak więc, aby wrócić do N [0] z N [k], potrzebujemy m więcej kroków.
Mówiąc najprościej, po znalezieniu węzła kolizji wystarczy wykonać m więcej kroków. Możemy mieć wskaźnik do uruchomienia od początku i wskaźnik biegnący od węzła kolizji, spotkają się one na N [0] po m krokach.
Dlatego pseudokod jest następujący:
źródło
Nie sądzę, żeby to prawda, że kiedy się spotykają, to jest punkt wyjścia. Ale tak, jeśli drugi wskaźnik (F) znajdował się wcześniej w miejscu spotkania, to ten wskaźnik będzie na końcu pętli zamiast na początku pętli, a wskaźnik (S), który rozpoczął się od początku listy, będzie kończą się na początku pętli. na przykład:
źródło
Proste wyjaśnienie z wykorzystaniem idei prędkości względnej nauczanej w liceum - wykład Fizyka 101 / Kinematyka.
Załóżmy, że odległość od początku połączonej listy do początku okręgu to
x
przeskoki. Nazwijmy początek okręgu punktemX
(wielkimi literami - patrz rysunek powyżej). Przyjmijmy również, że całkowity rozmiar koła to N przeskoków.Prędkość zająca = 2 * Prędkość żółwia. Więc to jest
1 hops/sec
i2 hops/sec
odpowiednioKiedy żółw osiągnie początek koła
X
, zając musi dalejx
przeskakiwać w miejscuY
na rysunku. (Ponieważ zając przebył dwukrotnie większą odległość niż żółw).Zatem długość pozostałego łuku zgodnie z ruchem wskazówek zegara od X do Y byłaby
N-x
. Tak się składa, że jest to również względna odległość, jaką należy pokonać między zającem a żółwiem, aby mogły się spotkać . Powiedzmy, że ta względna odległość zostanie pokonana w czasie,t_m
tj. W czasie do spotkania. Względna prędkość to(2 hops/sec - 1 hops/sec)
np1 hops/sec
. Zatem używając, odległość względna = prędkość względna X czas, otrzymujemyt
=N-x
sek. Tak więc zajmieN-x
to dotarcie do miejsca spotkania zarówno żółwia, jak i zająca.Teraz za
N-x
sekundę iz1 hops/sec
dużą prędkością żółw, który był wcześniej na miejscuX
, pokona skok Nx, aby dotrzeć do miejsca spotkaniaM
. Oznacza to, że punkt spotkaniaM
znajduje się wN-x
przeskokach w kierunku przeciwnym do ruchu wskazówek zegara odX
= (co dalej oznacza) =>, żex
pozostała odległość od punktuM
doX
ruchu wskazówek zegara.Ale
x
jest to także odległość do punktuX
od początku połączonej listy.Teraz nie obchodzi nas, jaka
x
odpowiada liczbie przeskoków . Jeśli umieścimy jednego żółwia na początku LinkedList i jednego żółwia w miejscu spotkaniaM
i pozwolimy im skakać / chodzić, spotkają się w punkcieX
, który jest punktem (lub węzłem), którego potrzebujemy.źródło
Pomocna byłaby praca z diagramem. Próbuję wyjaśnić problem bez równań.
źródło
-jest k kroków przed pętlą. Nie wiemy, czym jest k i nie musimy się tego dowiadywać. Możemy pracować abstrakcyjnie, używając tylko k.
--Po k kroków
----- T jest na początku cyklu
----- H to k kroków w cyklu (przeszedł łącznie 2k, a zatem k w pętlę)
** mają teraz rozmiar pętli - k od siebie
(zwróć uwagę, że k == K == mod (loopsize, k) - np. jeśli węzeł jest 2 kroki w cyklu 5 węzłów, to również 7, 12 lub 392 kroki, więc jak duży jest cykl, k nie czynnik w.
Ponieważ dogonią się w tempie 1 kroku na jednostkę czasu, ponieważ jeden porusza się dwa razy szybciej niż drugi, spotkają się przy rozmiarze pętli - k.
Oznacza to, że osiągnięcie początku cyklu zajmie k węzłów, a zatem odległość od głowy do początku cyklu i kolizji do początku cyklu jest taka sama.
Więc teraz po pierwszym zderzeniu przenieś T z powrotem do głowy. T i H spotkają się na początku cyklu, jeśli poruszasz się w tempie 1 każdy. (w k krokach dla obu)
Oznacza to, że algorytm to:
// zajmij się przypadkiem, gdy k = 0 lub T i H spotkały się na początku pętli, obliczając długość pętli
- policz długość cyklu, przesuwając T lub H wokół niego za pomocą licznika
- przenieś wskaźnik T2 na początek listy
- przesuń wskaźnik długości kroków cyklu
- przesuń kolejny wskaźnik H2 do głowy
- przesuń T2 i H2 w tandemie, aż spotkają się na początku cyklu
Otóż to!
źródło
Odpowiedzi na to jest już wiele, ale kiedyś wymyśliłem diagram, który jest dla mnie bardziej intuicyjny wizualnie. Być może pomoże innym ludziom.
Głównymi momentami aha dla mnie były:
Podziel T (żółw) na T1 (przed pętlą) i T2 (w pętli).
Odejmij T od H , gdzie wizualnie się nakładają. Co zostało ( H - T = H” ) wynosi T .
źródło
Wiem, że istnieje już zaakceptowana odpowiedź na ten problem, ale nadal będę starał się odpowiadać w sposób płynny. Założyć :
Teraz pozwól zającowi i żółwiowi spotkać się po czasie „t” od początku.
Obserwacje:
Jeśli, odległość przebyta przez żółwia = v * t = x + (bk) (powiedzmy)
Wówczas Odległość przebyta przez zająca = 2 * v * t = x + (b - k) + b (ponieważ zając przeszedł już raz zapętloną część)
Teraz czasy spotkań są takie same.
=> x + 2 * b - k = 2 * (x + b - k)
=> x = k
Oznacza to oczywiście, że długość ścieżki, która nie jest zapętlona, jest taka sama, jak odległość punktu początkowego pętli od punktu, w którym oba się spotykają.
źródło
W rzeczywistości łatwo jest udowodnić, że obaj spotkają się na początku, jeśli weźmiesz pod uwagę matematykę za miejscem spotkania.
Najpierw niech m oznacza punkt początkowy cyklu na połączonej liście, a n oznacza długość cyklu. Następnie na spotkanie zająca i żółwia mamy:
Mówiąc bardziej matematycznie:
więc spotkają się w czasie t, który powinien być wielokrotnością długości cyklu. Oznacza to, że spotykają się w miejscu, którym jest
(t-m) modulo n = (0-m) modulo n = (-m) modulo n
.Wracając teraz do pytania, jeśli przesuniesz jeden wskaźnik z początku połączonej listy, a drugi z punktu przecięcia, po m krokach zając (który porusza się w cyklu) dojdzie do punktu
((-m) + m) modulo n = 0 modulo n
co jest niczym innym jak początkiem cyklu, więc widzimy, że po m krokach dochodzi do początku cyklu i żółw go tam spotka, pokonując m kroków od początku połączonej listy.Na marginesie, możemy również obliczyć czas ich przecięcia się w następujący sposób: Warunek
t = 0 modulo n
mówi nam, że spotkają się w czasie, który jest wielokrotnością długości cyklu, a także t powinno być większe niż m, ponieważ spotkałyby się w cykl. Zatem potrzebny czas będzie równy pierwszej wielokrotności n, która jest większa niż m .źródło
Załóżmy, że twoje wskaźniki spotykają się na przecięciu punktu y i z.
n i m to odpowiednio liczba pętli, które są odpowiednio szybsze i wolniejsze przed spotkaniem.
Resztę dowodu znajdziesz na obrazku. Znajdź punkt początkowy pętli na połączonej liście
źródło