Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Решение задачи

Автор: terance 17.7.2009, 16:40

Вот условие задачи : Цитата Функция f {1, ..., n} → {1, ..., n} (1 ≤ n ≤ 10^6) задана значением n и таблицей f(1), ..., f(n). Для каждого аргумента i (1 ≤ i ≤ n) определим его разнообразие как количество различных значений, встречающихся в (бесконечной) последовательности f(i), f(f(i)), f(f(f(i))), ... . Найти аргумент, имеющий максимальное разнообразие. вот мой алгоритм : Код int c=0; int d=0; int j=1; int data[n];//массив значений функции ,индексация массива мначинается с 1 int results[n];//n-заданное число не превосходящее 10^6,в этот массив заносятся разнообразия каждого из индекса массива for(int i=1;i++;i<n){     с=data[i];     if((c>=1)&&(c<=n)){//если значение функции совпадает со следующим аргументом             d++;             c=eval(c);     }      else{             result[j]=c;             j++;     } } проблема заключается в корректном написании функции  Код void eval(int arg)  ,которая отвечает за вычисление функции f(....f(...f(i))).Подскажите как реализовать данную функцию?

Автор: maxdiver 17.7.2009, 19:20

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

Автор: terance 17.7.2009, 20:15

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

Автор: maxdiver 17.7.2009, 21:46

Всё, что будет нужно - по индексу i смотреть значение f[i]. Никаких рекурсий f(...f(i)...) не будет нужно. За счёт того, что при обнаружении цикла ответ будет проставляться сразу для всех элементов цикла (а не для каждого заново, как у тебя), асимптотика будет линейной. А если решаешь в лоб (а для n=10^6 это решение будет работать страшно долго), то надо вычислять эту штуку f(...f(i)...). Очевидно, что функции eval надо передавать индекс i и уровень вложенности. Выглядеть она будет как-то так: Код int eval (int i, int depth) {    if (depth == 0)       return i;    return f (eval (i, depth-1)); } Для вычисления 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.

Автор: terance 17.7.2009, 23:05

вопрос : как можно отличить ситуацию "с хвостом" от ситуации "без хвоста"? вот моя реализация первой части :ситуация "без хвоста" Код int start=0; int length=0; start=index;//index-номер аргумента для которого вычисляем разнообразие int next(int elem){      if(start==elem) return length;      else{             start=f[elem];//в массиве f[] хранятся значения функции f             length++;             next(start);      } }

Автор: maxim1000 17.7.2009, 23:58

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

Автор: maxdiver 18.7.2009, 18:22

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)