Форум умных людей

Задачи и головоломки => Помогите решить! => Тема начата: HeeL от Июль 06, 2010, 07:23:17


Название: Алгоритм для массива
Отправлено: HeeL от Июль 06, 2010, 07:23:17
Есть массив целых чисел величины N диапазона 0-(N-1). Нужно придумать метод, который вернет -1, если все числа разные, или одно из повторяющихся, если таковые есть. Можно портить начальный массив. Нельзя тратить много памяти, сложность алгоритма = N. Короче говоря, отсортировать и пройтись пузырьком - не годится.

Название: Re: Алгоритм для массива
Отправлено: MagTux от Июль 06, 2010, 22:55:35
Проще, чем это (банально и неинтересно), я придумать не смог.
Используется исходный массив и 3 переменных.
Код: (Pascal)
result:=-1;
for i:=0 to n-2 do
  for j:=i+1 to n-1 do
    if M[i]=M[j] then
      begin
        result:=M[i];
        break;
      end;

Есть вариант похитрее и поинтереснее.
Используется также исходный массив и 3 переменных, но цикл, вроде, покороче.
Код: (Pascal)
result:=-1;
for i:=0 to n-1 do
  begin
    if M[i]=-1 then continue;
    x:=M[i];
    M[i]:=-1;
    while x<>i do
      begin
	  if M[x]=-1 then
          begin
            {число x уже было}
            result:=x;
            break;
          end;
        x:=M[x];
        M[x]:=-1;
      end;
    if result>-1 then break;
  end;

Пишу вечером, поэтому мог упустить что-то. Возможно его можно оптимизировать.

Название: Re: Алгоритм для массива
Отправлено: Репка от Июль 06, 2010, 23:01:42
Первый не удовлетворяет условию сложность алгоритма = N, а второй можешь на словах идею поянить? Читать код мне тяжело, тем более на паскале.

Название: Re: Алгоритм для массива
Отправлено: iPhonograph от Июль 06, 2010, 23:22:40
идея второго кода, наверное, попытаться разбить перестановку на независимые циклы

Название: Re: Алгоритм для массива
Отправлено: MagTux от Июль 06, 2010, 23:32:22
Если вкратце без подробностей:
Берём первый элемент (X=M[0]), помечаем как прочитанный (M[0]=-1), берём элемент с индексом X (X=M[X]), помечаем (M[X]=-1) и т.д. Если в процессе перебора мы получим M[X]=-1 и при этом он не был взят первым (X<>0), значит значение X уже было ранее.

P.S. Я не шарю в сложностях алгоритмов.

Название: Re: Алгоритм для массива
Отправлено: MagTux от Июль 06, 2010, 23:44:02
Если в простейшем случае возьмём N=5. Все элементы разные.
Код:
M={2 3 4 0 1}
X=M[0]=2
M={-1 3 4 0 1}
X=M[2]=4
M={-1 3 -1 0 1}
X=M[4]=1
M={-1 3 -1 0 -1}
X=M[1]=3
M={-1 -1 -1 0 -1}
X=M[3]=0
M={-1 -1 -1 -1 -1}
X=M[0]=-1
Мы вернулись к стартовому элементу. Обход окончен. Элементы разные.

Теперь есть повторы.
Код:
M={2 3 4 0 2}
X=M[0]=2
M={-1 3 4 0 2}
X=M[2]=4
M={-1 3 -1 0 2}
X=M[4]=2
M={-1 3 -1 0 -1}
X=M[2]=-1
Мы получили -1, но не вернулись к стартовому элементу. Повтор найден. Он равен последнему значению X=2 (до получения пометки -1).

Например, в массиве M={2 3 0 1 2} мы почти сразу вернёмся к старту и надо перебирать элементы дальше для старта. Для этого в алгоритме нужен ещё один цикл.

Название: Re: Алгоритм для массива
Отправлено: moonlight от Июль 07, 2010, 15:14:08
создаем вспомогательный массив M[0..n-1]. все элементы массива M устанавливаем в 0. перебираем все элементы заданного массива A и изменяем значения элементов массива M : M[Ai ]=M[Ai]+1; как только произойдет повтор какого либо значения в массиве A значение M[Ai] станет равным 2. на этом перебор можно прекратить и вернуть значение Ai.

Название: Re: Алгоритм для массива
Отправлено: MagTux от Июль 07, 2010, 15:57:43
Это займёт больше памяти, чем мой алгоритм. Требуется дополнительный массив.

Хотя я тоже отталкивался от сортировки подсчётом.

Название: Re: Алгоритм для массива
Отправлено: moonlight от Июль 07, 2010, 20:53:13
введение дополнительного массива по условию вполне допустимо, главное чтобы количество операций было пропорционально N, а не например N^2 или N*ln(N). можно обойтись и одним массивом - например сначала все A умножить на 2 и затем прибавлять 1 к A[ Ai div 2 ]. если перед таким прибавлением Ai уже нечетно вовращаем (Ai div 2).