Saya mengerti bahwa pertemuan Tortoise dan Hare menyimpulkan keberadaan loop, tetapi bagaimana cara memindahkan kura-kura ke awal daftar tertaut sambil menjaga kelinci di tempat pertemuan, diikuti dengan memindahkan kedua langkah sekaligus membuat mereka bertemu di titik awal siklus?
algorithm
linked-list
cycle
floyd-cycle-finding
Pemrogram yang bergairah
sumber
sumber
Jawaban:
Ini adalah algoritma Floyd untuk deteksi siklus . Anda bertanya tentang fase kedua dari algoritma - setelah Anda menemukan simpul yang merupakan bagian dari siklus, bagaimana orang menemukan awal siklus?
Pada bagian pertama dari algoritma Floyd, kelinci menggerakkan dua langkah untuk setiap langkah kura-kura. Jika kura-kura dan kelinci pernah bertemu, ada siklus, dan titik pertemuan adalah bagian dari siklus, tetapi belum tentu simpul pertama dalam siklus.
Ketika kura-kura dan kelinci bertemu, kami telah menemukan i terkecil (jumlah langkah yang diambil oleh kura-kura) sehingga X i = X 2i . Biarkan mu mewakili jumlah langkah untuk mulai dari X 0 ke awal siklus, dan biarkan lambda mewakili panjang siklus. Kemudian i = mu + a lambda, dan 2i = mu + b lambda, di mana a dan b adalah bilangan bulat yang menunjukkan berapa kali kura-kura dan kelinci mengelilingi siklus. Mengurangi persamaan pertama dari yang kedua memberi i = (ba) * lambda, jadi saya adalah kelipatan integer dari lambda. Karena itu, X i + mu = X mu . X i mewakili titik pertemuan kura-kura dan kelinci. Jika Anda memindahkan kura-kura kembali ke simpul awal X0 , dan biarkan kura-kura dan kelinci melanjutkan dengan kecepatan yang sama, setelah langkah-langkah tambahan mu kura-kura akan mencapai X mu , dan kelinci akan mencapai X i + mu = X mu , sehingga titik pertemuan kedua menunjukkan awal dari siklus.
sumber
X_mu
, awal siklus (menurut definisi mu). Kemudian jika Anda mengambil lebih banyak langkah, di mana saya adalah kelipatan dari panjang siklus, Anda berakhir kembali di awal siklus:X_mu + i
=X_mu
. Tetapi penambahan itu bersifat komutatif, jadi ini sama dengan mengambil langkah-langkah untuk memulai dari awal sampai titik pertemuan pertamaX_i
, lalu mengambil langkah-langkah tambahan untuk kembali keX_mu
, awal siklus.i
berada di beberapa titik siklus, saya pikir persamaannya harusi = mu + k + a*lambda
dan2i = mu + k + b*lambda
, di manak
jumlah langkah dari siklus mulai ke titik pertemuan. Mengurangi kedua persamaan memberikan hasil yang sama.Biarkan saya mencoba untuk mengklarifikasi algoritma deteksi siklus yang disediakan di http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare dengan kata-kata saya sendiri.
Bagaimana itu bekerja
Mari kita memiliki kura-kura dan kelinci (nama pointer) yang menunjuk ke awal daftar dengan siklus, seperti pada diagram di atas.
Mari berhipotesis bahwa jika kita memindahkan kura-kura 1 langkah sekaligus, dan membagi 2 langkah sekaligus, mereka akhirnya akan bertemu pada suatu titik. Mari kita tunjukkan bahwa pertama-tama hipotesis ini benar.
Angka tersebut menggambarkan daftar dengan siklus. Siklus memiliki panjang
n
dan kami awalnya beberapam
langkah menjauh dari siklus. Juga katakanlah bahwa titik pertemuan adalah beberapak
langkah menjauh dari siklus awal dan kura-kura dan kelinci bertemu ketika kura-kura telah mengambili
langkah-langkah total. (Kelinci akan mengambil2i
langkah total saat itu.)2 kondisi berikut harus berlaku:
Yang pertama mengatakan bahwa kura-kura bergerak
i
langkah-langkah dan dalami
langkah - langkah ini pertama kali sampai ke siklus. Kemudian ia melewati waktu siklusp
untuk beberapa angka positifp
. Akhirnya melewati lebihk
banyak node sampai bertemu kelinci.Hal serupa juga berlaku untuk kelinci. Ini bergerak
2i
langkah-langkah dan langkah-2i
langkah ini pertama kali sampai ke siklus. Kemudian ia melewati waktu siklusq
untuk beberapa angka positifq
. Akhirnya melewati lebihk
banyak node sampai bertemu kura-kura.Saat kelinci berjalan dengan dua kali lipat kecepatan kura-kura, dan waktu konstan untuk keduanya ketika mereka mencapai titik pertemuan.
Jadi dengan menggunakan hubungan kecepatan, waktu dan jarak yang sederhana,
Di antara m, n, k, p, q, dua yang pertama adalah properti dari daftar yang diberikan. Jika kita dapat menunjukkan bahwa setidaknya ada satu set nilai untuk k, q, p yang membuat persamaan ini benar, kita menunjukkan bahwa hipotesisnya benar.
Satu set solusi tersebut adalah sebagai berikut:
Kami dapat memverifikasi bahwa nilai-nilai ini berfungsi sebagai berikut:
Untuk set ini,
i
adalahTentu saja, Anda harus melihat bahwa ini belum tentu yang terkecil yang saya bisa. Dengan kata lain, kura-kura dan kelinci mungkin sudah pernah bertemu sebelumnya. Namun, karena kami menunjukkan bahwa mereka bertemu di beberapa titik setidaknya sekali kita dapat mengatakan bahwa hipotesis itu benar. Jadi mereka harus bertemu jika kita memindahkan salah satu dari mereka 1 langkah, dan yang lainnya 2 langkah sekaligus.
Sekarang kita bisa menuju ke bagian kedua dari algoritma yang adalah bagaimana menemukan awal siklus.
Awal Siklus
Setelah kura-kura dan kelinci bertemu, mari kita meletakkan kura-kura kembali ke awal daftar dan simpan kelinci di tempat mereka bertemu (yang berjarak beberapa langkah dari siklus awal).
Hipotesisnya adalah jika kita membiarkan mereka bergerak dengan kecepatan yang sama (1 langkah untuk keduanya), pertama kali mereka bertemu lagi adalah siklusnya.
Mari kita buktikan hipotesis ini.
Pertama-tama mari kita asumsikan beberapa oracle memberi tahu kita apa itu m.
Kemudian, jika kita membiarkan mereka bergerak m + k langkah, kura-kura harus tiba pada titik yang mereka temui semula (k langkah menjauh dari siklus awal - lihat pada gambar).
Sebelumnya kami menunjukkan itu
m + k = (q - 2p) n
.Karena langkah m + k adalah kelipatan dari panjang siklus n, kelinci, pada saat yang bersamaan, akan melewati siklus (q-2p) kali dan akan kembali ke titik yang sama (k langkah menjauh dari awal siklus).
Sekarang, alih-alih membiarkan mereka bergerak langkah m + k, jika kita membiarkan mereka bergerak hanya langkah m, kura-kura akan tiba di awal siklus. Kelinci akan menjadi k langkah-langkah pendek menyelesaikan rotasi (q-2p). Karena itu dimulai k langkah di depan siklus awal, kelinci harus tiba di siklus awal.
Akibatnya, ini menjelaskan bahwa mereka harus bertemu di siklus dimulai setelah beberapa langkah untuk pertama kalinya (sangat pertama karena kura-kura baru saja tiba di siklus setelah langkah m dan tidak pernah bisa melihat kelinci yang sudah ada di siklus).
Sekarang kita tahu bahwa jumlah langkah yang kita butuhkan untuk memindahkannya sampai bertemu ternyata menjadi jarak dari awal daftar ke awal siklus, m. Tentu saja, algoritma tidak perlu tahu apa itu m. Itu hanya akan memindahkan kedua kura-kura dan berbagi satu langkah pada satu waktu sampai mereka bertemu. Titik pertemuan harus menjadi awal siklus dan jumlah langkah harus jarak (m) ke awal siklus. Dengan asumsi kita tahu panjang daftar, kita juga bisa, menghitung panjang siklus pengurangan m dari panjang daftar.
sumber
m + k = (q - 2p) n
dapat lebih disederhanakan menjadim + k = q*n
. Ini karena jumlah loop yang diambil kura-kura akan selalu nol karena kelinci tidak pernah bisa menyalip kura-kura tanpa memenuhi itu. Pikirkan tentang itu.Rujuk gambar ini:
Jarak yang ditempuh oleh slowPointer sebelum pertemuan = x + y
Jarak yang ditempuh oleh fastPointer sebelum pertemuan = (x + y + z) + y = x + 2y + z
Karena fastPointer bergerak dengan dua kali lipat kecepatan slowPointer, dan waktu adalah konstan untuk keduanya ketika mencapai titik pertemuan.
Jadi dengan menggunakan hubungan kecepatan, waktu dan jarak yang sederhana 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
Oleh karena itu dengan menggerakkan slowPointer untuk memulai daftar tertaut, dan membuat slowPointer dan fastPointer untuk memindahkan satu node pada satu waktu, keduanya memiliki jarak yang sama untuk dibahas .
Mereka akan mencapai pada titik di mana loop dimulai pada daftar yang ditautkan.
sumber
Jawaban Old Monk yang sederhana dan kurang diselidiki menjelaskan menemukan siklus ketika pelari cepat hanya menyelesaikan satu siklus penuh. Dalam jawaban ini saya menjelaskan kasus ketika pelari cepat telah menjalankan loop beberapa kali sebelum pelari lambat memasuki loop.
Menggunakan gambar yang sama:
Katakanlah pelari cepat telah menjalankan loop m kali sebelum bertemu lambat dan cepat. Ini berarti:
Karena berlari cepat dengan kecepatan dua kali lipat lambat, dan bahwa mereka telah berlari untuk waktu yang sama, itu menyiratkan bahwa jika kita menggandakan jarak berlari dengan lambat, kita mendapatkan jarak berlari dengan cepat. Jadi,
Memecahkan untuk x memberi,
Dalam skenario nyata itu berarti, x = (m - 1) loop lengkap berjalan + jarak ekstra z .
Oleh karena itu, jika kita meletakkan satu pointer di awal daftar dan meninggalkan yang lain di titik pertemuan, kemudian memindahkannya dengan kecepatan yang sama akan menghasilkan pointer loop menyelesaikan m - 1 putaran dan kemudian bertemu dengan lainnya arahkan tepat di awal loop.
sumber
Ini sangat sangat sederhana. Anda dapat berpikir dalam hal kecepatan relatif. Jika kelinci bergerak dua node dan kura-kura bergerak satu simpul, relatif terhadap kura-kura kelinci bergerak satu simpul (asumsikan kura-kura saat istirahat). Jadi, jika kita memindahkan satu simpul dalam daftar tertaut melingkar, kita yakin akan bertemu lagi di titik itu.
Setelah menemukan titik yang terhubung di dalam daftar tertaut melingkar, sekarang masalahnya dikurangi menjadi menemukan titik persimpangan dua masalah daftar tertaut.
sumber
Pada saat tabrakan pertama, kura-kura memindahkan langkah m + k seperti yang ditunjukkan di atas. Kelinci bergerak dua kali lebih cepat dari kura-kura, artinya kelinci bergerak 2 (m + k) langkah. Dari fakta-fakta sederhana ini kita dapat memperoleh grafik berikut.
Pada titik ini, kami memindahkan kura-kura kembali ke awal dan menyatakan bahwa kelinci dan kura-kura harus bergerak selangkah demi selangkah. Menurut definisi, setelah langkah m , kura-kura akan berada di awal siklus. Di mana hare akan berada?
Kelinci juga akan berada di awal siklus. Hal ini jelas dari grafik kedua: Ketika kura-kura dipindahkan kembali ke awal, kelinci adalah k langkah ke siklus terakhir. Setelah langkah m , kelinci akan menyelesaikan siklus lain dan bertabrakan dengan kura-kura.
sumber
Pendekatan:
Ada dua petunjuk:
Jika kedua penunjuk bertemu, itu membuktikan bahwa ada loop. Setelah mereka bertemu, salah satu simpul akan menunjuk ke kepala dan kemudian keduanya melanjutkan satu simpul pada satu waktu. Mereka akan bertemu di awal perulangan.
Dasar Pemikiran: Ketika dua orang berjalan di jalur yang melingkar, salah satunya dengan kecepatan dua kali lipat, di mana mereka bertemu? Persis di mana mereka mulai.
Sekarang, misalkan pelari cepat memiliki
k
langkahn
awal di putaran langkah. dimana mereka akan bertemu? Tepat padan-k
langkah-langkah. Ketika pelari lambat telah membahas(n-k)
langkah - langkah, pelari cepat akan membahask+2(n-k)
langkah - langkah. ( Yaitu,k+2n-2k
langkah yaitu2n-k
langkah ). yaitu(n-k)
langkah-langkah (Jalannya melingkar dan kami tidak peduli tentang jumlah putaran setelah mereka bertemu; Kami hanya tertarik pada posisi di mana mereka bertemu).Sekarang bagaimana pelari cepat mendapatkan
k
langkah awal di tempat pertama? Karena butuh pelari lambat sehingga banyak langkah untuk mencapai awal loop. Jadi awal dari loop adalah k langkah dari simpul kepala.Catatan: Node tempat kedua penunjuk bertemu berjarak beberapa
k
langkah dari awal lingkaran (di dalam lingkaran) dan simpul kepala juga berjarak beberapak
langkah dari awal putaran. Jadi ketika kita memiliki pointer yang maju pada kecepatan yang sama dengan 1 langkah dari bot node ini, mereka akan bertemu pada awal loop.Saya percaya ini mudah. Tolong beri tahu saya jika ada bagian yang ambigu.
sumber
Oke jadi mari kita asumsikan kelinci dan kura-kura bertemu pada titik yang k langkah menjauh dari awal siklus, jumlah langkah sebelum siklus dimulai adalah mu dan panjang siklus adalah L.
Jadi sekarang di titik pertemuan ->
Jarak yang dicakup oleh kura-kura = mu + a * L + k - Persamaan 1
(Langkah-langkah yang diambil untuk mencapai awal siklus + langkah-langkah yang diambil untuk membahas iterasi siklus 'a' dari awal siklus) (di mana a adalah konstanta positif)
Jarak yang dicakup oleh kelinci = mu + b * L + k - Persamaan 2
(Langkah-langkah yang diambil untuk mencapai awal siklus + langkah-langkah yang diambil untuk mencakup iterasi 'b' dari siklus + k langkah-langkah dari awal siklus) (di mana b adalah konstanta positif dan b> = a)
Jadi jarak ekstra yang dicakup oleh kelinci adalah = Persamaan 2 - Persamaan 1 = (ba) * L
Harap dicatat bahwa jarak ini juga sama dengan jarak kura-kura dari titik awal karena kelinci bergerak 2 kali lebih cepat daripada kura-kura. Ini dapat disamakan dengan 'mu + k' yang juga merupakan jarak dari titik pertemuan dari awal jika kita tidak menyertakan banyak lintasan lintas siklus.
Dengan demikian, mu + k = (ba) * L
Jadi langkah mu dari titik ini akan mengarah kembali ke awal siklus (karena langkah k dari awal siklus telah diambil untuk mencapai titik pertemuan). Ini bisa terjadi dalam siklus yang sama atau siklus berikutnya. Jadi sekarang jika kita memindahkan kura-kura ke awal daftar terkait, itu akan mengambil langkah mu untuk mencapai titik awal siklus dan kelinci akan mengambil langkah mu untuk juga mencapai awal siklus dan dengan demikian mereka berdua akan bertemu di titik awal siklus.
PS Jujur, saya memiliki pertanyaan yang sama dengan poster asli di pikiran saya dan saya membaca jawaban pertama, mereka benar-benar membersihkan beberapa hal tetapi saya tidak dapat mencapai hasil akhir dengan jelas sehingga saya mencoba melakukannya dengan cara saya sendiri dan merasa lebih mudah dimengerti.
sumber
kredit gambar
Panggilan jarak jumlah link yang diikuti oleh pointer, dan waktu jumlah iterasi algoritma yang dibutuhkan untuk memindahkan pointer lambat satu link dan pointer cepat dua link. Ada N node sebelum siklus panjang C, diberi label dengan siklus offset k = 0 hingga C-1.
Untuk mencapai awal siklus, lambat membutuhkan waktu dan jarak N. Ini berarti cepat mengambil jarak N dalam siklus (N untuk sampai di sana, N untuk berputar). Jadi pada waktu N, lambat pada siklus offset k = 0, dan cepat pada siklus offset k = N mod C.
Jika N mod C nol, lambat dan cepat sekarang cocok dan siklus ditemukan pada waktu N dan posisi siklus k = 0.
Jika N mod C bukan nol, maka fast sekarang harus mengejar ketinggalan dengan lambat, yang pada saat N adalah C- (N mod C) jarak di belakang dalam siklus.
Karena gerakan cepat 2 untuk setiap 1 lambat, mengurangi jarak oleh 1 pada setiap iterasi, ini membutuhkan waktu tambahan sebanyak jarak antara cepat dan lambat pada waktu N, yaitu C- (N mod C). Karena lambat bergerak dari offset 0, ini juga merupakan offset tempat mereka bertemu.
Jadi, jika N mod C adalah nol, fase 1 berhenti setelah iterasi N pada awal siklus. Jika tidak, fase 1 berhenti setelah iterasi N + C- (N mod C) pada offset C- (N mod C) ke dalam siklus.
Ok, jadi fase 2: lambat mengambil N langkah lebih lanjut untuk sampai ke siklus, di mana titik cepat (sekarang bergerak 1 per langkah waktu) berada di (C- (N mod C) + N) mod C = 0. Jadi mereka bertemu di awal siklus setelah fase 2.
Untuk kelengkapan, fase 3 menghitung panjang siklus dengan bergerak sekali lagi melalui siklus:
sumber
Kurangi masalah menjadi masalah berulang, lalu kembali ke masalah awal
Saya menemukan penjelasan berikut ini lebih intuitif.
Ambil dua petunjuk ( 1 = kura-kura dan 2 = kelinci) yang dimulai dari kepala ( O ), 1 memiliki panjang langkah 1 , 2 memiliki panjang langkah 2 . Pikirkan saat ketika 1 mencapai simpul awal dari siklus itu ( A ).
Kami ingin menjawab pertanyaan berikut "Di mana 2 ketika 1 berada di A?" .
Jadi,
OA = a
adalah bilangan alami (a >= 0
). Tetapi dapat ditulis dengan cara berikut:, dia = k*n + b
manaa, k, n, b are natural numbers
:n
= panjang siklusk >= 0
= konstan0 <= b <= n-1
Itu artinya
b = a % n
.Misalnya: jika
a = 20
dann = 8
=>k = 2
danb = 4
karena20 = 2*8 + 4
.Jarak yang dicakup oleh 1 adalah
d = OA = a = k*n + b
. Tetapi pada saat yang sama, 2 mencakupD = 2*d = d + d = OA + d = OA + k*n + b
. Ini berarti bahwa ketika 2 berada di A ia harus menutupk*n + b
. Seperti yang Anda lihat,k
adalah jumlah lap, tapi setelah mereka lap, 2 akan b jauh dari A. Jadi, kami menemukan di mana 2 adalah ketika 1 adalah di A. Mari panggilan titikB
, di manaAB = b
.Sekarang, kami mengurangi masalah menjadi lingkaran. Pertanyaannya adalah "Di mana titik pertemuannya?" . Di mana C itu ?
Dalam setiap langkah, 2 mengurangi jarak dari 1 dengan
1
(katakanlah meter) karena 1 semakin jauh dari 2 dengan1
, tetapi pada saat yang sama 2 semakin mendekati 1 oleh2
.Jadi, persimpangan akan menjadi ketika jarak antara 1 dan 2 akan menjadi nol. Ini berarti bahwa 2 mengurangi
n - b
jarak. Untuk mencapai ini, 1 akan membuatn - b
langkah, sedangkan 2 akan membuat2*(n - b)
langkah.Jadi, titik persimpangan akan
n - b
jauh dari A (searah jarum jam), karena ini adalah jarak yang dicakup oleh 1 hingga bertemu 2 . => jarak antara C dan A adalahCA = b
, karenaAC = AB + BC = n - b
danCA = n - AC
. Jangan berpikir bahwaAC = CA
, karenaAC
jarak itu bukan jarak matematis sepele, ini adalah jumlah langkah antara A dan C (di mana A adalah titik awal dan C adalah titik akhir).Sekarang, mari kita kembali ke skema awal.
Kami tahu itu
a = k*n + b
danCA = b
.Kita dapat mengambil 2 pointer baru 1 ' dan 1' ' , di mana 1' dimulai dari kepala ( O ) dan 1 '' mulai dari titik persimpangan ( C ).
Sementara 1 ' pergi dari O ke A , 1' ' pergi dari C ke A dan terus menyelesaikan
k
putaran. Jadi, titik persimpangan adalah A .sumber
Jika pointer bertemu pada titik P seperti yang ditunjukkan pada gambar, jarak Z + Y adalah titik P dan X + Y juga merupakan titik P yang berarti Z = X. Itulah sebabnya menjaga memindahkan satu pointer dari P dan memindahkan yang lain dari awal (S) hingga mereka bertemu, yang berarti memindahkan jarak yang sama (Z atau X) ke titik yang sama M (jarak Z dari P dan X dari S) akan menjadi mulai dari loop. Sederhana!
sumber
Dengan semua analisis di atas, jika Anda adalah orang yang belajar melalui contoh, saya mencoba untuk menulis analisis singkat dan contoh yang membantu menjelaskan matematika yang orang lain coba jelaskan. Kita mulai!
Analisis:
Jika kita memiliki dua pointer, satu lebih cepat dari yang lain, dan memindahkannya bersama, mereka akhirnya akan bertemu lagi untuk menunjukkan siklus atau nol untuk menunjukkan tidak ada siklus.
Untuk menemukan titik awal siklus, biarkan ...
m
menjadi jarak dari kepala ke awal siklus;d
menjadi jumlah node dalam siklus;p1
menjadi kecepatan dari pointer yang lebih lambat;p2
menjadi kecepatan penunjuk yang lebih cepat, mis. 2 berarti langkah melalui dua node sekaligus.Perhatikan iterasi berikut:
Dari data sampel di atas, kita dapat dengan mudah menemukan bahwa kapan pun pointer yang lebih cepat dan lebih lambat bertemu, mereka berada beberapa
m
langkah dari awal siklus. Untuk mengatasi ini, letakkan penunjuk yang lebih cepat kembali di kepala dan atur kecepatannya ke kecepatan penunjuk yang lebih lambat. Ketika mereka bertemu lagi, simpul adalah awal dari siklus.sumber
Katakanlah,
kami memiliki 2 pointer A dan B, A berjalan pada kecepatan 1x, B pada kecepatan 2x, keduanya dimulai dari awal.
ketika A mencapai N [0], B seharusnya sudah dalam N [m]. (Catatan: A menggunakan langkah m untuk mencapai N [0], dan B harus langkah m lebih lanjut)
Kemudian, A menjalankan k lebih banyak langkah untuk bertabrakan dengan B, yaitu A berada di N [k], B berada di N [m + 2k] (Catatan: B harus menjalankan langkah 2k mulai dari N [m])
A bertabrakan B pada N [k] dan N [m + 2k], artinya k = m + 2k, sehingga k = -m
Jadi, untuk kembali ke N [0] dari N [k], kita perlu lebih banyak langkah.
Cukup dengan mengatakan, kita hanya perlu menjalankan lebih banyak langkah setelah kita menemukan node collision. Kita dapat memiliki pointer untuk dijalankan dari awal dan pointer berjalan dari collision node, mereka akan bertemu di N [0] setelah langkah m.
Oleh karena itu, kode pseudo adalah sebagai berikut:
sumber
Saya tidak berpikir begitu benar bahwa ketika mereka bertemu itu adalah titik awal. Tapi ya jika pointer lainnya (F) berada di titik pertemuan sebelumnya, maka pointer tersebut akan berada di akhir loop, bukan di awal loop dan pointer (S) yang dimulai dari awal daftar itu akan berakhir di awal loop. untuk misalnya:
sumber
Penjelasan sederhana menggunakan gagasan kecepatan relatif yang diajarkan di sekolah menengah - Fisika 101 / Kinematika kuliah.
Mari kita asumsikan jarak dari awal daftar tertaut ke mulai dari lingkaran adalah
x
hop. Mari kita sebut awal lingkaran sebagai titikX
(dalam huruf besar - lihat gambar di atas). Juga mari kita asumsikan ukuran lingkaran adalah N hop.Kecepatan kelinci = 2 * Kecepatan kura-kura. Jadi itu
1 hops/sec
dan2 hops/sec
masing - masingKetika kura-kura mencapai awal lingkaran
X
, kelinci harusx
melompat jauh pada titikY
dalam gambar. (Karena kelinci telah menempuh jarak dua kali lipat dari kura-kura).Dengan demikian, panjang busur yang tersisa searah jarum jam dari X ke Y adalah
N-x
. Ini juga merupakan jarak relatif yang harus ditempuh antara kelinci dan kura-kura agar mereka dapat bertemu . Katakanlah jarak relatif ini akan dibahas dalam waktut_m
yaitu waktu untuk bertemu. Kecepatan relatif(2 hops/sec - 1 hops/sec)
yaitu1 hops/sec
. Dengan menggunakan, jarak relatif = kecepatan relatif X waktu, kita dapatkan,t
=N-x
dtk. Jadi akan dibutuhkanN-x
untuk mencapai titik pertemuan untuk kura-kura dan kelinci.Sekarang dalam
N-x
detik dan dengan1 hops/sec
kecepatan, kura-kura yang sebelumnya pada titikX
akan mencakup Nx hop untuk mencapai titik pertemuanM
. Jadi, itu berarti titik pertemuanM
berada diN-x
berlawanan berlawanan arah jarum jam dariX
= (yang selanjutnya menyiratkan) => bahwa adax
jarak yang tersisa dari titikM
keX
arah jarum jam.Tetapi
x
juga jarak untuk mencapai titikX
dari awal daftar tertaut.Sekarang, kami tidak peduli dengan jumlah hop yang
x
sesuai. Jika kita meletakkan satu kura-kura di awal LinkedList dan satu kura-kura di titik pertemuanM
dan membiarkan mereka melompat / berjalan, maka mereka akan bertemu di titikX
, yang merupakan titik (atau simpul) yang kita butuhkan.sumber
Mengerjakan ini dengan diagram akan membantu. Saya mencoba menjelaskan masalah tanpa persamaan.
sumber
-ada langkah k sebelum loop. Kami tidak tahu apa itu k dan tidak perlu mencari tahu. Kita dapat bekerja secara abstrak hanya dengan k.
--Setelah k langkah
----- T pada awal siklus
----- H adalah k langkah ke dalam siklus (dia pergi total 2k dan dengan demikian k ke loop)
** mereka sekarang melenggang - k terpisah
(catat bahwa k == K == mod (loopsize, k) --eg jika sebuah simpul 2 langkah ke dalam siklus 5 simpul juga 7, 12 atau 392 langkah masuk, jadi seberapa besar siklusnya, k tidak faktor dalam.
Karena mereka mengejar satu sama lain dengan kecepatan 1 langkah per unit waktu karena satu bergerak dua kali lebih cepat daripada yang lain, mereka akan bertemu di loopsize - k.
Ini berarti akan membutuhkan k node untuk mencapai awal siklus dan dengan demikian jarak dari head ke cyclestart dan collision ke cyclestart adalah sama.
Jadi sekarang setelah tabrakan pertama pindah T kembali ke kepala. T dan H akan bertemu di cyclestart jika Anda bergerak dengan laju masing-masing 1. (dalam langkah k untuk keduanya)
Ini berarti bahwa algoritma tersebut adalah:
// atasi case ketika k = 0 atau T dan H bertemu di bagian atas loop dengan menghitung panjang loop
--hitung panjang siklus dengan menggerakkan T atau H di sekitarnya dengan penghitung
--memindahkan pointer T2 ke kepala daftar
--memindahkan panjang pointer langkah-langkah siklus
--move pointer H2 lainnya ke kepala
- Pindahkan T2 dan H2 bersama-sama sampai mereka bertemu di awal siklus
itu dia!
sumber
Sudah ada banyak jawaban untuk ini, tetapi saya pernah membuat diagram untuk ini yang lebih intuitif secara visual bagi saya. Mungkin itu bisa membantu orang lain.
Aha-momen utama bagi saya adalah:
Membagi T (kura-kura) menjadi T1 (pre-loop) dan T2 (in-loop).
Kurangi T dari H , di mana mereka tumpang tindih secara visual. Apa yang tetap ( H - T = H' ) sama dengan T .
sumber
Saya tahu sudah ada jawaban yang diterima untuk masalah ini, tetapi saya akan tetap mencoba menjawab dengan lancar. Menganggap :
Sekarang, biarkan kelinci dan kura-kura bertemu setelah waktu 't' dari awal.
Pengamatan:
Jika, Jarak yang ditempuh oleh kura-kura = v * t = x + (bk) (katakanlah)
Kemudian, Jarak yang ditempuh oleh kelinci = 2 * v * t = x + (b - k) + b (karena kelinci telah melewati bagian yang dililitkan sekali)
Sekarang, waktu pertemuan di sana sama.
=> x + 2 * b - k = 2 * (x + b - k)
=> x = k
Ini tentu saja berarti bahwa panjang jalur yang tidak dilingkarkan sama dengan jarak dari titik awal loop dari titik di mana keduanya bertemu.
sumber
Sebenarnya mudah untuk membuktikan bahwa mereka berdua akan bertemu di titik awal, jika Anda mempertimbangkan matematika di belakang titik pertemuan.
Pertama biarkan m menunjukkan titik awal siklus dalam daftar yang ditautkan, dan n menunjukkan panjang siklus. Kemudian agar kelinci dan kura-kura bertemu, kita memiliki:
Menyatakan ini secara lebih matematis:
sehingga mereka akan bertemu pada waktu t yang seharusnya merupakan kelipatan dari panjang siklus. Ini berarti bahwa mereka bertemu di suatu lokasi, yaitu
(t-m) modulo n = (0-m) modulo n = (-m) modulo n
.Jadi sekarang kembali ke pertanyaan, jika Anda memindahkan satu pointer dari awal daftar tertaut, dan satu lagi dari titik persimpangan, setelah langkah m kita akan memiliki kelinci (yang bergerak di dalam siklus) datang ke titik yang
((-m) + m) modulo n = 0 modulo n
yang tidak lain adalah titik awal dari siklus. Jadi kita dapat melihat bahwa setelah m langkah-langkah datang ke awal siklus dan kura-kura akan bertemu di sana karena akan melintasi m langkah-langkah dari awal daftar terkait.Sebagai catatan tambahan, kita juga dapat menghitung waktu persimpangan mereka dengan cara ini: Kondisi
t = 0 modulo n
memberi tahu kita bahwa mereka akan bertemu pada waktu yang merupakan kelipatan dari panjang siklus, dan juga t harus lebih besar dari m seperti yang akan mereka temui di siklus. Jadi waktu yang diambil akan sama dengan kelipatan pertama dari n yang lebih besar dari m .sumber
Misalkan pointer Anda bertemu di persimpangan titik y dan z.
n dan m adalah jumlah loop yang lebih cepat dan pointer yang lebih lambat masing-masing dibutuhkan sebelum pertemuan.
Lihat gambar untuk sisa buktinya. Temukan titik awal loop dalam daftar tertaut
sumber