Regarding Floyd's cycle-finding algorithm

  • Thread starter Thread starter cyberfrenzy
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
Floyd's cycle-finding algorithm involves two pointers, the tortoise and the hare, moving at different speeds to detect cycles in a sequence. When starting M places apart on a cycle of size N, the distance between the two after k steps can be expressed mathematically. The tortoise moves one step per iteration, while the hare moves two steps, leading to a predictable pattern of their positions. The key is to analyze their relative positions modulo N to determine when they will coincide. A mathematical proof can be constructed to show that they will eventually meet regardless of their initial separation.
cyberfrenzy
Messages
3
Reaction score
0
Well I understand what is happening - the tortoise moving 1 step, and the hare moving 2 steps and finally coinciding at a point. But I want a mathematical proof of this - ie; when you have 2 counters moving in a cycle, one going 1 step, the other 2 steps, then they finally meet at a point.
 
Physics news on Phys.org
Suppose that they start M places apart (suitably oriented) on a cycle of size N. How many places apart are they after k steps?
 

Similar threads

Chemistry How do we interpret the steps in the algorithm to balance a redox equation?
Replies
7
Views
2K
I Runge-Kutta 4 w/ some sugar on the top: How to do error approximation?
2
Replies
65
Views
7K
MHB What are the best algorithms for solving a TSP with 6 points?
Replies
2
Views
2K
I Gradient descent algorithm and optimizers
Replies
5
Views
2K
Non youtube courses and paid textbooks to learn algorithms?
Replies
8
Views
3K
Chemistry How does it work to mix two gases reversibly in this device?
Replies
1
Views
2K
MHB Algorithm to answer existential questions - Reduction
Replies
1
Views
2K
Chemistry A few questions on an irreversible adiabatic expansion of an ideal gas
Replies
1
Views
2K
Some questions on strange things in online courses
Replies
10
Views
2K
I Proof of the Halting Problem's Unsolvability
Replies
16
Views
3K

Hot Threads

Recent Insights

Back
Top