Phát hiện chu trình
Các thuật toán > Thuật toán rùa và thỏ của Floyd

Thuật toán tìm chu trình của Floyd là thuật toán con trỏ dùng hai con trỏ, di chuyển trên cùng một chuỗi với tốc độ khác nhau. Nó cũng được gọi là "thuật toán rùa và thỏ", dựa trên câu chuyện ngụ ngôn của Aesop.
Thuật toán được đặt tên theo Robert W. Floyd, người được công nhận bởi Donald Knuth. Tuy nhiên, thuật toán không xuất hiện trong các bài của Floyd, và do đó đây có thể là quy kết nhầm: Floyd mô tả các thuật toán liệt kê toàn bộ các chu trình đơn trong một đồ thị có hướng trong tờ nghiên cứu năm 1967, nhưng tờ báo đó không mô tả bài toán tìm chu trình với đồ thị hàm ở đây. Thậm chí, theo lời của Knuth (vào năm 1969), quy nó về Floyd mà không trích dẫn.
Yếu tố quan trọng trong thuật toán như sau. Nếu có một chu trình, thì, với bất kỳ i ≥ μ và k ≥ 0, xi = xi + kλ, với λ là độ dài vòng lặp cần tìm và μ là vị trí của phần tử đầu tiên trong chu trình. Dựa trên đây, ta có thể chứng minh i = kλ ≥ μ với một vài số k khi và chỉ khi xi = x2i. Như vậy, thuật toán chỉ cần kiểm tra các giá trị lặp lại dưới dạng đặc biệt trên, với một con trỏ để cách gấp đôi từ vị trí xuất phát, để tìm chu kỳ ν cho một lần lặp là bội của λ. Một khi ν được tìm thấy, thuật toán tìm ngược lại từ lúc ban đầu để tìm giá trị đầu tiên xμ trong chuỗi, khi biết rằng λ là ước của ν và do đó xμ = xμ + v.  Cuối cùng, một khi μ đã được biết, bài toán trở nên đơn giản trong việc tìm độ dài λ cho chu trình lặp lại ngắn nhất, bằng việc tìm vị trí đầu tiên của μ + λ sao cho xμ + λ = xμ.
Thuật toán do đó dùng hai con trỏ, con trỏ đầu tiên (con rùa) nằm tại xi, và con còn lại (con trỏ) nằm tại x2i. Trong mỗi bước của thuật toán, tăng i bởi một, di chuyển con rùa một bước phía trước và con thỏ hai bước phía trước trong chuỗi, rồi so sánh giá trị chuỗi ở hai con trỏ này. Giá trị nhỏ nhất của i > 0 sao cho rùa và thỏ đều trỏ vào cùng một giá trị là giá trị ν cần tìm.
Đoạn code Python sau mô tả ý tưởng thuật toán trên:
def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu
Thuật toán chỉ dùng con trỏ để lưu và sao chép giá trị, tính giá trị hàm và kiểm tra bằng nhau, do đó nó thỏa mãn yêu cầu của thuật toán con trỏ.Thuật toán dùng O(λ + μ) số phép tính trên, và O(1) bộ nhớ.