Почему алгоритм поиска цикла Флойда, черепаха и заяц, должны начинаться в одном и том же месте?C++

Программы на C++. Форум разработчиков
Ответить
Гость
 Почему алгоритм поиска цикла Флойда, черепаха и заяц, должны начинаться в одном и том же месте?

Сообщение Гость »

Я понимаю, почему черепаха и заяц встретятся, если заяц движется со скоростью 2, а черепаха движется со скоростью 1, если существует один цикл. Потому что, если длина цикла равна k, (2-1)*t (расстояние между черепахой и зайцем) в конечном итоге будет делиться на k. Но чего я не понимаю, так это почему, чтобы найти точку входа, черепаха и заяц должны начинать с одного и того же места вначале.
Вот что я реализовал правильно. Но просто изменив начальное условие, поиск точки входа будет зацикливаться навсегда.
if(!head || head->next==nullptr) return nullptr;
ListNode* fast=head->next->next;
ListNode* slow=head->next; // if changing to slow=head or fast=head->next the second loop below will loop forever.
while(fast!=nullptr && fast->next!=nullptr
&& slow!=nullptr && fast!=slow) {
fast = fast->next->next;
slow = slow->next;
}
if(fast!=nullptr && slow!=nullptr && fast==slow) {
slow = head;
while(fast!=slow){
fast = fast->next;
slow = slow->next;
}
return fast;
} else {
return nullptr;
}


Подробнее здесь: https://stackoverflow.com/questions/782 ... o-start-at
Ответить

Быстрый ответ

Изменение регистра текста: 
Смайлики
:) :( :oops: :roll: :wink: :muza: :clever: :sorry: :angel: :read: *x)
Ещё смайлики…
   
К этому ответу прикреплено по крайней мере одно вложение.

Если вы не хотите добавлять вложения, оставьте поля пустыми.

Максимально разрешённый размер вложения: 15 МБ.

Вернуться в «C++»