Страниц: [1]
  Печать  
Автор Тема: Алгоритм для массива  (Прочитано 7345 раз)
0 Пользователей и 1 Гость смотрят эту тему.
HeeL
Модератор
Гений
*****
Offline Offline

Сообщений: 830

СПАСИБО
-вы поблагодарили: 371
-вас поблагодарили: 284


121231532
Просмотр профиля
: Июль 06, 2010, 07:23:17 �

Есть массив целых чисел величины N диапазона 0-(N-1). Нужно придумать метод, который вернет -1, если все числа разные, или одно из повторяющихся, если таковые есть. Можно портить начальный массив. Нельзя тратить много памяти, сложность алгоритма = N. Короче говоря, отсортировать и пройтись пузырьком - не годится.
Записан

По Вашему жизнь сложная? Нет, это просто Вы тупые =)
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #1 : Июль 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;

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

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
Репка
Умник
****
Offline Offline

Сообщений: 694

СПАСИБО
-вы поблагодарили: 47
-вас поблагодарили: 42



Просмотр профиля
Ответ #2 : Июль 06, 2010, 23:01:42 �

Первый не удовлетворяет условию сложность алгоритма = N, а второй можешь на словах идею поянить? Читать код мне тяжело, тем более на паскале.
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #3 : Июль 06, 2010, 23:22:40 �

идея второго кода, наверное, попытаться разбить перестановку на независимые циклы
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #4 : Июль 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. Я не шарю в сложностях алгоритмов.

Эти пользователи сказали вам СПАСИБО :

Репка

За это сообщение 1 пользователь сказал спасибо!
Последнее редактирование: Июль 06, 2010, 23:51:06 от MagTux Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #5 : Июль 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} мы почти сразу вернёмся к старту и надо перебирать элементы дальше для старта. Для этого в алгоритме нужен ещё один цикл.
Последнее редактирование: Июль 06, 2010, 23:48:19 от MagTux Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #6 : Июль 07, 2010, 15:14:08 �

создаем вспомогательный массив M[0..n-1]. все элементы массива M устанавливаем в 0. перебираем все элементы заданного массива A и изменяем значения элементов массива M : M[Ai ]=M[Ai]+1; как только произойдет повтор какого либо значения в массиве A значение M[Ai] станет равным 2. на этом перебор можно прекратить и вернуть значение Ai.
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
MagTux
Гений-Говорун
*
Offline Offline

Сообщений: 1415

СПАСИБО
-вы поблагодарили: 46
-вас поблагодарили: 99


Реинкарнация Будды


Просмотр профиля
Ответ #7 : Июль 07, 2010, 15:57:43 �

Это займёт больше памяти, чем мой алгоритм. Требуется дополнительный массив.

Хотя я тоже отталкивался от сортировки подсчётом.
Последнее редактирование: Июль 07, 2010, 19:16:03 от MagTux Записан

Существует два правила на пути к успеху:
1. Не говори никому всего, что ты знаешь.
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #8 : Июль 07, 2010, 20:53:13 �

введение дополнительного массива по условию вполне допустимо, главное чтобы количество операций было пропорционально N, а не например N^2 или N*ln(N). можно обойтись и одним массивом - например сначала все A умножить на 2 и затем прибавлять 1 к A[ Ai div 2 ]. если перед таким прибавлением Ai уже нечетно вовращаем (Ai div 2). 
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
Страниц: [1]
  Печать  
 
Перейти в: