Floyd ' s Syklin tunnistusalgoritmi | Syklin aloituskohdan määrittäminen

Voit viitata kohtaan ”Silmukan alkamisen havaitseminen yksitellen linkitetyssä luettelossa” , tässä on ote:

slowPointer kuljettu matka ennen tapaamista $ = x + y $

fastPointer kuljettu matka ennen tapaamista $ = (x + y + z) + y = x + 2y + z $

Koska fastPointer matkustaa kanssa kaksinkertainen slowPointer -nopeus ja -aika on vakio molemmille, kun saavutat kohtaamispisteen. Joten käyttämällä yksinkertaista nopeuden, ajan ja matkan suhdetta (slowPointer kuljettu puolet matkan pituudesta):

\ begin {align *} 2 * \ operaattorin nimi {dist} (\ text {slowPointer}) & = \ operaattorin nimi {dist} (\ text {fastPointer}) \\ 2 (x + y) & = x + 2y + z \\ 2x + 2y & = x + 2y + z \\ x & = z \ end {tasaa *}

Siirtämällä slowPointer linkitetyn luettelon alkuun ja tekemällä molemmat slowPointer ja fastPointer siirtääksesi solmun kerrallaan, molemmilla on sama etäisyys .

Ne saavuttavat siinä kohdassa, missä silmukka alkaa linkitetyssä luettelossa.

Kommentit

• Tässä oletat, että he kohtaavat yhden kierroksen jälkeen. Voi olla tapauksia (joissa sykli on pieni), joissa he saattavat tavata tietyn ei.
• @JotWaraich kuva ei edusta kaikkia tapauksia; logiikka pitää kuitenkin paikkansa edelleen
• tämä on suoraviivaisin vastaus tähän algoritmiin koko Internetissä
• En ole kovin varma siitä,

Olen nähnyt hyväksytyn vastauksen todisteena myös muualla. Vaikka se on helppo napata, se on väärä. Se osoittaa, että se on

$ x = z $ (mikä on ilmeisesti väärin, ja kaavio tekee siitä vain uskottavan, koska se on piirretty).

Mitä todella haluat todistaa on (käyttäen samoja muuttujia kuin yllä olevassa hyväksytyssä vastauksessa olevassa kaaviossa kuvataan):

$ z = x \ mod \ (y + z) $

$ (y + z) $ on silmukan pituus, $ L $

joten haluamme todistaa:

$ z = x \ mod \ L $

Tai että z on yhtenevä x: n kanssa (moduuli L)

Seuraavan todisteen tekeminen on mielestäni järkevämpää:

Kokouspiste, $ M = x + y $

$ 2 (x + y) = M + kL $, jossa $ k $ on jokin vakio.Periaatteessa nopean osoittimen kulkema etäisyys on $ x + y $ plus jokin silmukan pituuden moninkertainen, $ L $

$ x + y = kL $

$ x = kL – y $

Yllä oleva yhtälö osoittaa, että $ x $ on sama kuin joku silmukan pituuden kerrannaisista, $ L $ miinus $ y $. Joten jos nopea osoitin alkaa kohtaamispaikasta, $ M $ tai $ x + y $, se päätyy silmukan alkuun.

Kommentit

• En tiedä ’ en tiedä miksi tätä vastausta aliarvioidaan. Tämä näyttää olevan muodollisin todiste.
• @ I8Jälleen, jos x = z on väärä, sitten logiikkaa siirrettäessä nopea osoitin takaisin aloituspisteeseen & siirrä molemmat nopea & hidas osoitin silmukan alun löytämiseksi ei toimi ’. en ymmärrä mitä tarkoitit x = z: llä on väärin, selitä miten se on?
• @divine x = z on väärä, koska se tarkoittaa, että molemmat ovat tasa-arvoisia, mutta on hyväksyttävää, että sinulla on hyvin pitkä ” häntä ”(iso x) ja hyvin pieni ympyrä (pieni z). Käyttämällä moduulia olemme muodollisesti oikeita, haluamme vain todistaa, että x% L == z, toisin sanoen osoitin, joka kulkee ympyrässä, joka odottaa liittymistä toiseen, voi tehdä niin monta silmukkaa kuin haluaa, kunhan viimeiset vaiheet (ts. loput silmukan jälkeen) johtavat itse ympyrän alkuun.
• tämä on hieno !!
• Niille teistä, jotka vielä ette ’ ei ymmärrä miksi x = k * L – y johtaa z = x mod L: ään. Alkaen x = k * L – y — > x = (k – 1) * L + L – y ja nyt voit kertoa, että L – y: n on oltava z. Nyt saat x = (k – 1) * L + z

Sano, että on $ l $ elementit ennen silmukan alkua ja $ n $ elementit silmukassa. Ja $ e_l $ on silmukan ensimmäinen elementti, joka näkyy, kun siirrymme linkitetyn luettelon läpi. Kun sanomme ” elementin $ x $ askelta eteenpäin $ e $ ”, se tarkoittaa, että voimme saavuttaa kyseisen elementin ottamalla $ x $ -vaiheet vaiheesta $ e $ .

Nyt kun Tr (kilpikonna) saavuttaa $ e_l $ , <: n j span class="math-container"> $ l $ iteraatiot, eli Hr (jänis) on $ x $ askelta edellä $ e_l $ . Koska Hr on ottanut siihen mennessä yhteensä $ 2l $ askelta ( $ l $ askelta ennen silmukkaa), joten:

$ x = l \ bmod n $ .

Jokaisessa tulevassa iteraatiossa Tr ja Hr etenevät 1 ja 2 vaihetta, ja siten kukin iterointi kasvattaa ” -vajetta ” yhdellä. Joten he tapaavat $ nx $ lisää iteraatioita, kun niiden välistä tulee $ x + (nx) = n $ . Joten kokouselementti $ M $ on $ nx $ askelta eteenpäin $ e_l $ . Nyt se tarkoittaa, että $ x $ -vaiheiden siirtäminen $ M $ jälkeen tuo meidät jälleen $ e_l $ . Tavoitteenamme on löytää $ e_l $ .

Joten kun aloitamme yhdellä viitteellä Tr $ M $ ja toinen viite Hr linkitetyn luettelon kärjessä ja edetä molempiin yksi askel kerrallaan $ l $ -toiston jälkeen :

• Hr $ l $ askelta eteenpäin, mikä on $ e_l $ .

• Tr on $ (l \ bmod n) $ -vaihe edellä $ M $ , eli $ x $ askelta edellä $ M $ container ”> $ M $ , joka on $ e_l $ .

Siten kun heillä on tapasi, tiedämme, että se on $ e_l $ .

Katso tämä artikkeli yksityiskohtia varten. Sieltä löydät hieman muokatun tavan löytää $ e_l $ .

Löysin vastauksen pinonsiirrosta. Kiitos, jos joku tutki tätä minulle. Ja niille, jotka pidän minusta, halusivat selityksen, katso: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Valittu vastaus kysymykseen selittää se!

Uskon myös, että ylin vastaus on puutteellinen, ja vaikka jotkut muutkin selitykset ovat hyviä, minulla on toinen versio ilman MOD: tä näyttämään saman asian, mikä on ehkä helpompaa joillekin ihmisille.

Samassa asennuksessa pidetään $ X \ ge 0 $ olevan silmukan edellinen etäisyys, $ N \ le \ text {list of size} $ on silmukan koko (määrä $ y + z $ kuvassa) ja kohtaamispaikka on $ Y $ silmukassa. Tässä vaiheessa huomaa, että olemme tehneet myös $ X + Y \ le N $ .

Nyt hidas osoitin kulkee $ X + Y + pN $ , jossa $ p $ on mielivaltainen kokonaisluku. Sitten nopea osoitin kulki $ 2 (X + Y + pN) $ .

Nyt väitä , että he tapaavat $ Y $ .

Todiste :

Jos he tapaavat $ Y $ , sen on oltava että nopeampi osoitin kulki täsmälleen $ qN $ enemmän kuin hitaampi osoitin, jossa $ q $ on kokonaisluku . Sitten meillä on: $$ \ text {etäisyysero =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Mutta $ Y $ oli mielivaltainen kokouspiste silmukassa, joten voimme valita yksinkertaisesti $ X + Y = N $ , joka pitää sisällään $ X + Y \ le N $ .

Siksi meillä on: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ , mikä on totta, jos $ p + 1 = q $ . Koska sekä $ p $ että $ q $ ovat mielivaltaisia kokonaislukuja, voimme vain valita vähimmäisarvon, joten että $ p = 0, q = 1 $ , joka vastaa: $$ \ text {matkan kulku hitaalla osoittimella} = X + Y + pN = X + Y $$ ja $$ \ text {nopean osoittimen kuljettu matka} = (X + Y + pN) + qN = X + Y + N $$ , joten nopea osoitin matkusti ensimmäistä kertaa hitaalla osoittimella täsmälleen $ N $ enemmän.

Kilpikonna ja jänis ovat kaksi osoitinta, jotka alustetaan luettelon ”yläosan” arvolla. Kummassakin silmukan jaksossa jänis kasvaa kahdella lisäyksellä, kun taas kilpikonna kasvaa yhdellä. Jos jänis on jossakin vaiheessa yhtä suuri kuin jänis, on havaittu silmukka. Jos jänis on yhtä suuri kuin loppu, silmukkaa ei löydy.

Tämä viesti selittää sen paremmin rivi kerrallaan:

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29