Regarding Floyd's cycle-finding algorithm

  • #1

Main Question or Discussion Point

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
3
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 for: Regarding Floyd's cycle-finding algorithm

  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
599
  • Last Post
Replies
1
Views
399
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
830
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
727
Top