Кузнечики
От: A13x США  
Дата: 20.12.19 08:18
Оценка:
Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:

По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 0 — голова списка, узел 1 — следующий за головой, узел 2 — следующий за 1-м узлом и т.д.

1. На самом первом шаге первый кузнечик помещается в узел 0 и не делает прыжков.
2. На каждом следующем шаге первый кузнечик прыгает на непосредственно следующий узел.
3. Второй кузнечик "шустрее" первого и делает за шаг два последовательных прыжка, но всегда после того, как прыгает первый кузнечик. На самом первом шаге второй кузнечик успевает прыгнуть на узел 1 и затем на узел 2. Далее, например, на втором шаге первый кузнечик прыгает в узел 1, а второй прыгает в узел 3 и затем в узел 4, на 3-м шаге первый прыгает в узел 2, а второй — в узел 5 и затем в узел 6 и так далее.
4. Как было сказано вначале, список зациклен, таким образом, что если кузнечик прыгает на следующий узел с некоторого узла M он попадает на узел N встречавшийся ранее. Считаем, что 0 < N < M.

Когда второй кузнечик встречает первого кузнечика на некотором прыжке некоторого шага, процесс останавливается.

Можно ли назвать количество узлов для части списка до начала цикла, если известны:
1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)?
2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)?
Отредактировано 20.12.2019 8:21 A13x . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.