Regarding Floyd's cycle-finding algorithm

  • #1
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.
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
4
Suppose that they start M places apart (suitably oriented) on a cycle of size N. How many places apart are they after k steps?
 

Related Threads on Regarding Floyd's cycle-finding algorithm

  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
692
  • Last Post
Replies
1
Views
485
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
934
  • Last Post
Replies
4
Views
838
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
175
  • Last Post
2
Replies
26
Views
19K
Top