2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задача о болтах и гайках
Сообщение25.06.2011, 14:52 
Заслуженный участник


04/05/09
4596
На самом деле я уже погуглил - эта задача довольно долго была нерешённой, но в конце концов нашли алгоритм с $O(N\log N)$ сравнений. Он сводится к делению, как предложил hurtsy, но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение25.06.2011, 22:09 


01/07/08
836
Киев
venco в сообщении #462118 писал(а):
но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.


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

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение26.06.2011, 00:54 
Заслуженный участник


04/05/09
4596
hurtsy в сообщении #462203 писал(а):
venco в сообщении #462118 писал(а):
но средний элемент выбирается весьма нетривиально, чтобы исключить квадратичность.


Да, стратегия выбора обязана быть нетривиальной. Но ведь если некто(типа демона Максвелла, естественно не нарушая условий, а это возможно) будет подсовывать Вам наименьший элемент, не на чем будет строить выбор и быть квадратичности. Собственно, топик стартер об этом говорил, без привлечения ДМ. С уважением,
Ну у нас есть возможность потратить порядка $N$ сравнений для выбора более-менее среднего элемента, чтобы не ухудшить общую сложность $N\log N$.

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение26.06.2011, 12:53 


01/07/08
836
Киев
venco в сообщении #462232 писал(а):
Ну у нас есть возможность потратить порядка $N$ сравнений для выбора более-менее среднего элемента, чтобы не ухудшить общую сложность $N\log N$.


Согласен. :-) Просто "тему жалко". В итерационных методах для конечных разностей самая большая радость заменить $N$ на $\log N$. С уважением,

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение27.06.2011, 18:27 
Заслуженный участник


26/07/09
1559
Алматы

(Похожая задачка :))

Неподскажите, можно ли решить такую похожую задачку. Есть всего две гайки разного диаметра и два болта разного диаметра, нужно разместить гайки по возрастанию диаметра и болты, тоже по возрастанию диаметра, используя только сравнения диаметров изделий разного типа (как в исходной задаче). Заметьте, для гайки/болта необязательно существует комплементарное изделие того же диаметра. Но если для каждого изделия это условие выполняется, то задача эквивалентна исходной при $N=2$. Возможно ли решение в общем случае (но изделий каждого типа все-равно только две штуки)? Заранее спасибо.

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение27.06.2011, 19:27 
Заслуженный участник


04/05/09
4596

(Похожая задачка :))

Circiter в сообщении #462808 писал(а):
Неподскажите, можно ли решить такую похожую задачку. Есть всего две гайки разного диаметра и два болта разного диаметра, нужно разместить гайки по возрастанию диаметра и болты, тоже по возрастанию диаметра, используя только сравнения диаметров изделий разного типа (как в исходной задаче). Заметьте, для гайки/болта необязательно существует комплементарное изделие того же диаметра. Но если для каждого изделия это условие выполняется, то задача эквивалентна исходной при $N=2$. Возможно ли решение в общем случае (но изделий каждого типа все-равно только две штуки)? Заранее спасибо.
Нет. Возьмите два очень маленьких болта и две очень больших гайки.

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:51 
Основатель
Аватара пользователя


11/05/05
4313
 i  Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

Сейчас этот форум просматривают: Dmitriy40


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group