Вот условие задачи :



вот мой алгоритм :


проблема заключается в корректном написании функции  ,которая отвечает за вычисление функции f(....f(...f(i))).Подскажите как реализовать данную функцию?

Это сообщение отредактировал(а) terance - 17.7.2009, 17:06

Вообще мне кажется, что при 10^6 должно быть совсем другое ("умное") решение (хотя, если честно, твоё решение я не понял совсем  ).

Эта последовательность f[i], f[f[i]], и т.д. - рано или поздно она сойдётся в цикл. Т.е. для любого индекса i мы либо рано или поздно придём в себя же, тем самым мы обнаружим просто цикл (тогда ответом для этого индекса i, как и для всех остальных индексов обнаруженного цикла, будет один и тот же, и этот ответ будет равен длине цикла). Либо для индекса i мы в себя не придём, на зато рано или поздно придём в какой-то индекс j дважды - это ситуация, когда есть какой-то цикл, но до этого цикла есть "хвостик": начиная с i, мы идём по этому хвосту, пока не попадём в цикл. Тогда ответом для всех индексов цикла, опять же, будет одним и тем же и равным длине цикла, а ответом для элементов хвоста будет длина цикла плюс расстояние до цикла.

Много слов, но кода будет гораздо меньше (работать будет за O(N), в отличие от квадратичного тривиального решения). Ну если уж не получается написать, могу помочь, но всё же самому это будет гораздо полезней 

решаю задачу "в лоб" т.е. для каждого аргумента пытаюсь вычислить его максимальное разнообразие))) 



но все таки ,для реализации данной идеи нужна "элементарная операция"-поиск элемента с заданным индексом i (или я чего-то сам не допонял))).а поиск вроде как в лучшем случае работает за O(N*N)....

Всё, что будет нужно - по индексу i смотреть значение f[i]. Никаких рекурсий f(...f(i)...) не будет нужно. За счёт того, что при обнаружении цикла ответ будет проставляться сразу для всех элементов цикла (а не для каждого заново, как у тебя), асимптотика будет линейной.

А если решаешь в лоб (а для n=10^6 это решение будет работать страшно долго), то надо вычислять эту штуку f(...f(i)...). Очевидно, что функции eval надо передавать индекс i и уровень вложенности. Выглядеть она будет как-то так:

Для вычисления eval в худшем случае будет O(N) операций. А для обнаружения цикла тебе надо будет перебирать все уровни вложенности, для каждого вызывать eval, да ещё и как-то обнаруживать повторы... В простой реализации вообще куб будет, ну чуть изменив - квадрат будет, но всё равно ж долго... В общем, одумайся 


По поводу моего метода - могу пояснения.
пример:
f[1] = 2, f[2] = 1, f[3] = 3
Здесь для индекса i = 1 мы составим последовательность: 1, f[1]=2, f[2]=1 - стоп, обнаружили цикл длины 2; всё, опять проходимся по циклу (т.е. по элементам 1 и 2) и для них в качестве ответа ставим длину цикла, которая равна 2.
Для индекса i = 2 ниче не делаем - ответ уже посчитан.
Для индекса i = 3 составляем последовательность: 3, f[3] = 3 - стоп, цикл длины 1, ответ для 3 равен 1.
Всё. Это был пример с двумя циклами.

Пример с циклом с хвостиком:
f[1] = 2, f[2] = 3, f[3] = 2
Для индекса i = 1 последовательность получается: 1, f[1] = 2, f[2] = 3, f[3] = 2 - стоп, обнаружили цикл длины 2; проходимся по циклу (т.е. по элементам 2 и 3), проставляем ответ = 2, потом проходимся по хвосту, здесь он содержит единственный элемент 1, для него ответ равен расстояние_до_цикла - 1 + длина_цикла, т.е. 1-1+2=2.

вопрос :

как можно отличить ситуацию "с хвостом" от ситуации "без хвоста"?

вот моя реализация первой части :ситуация "без хвоста"

для обнаружения цикла последовательности an даже с возможностью хвоста можно сравнивать a[n] и a[2n], когда n станет больше длины хвоста, то первое же значение, кратное периоду, даст равенство, после этого можно пройтись от a[n], чтобы найти период, а потом пройтись по a[k] и a[k+T], чтобы найти начало цикла (если оно нужно)

terance
Во-первых, советую дописать до конца разбор первого случая. Т.е. чтобы она работала для всех случаев без хвостов, и разумеется проставляла ответ (у тебя пока она просто ходит по массиву).

Во-вторых, как обнаруживать цикл с хвостом. Как предложил maxim1000 - можно, но имхо это слишком "хороший" метод, он без использования доп. памяти. А можно и попроще: проставлять в некотором массиве used[] true для встретившихся элементов. Тогда, если мы пытаемся поставить used[some_index]=true, а там уже стоит true, то обнаружили цикл (сам этот цикл можно восстановить, взяв some_index и применив к нему решение первого случая задачи). После этот можно очищать массив used и заняться проставлением ответа для хвоста (хвостом будет всё, начиная со стартового индекса и заканчивая some_index не включая его).

Тут маленькое примечание (для начала его можно пропустить, пока главное, чтобы хоть как заработало  ) : чтобы достичь действительно линейного времени, очищать массив used надо не заполнением его всего false'ами, а надо обнулять только те элементы, которые действительно были поставлены в true: берём стартовый индекс, и запускаем от него этот процесс итераций, только в массив used[] уже ставя false'ы для каждого текущего индекса. Как только случится, что мы хотим поставить false, а там уже стоит false - останавливаем, всё, мы обнулили used вдоль хвоста с циклом.