два указателя

[avva]

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

Comments

RE: Re: "А ты не так прост, как кажешься" [Губерман]

[bopstr]

Попробовал. Получилось процентов на 30 меньше вызовов fn(), но сложность всё равно квадратичная (5×5 - 60 вызовов, 7×7 - 119, то есть снова умножилось на 7/5^2).

Вот код:

auto fn_calls = 0;
auto fn = [&fn_calls, m, n](auto pos) { ++fn_calls; return (pos % m) * n + (pos / m); };

auto is_start = [fn](auto pos) -> bool {
auto this_pos = pos;
for (auto ret = 0; true; ++ret)
{
this_pos = fn(this_pos);
if (this_pos < pos)
return false;
if (this_pos == pos)
return true;
}
};

auto rotate = [&M, fn](auto i) mutable
{
auto elem = std::move(M[i]);
auto nPos = i;
do
{
nPos = fn(nPos);
std::swap(elem, M[nPos]);
} while (nPos != i);
};

for (auto i = 0; i < m * n; ++i)
{
if(is_start(i))
{
rotate(i);
}
}

Re: "А ты не так прост, как кажешься" [Губерман]

[dvornikstepanof]

Да, алгоритм квадратичный. Но не хочу больше засорять блог Анатолия. Я постараюсь сегодня попозже написать отдельный пост об этой задачке и поместить его (в кои-то веки) в своем ЖЖ. Я дам здесь линк.

Re: "А ты не так прост, как кажешься" [Губерман]

[dvornikstepanof]

Я тут постарался написать более или менее связно об этой задачке.