Часовой пояс: UTC + 3 часа




Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 18 
  Пред. тема | След. тема 
В случае проблем с отображением форума, отключите блокировщик рекламы
Автор Сообщение
 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Доброго. Есть такая задачка.
Дано: связанный список из N элементов, причем N неизвестно.
Требуется: проверить его на наличие зацикливаний, при этом алгоритм должен иметь линейную производительность ( O(N)).
Мне хватит собственно алгоритма или каких-нибудь наводок, реализацию я сам напишу...


Последний раз редактировалось Catar 16.12.2006 17:49, всего редактировалось 1 раз.


Партнер
 

Member
Статус: Не в сети
Регистрация: 14.01.2004
Откуда: Киев, Украина
Не ясно какой список, односвязный или двухсвязный? Плюс что понимается под словом зацикленность? Линейная производительность, я так понимаю значит то, что время выполнения алгоритма прямопорционально зависит от кол-ва элементов в списке?

_________________
Ку ку


 

Member
Статус: Не в сети
Регистрация: 28.03.2006
Ну что ж вы всё так усложняете. :) Берётся 2 указателя, которые будут идти с разныи шагом, если встретятся, то есть петля.

_________________
Первый огонь был получен людьми из-за перегрева.
Пессимист отличается от оптимиста датой наступления конца света.


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Daemon писал(а):
онимаю значит то, что время выполнения алгоритма прямопорционально зависит от кол-ва элементов в списке?

Ага.
Daemon писал(а):
односвязный или двухсвязный?

Односвязный.
Daemon писал(а):
люс что понимается под словом зацикленность?

N1->N2->N3->N1 и тд (это полная зацикленность)
N1->N2->N3->N4->N3 и тд (соответственно неполная)


Aside писал(а):
Берётся 2 указателя, которые будут идти с разныи шагом, если встретятся, то есть петля.

Да. Сидел думал и сам допер :) Это самое - я брал один указатель с шагом 1, другой с шагом 2. Это и есть оптимальный вариант?


 

Member
Статус: Не в сети
Регистрация: 28.03.2006
Catar
именно.

_________________
Первый огонь был получен людьми из-за перегрева.
Пессимист отличается от оптимиста датой наступления конца света.


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Еще одна задачка.
Есть массив из N чисел.
Есть число (A), которое повторяется в массиве нечетное число раз, все другие числа встречаются четное число раз. Определить число A за линейное время...


 

Member
Статус: Не в сети
Регистрация: 24.12.2005
Catar Перексорь все числа, получишь правильный ответ. :)


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Билли Бонс писал(а):
Перексорь все числа, получишь правильный ответ.

??
Код:
int a;
for(int i =0; i != N; ++i)
 a ^= array[i];

Добавлено спустя 4 минуты, 28 секунд
Гы, работает....
а на чем оно основано?


 

Member
Статус: Не в сети
Регистрация: 24.12.2005
Catar писал(а):
а на чем оно основано?
Ну как же: два одинаковых числа по xor дают ноль --> xor чётного количества одинаковых чисел = 0, а нечётного - самому числу.
Добавлено спустя 36 секунд
Catar писал(а):
int a;
int a = 0; :0)


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Билли Бонс писал(а):
int a = 0; :0)

дык это же не реальный кусок кода.... например никому не понятно, что такое array :)
естественно в рабочем app оно было прописано :)
Добавлено спустя 43 секунды
а если мы возьмем много чисел, встречающихся нечетное число раз, и будем искать ДВА числа, встречающихся четное число?


 

Member
Статус: Не в сети
Регистрация: 24.12.2005
Catar писал(а):
а если мы возьмем много чисел, встречающихся нечетное число раз, и будем искать ДВА числа, встречающихся четное число?
Не понял, это новая задачка? :) Почему именно два числа?


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Билли Бонс писал(а):
Не понял, это новая задачка?

ага.
Билли Бонс писал(а):
Почему именно два числа?

потому что это усложнение предыдущей задачи :)


 

Member
Статус: Не в сети
Регистрация: 24.12.2005
Хз. Имхо, за линейное время не получится... Счас что-то кроме перебора вообще в голову ничего не приходит.


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
Кстати говоря, там есть еще одно ограничение - исп. память не должна зависеть от N.


 

Advanced member
Статус: Не в сети
Регистрация: 09.03.2004
Откуда: Кишинёв
Код:
  #define MAX 0xFFFF+1
  unsigned short mas[MAX][3];
  unsigned short test[20] = {2,5,9,2,4,1,6,3,9,5,5,1,7,9,4,8,1,5,4,11};
 
  int i;
  for(i=0;i<MAX;i++) mas[i][0]=0,mas[i][1]=0,mas[i][2]=0; // обнуляем
 

  for(i=0;i<20;i++){ // сам процесс
         mas[test[i]][0] = 1;
         mas[test[i]][1] = test[i];;
         mas[test[i]][2] ^= test[i];
  }
 
  for(i=0;i<MAX;i++) // выделяем нужные числа
       if( mas[i][0] && !mas[i][2] )  printf("%d\n",mas[i][1]);


Немного громоздко, но зато линейно и потребление памяти не зависит от N. Разве что тип элементов массива ограничен(для чисел типа int уже потребуются гигабайты памяти).

зы: алгоритм находит все числа, встречающиеся чётное число раз.


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
mein писал(а):
линейно и потребление памяти не зависит от N.

я имел ввиду O(1) :cry:


 

Advanced member
Статус: Не в сети
Регистрация: 09.03.2004
Откуда: Кишинёв
Catar А что есть O(1) ? Насколько я знаю(подзабыл конечно малость за пару лет) это и есть линейность.


 

Member
Статус: Не в сети
Регистрация: 11.04.2004
Откуда: СПБ
mein писал(а):
А что есть O(1)

я говорил о памяти.... несколько переменных еще куда ни шло... но
mein писал(а):
для чисел типа int уже потребуются гигабайты памяти

не годится...
mein писал(а):
есть линейность.

O(N)


Показать сообщения за:  Поле сортировки  
Начать новую тему Новая тема / Ответить на тему Ответить  Сообщений: 18 
-

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB | Kolobok smiles © Aiwan