Интуиция позади алгоритма Черепаха и Заяц - PullRequest
0 голосов
/ 12 февраля 2020

Я могу написать код, используя алгоритм Черепаха и Заяц, и он работает. Но это не имеет смысла для меня. Такое ощущение, что он может сломаться для правильной длины цикла и размера шага зайца.

Существуют ли альтернативные объяснения, которые помогут мне понять?

1 Ответ

0 голосов
/ 12 февраля 2020

Если есть цикл, вы можете думать о нем как о бесконечно повторяющейся числовой строке.

В начале алгоритма Черепаха и Заяц мы помещаем зайца на один узел впереди черепахи. Но как только они входят в цикл, вы можете подумать о том, что заяц находится позади черепахи.

Типичными шагами для черепахи и зайца являются 1 и 2 соответственно. И независимо от того, насколько далеко позади зайца, он сокращается до двух вариантов - 1 шаг назад или 2 шага назад.

Если заяц находится на 1 шаг назад, он встретится с черепахой на следующем шаге , Черепаха двигается 1, Заяц двигается 2.

Если заяц на 2 шага назад, черепаха будет двигаться вперед 1, а заяц будет двигаться вперед 2. Теперь заяц находится всего в одном шаге назад, и они Мы встретимся на следующем шаге.

Для меня это имеет смысл, и кажется, что это обобщает любой шаг, который делает заяц. Ключевым моментом для меня было изменение моего ментального подхода с цикла на бесконечную, повторяющуюся числовую линию.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...