Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Regarding Floyd's cycle-finding algorithm

  1. Jun 15, 2008 #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.
     
  2. jcsd
  3. Jun 15, 2008 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Suppose that they start M places apart (suitably oriented) on a cycle of size N. How many places apart are they after k steps?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Regarding Floyd's cycle-finding algorithm
  1. Euclidean algorithm (Replies: 2)

  2. EM algorithm (Replies: 0)

  3. Randomized Algorithms (Replies: 2)

Loading...