Phát hiện chu kỳ trong danh sách được liên kết: Lý thuyết phơi sáng

Question

Đây KHÔNG phải là vấn đề về phát hiện chu trình trong danh sách được liên kết bằng phương pháp Hare và Tortoise của famous.

Trong phương pháp Rùa & Rùa, chúng tôi có con trỏ chạy ở tốc độ 1x và 2x để xác định rằng chúng đáp ứng và tôi tin rằng cách hiệu quả nhất và thứ tự của loại tìm kiếm đó là O (n).

Vấn đề là tôi phải đưa ra một bằng chứng (chứng minh hoặc disproving) rằng có thể hai con trỏ sẽ luôn luôn đáp ứng khi tốc độ di chuyển là Ax (A lần x) và Bx (B lần x) và A không bằng B. Trong trường hợp A a B là hai số nguyên ngẫu nhiên hoạt động trên một danh sách liên kết với một chu trình hiện tại.

Điều này đã được hỏi trong một cuộc phỏng vấn mà gần đây tôi đã tham dự và tôi không thể chứng minh điều đó một cách toàn diện cho chính mình rằng liệu điều trên có thể thực hiện được hay không. Bất kỳ trợ giúp nào được đánh giá cao.

Answer 1

Giả sử có vòng lặp, có chiều dài là L.

Dễ trường hợp đầu tiên

Để làm cho nó dễ dàng hơn, đầu tiên xem xét các trường hợp hai hạt toàn bộ vòng lặp cùng một lúc. Những hạt này ở cùng một vị trí bất cứ khi nào n*A = n*B (mod L) đối với một số số nguyên dương n, là số bước cho đến khi chúng gặp lại nhau. Lấy n=L cho một giải pháp (mặc dù có thể có một giải pháp nhỏ hơn). Vì vậy, sau khi L đơn vị thời gian, hạt A đã thực hiện A các chuyến đi vòng quanh để quay lại lúc bắt đầu và hạt B đã thực hiện các chuyến đi vòng quanh để bắt đầu, nơi chúng vui vẻ va chạm.

chung Trường hợp

Bây giờ những gì sẽ xảy ra khi họ không nhập vòng lặp cùng một lúc? Gọi A là hạt chậm hơn, tức là A<B và giả sử A nhập vòng lặp tại thời điểm m và gọi vị trí tại đó A nhập vòng lặp 0 (vì chúng ở trong vòng lặp, chúng không bao giờ có thể rời khỏi nó, vì vậy tôi ' m chỉ đổi tên vị trí bằng cách trừ A*m, khoảng cách A đã di chuyển sau m đơn vị thời gian).Sau đó, tại thời điểm đó, B đã ở vị trí m*(B-A) (vị trí thực của nó sau m đơn vị thời gian là B*m và do đó vị trí được đổi tên là B*m-A*m). Sau đó, chúng tôi cần hiển thị rằng có một thời gian n sao cho n*A = n*B+m*(B-A) (mod L). Đó là, chúng ta cần một giải pháp cho phương trình mô-đun

(n+m) * (A-B) = 0 (mod L) 

Lấy n = k*L-m cho k đủ rằng k*L>m hiện các trick lớn, mặc dù một lần nữa, có thể là một giải pháp nhỏ hơn.

Vì vậy, vâng, họ luôn gặp nhau.

Answer 2

Nếu hai kích thước bước của bạn có một yếu tố chung x: hãy nói kích thước bước là Ax và Bx, sau đó chỉ xem xét chuỗi bạn nhận được từ việc lấy chuỗi gốc và lấy mọi phần tử x'th. Trình tự mới này có chu kỳ nếu và chỉ khi chuỗi gốc thực hiện, và thực hiện các bước có kích thước A và B trên nó tương đương với việc thực hiện các bước có kích thước Ax và Bx trên trình tự ban đầu.

Mức giảm này có nghĩa là đủ để chứng minh rằng thuật toán hoạt động khi A và B là đồng thời.

Answer 3

Giả thuyết là sai. Ví dụ, nếu cả hai con trỏ làm cho bước nhảy vọt của một kích thước thậm chí, vòng lặp cũng có kích thước thậm chí, và khoảng cách giữa các con trỏ là lẻ, chúng sẽ không bao giờ gặp nhau.

UPD đây rõ ràng là một tình huống không thể xảy ra. Bởi vì hai con trỏ bắt đầu tại cùng một điểm, khoảng cách giữa chúng sẽ luôn luôn là ngay cả.