2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача о болтах и гайках
Сообщение22.06.2011, 14:12 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
Имеется $N$ болтов и столько же гаек, отличающихся диаметрами. Нет ни двух болтов одинакового диаметра, ни двух гаек одинакового диаметра. Однако каждая гайка подходит по диаметру ровно к одному болту, и наоборот.

За одну операцию разрешается сравнить диаметры одного болта и одной гайки. Сравнивать между собой диаметры болтов или диаметры гаек непосредственно нельзя, только опосредованно: например, выяснив, что диаметр болта X больше диаметра гайки Y, а диаметр гайки Y больше диаметра болта Z, мы можем заключить, что диаметр болта X больше диаметра болта Z. "На глазок" тоже ничего не видно :D

Требуется определить, какому болту какая гайка подходит по диаметру.

Понятно, что можно тупо сравнить каждую гайку с каждым болтом, и дело в шляпе.
Интересует алгоритм, использующий менее, чем $O(N^2)$ операций.

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


01/07/08
836
Киев
worm2 в сообщении #461093 писал(а):
Понятно, что можно тупо сравнить каждую гайку с каждым болтом, и дело в шляпе.
Интересует алгоритм, использующий менее, чем $O(N^2)$ операций.

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

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение22.06.2011, 17:58 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
Вероятно, в среднем данный метод приведёт к результату достаточно быстро. Однако в наихудшем случае может случиться так, что взятая наугад гайка окажется самой маленькой или самой большой (или её диаметр будет достаточно близок к экстремальному). И тогда число требуемых сравнений окажется близким к максимальному.

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


21/05/11
897
А если болты одинакового диаметра и различаются шагом резьбы, её направлением и/или числом заходов?

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение22.06.2011, 18:31 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
А нам всё равно. Главное — диаметр, а там молотком забьём если чо.

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


01/07/08
836
Киев
worm2 в сообщении #461195 писал(а):
И тогда число требуемых сравнений окажется близким к максимальному.


А вероятность такого печального исхода $\frac 1 {N!}$. С уважением,

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


04/05/09
4582
Рабочая структура - множество деревьев, в которых каждый узел (болт или гайка) меньше дочерних узлов. В каждом дереве тип узлов (болт/гайка) чётных и нечётных уровней чередуется. Причём обязательно есть хотя бы одно дерево с болтом в корне, и хотя бы одно дерево с гайкой в корне, т.к. самые маленькие из не подобранных болт и гайка находятся в корне какого-либо дерева.
Изначально у нас N деревьев с гайкой в корне и N деревьев с болтом в корне (без дочерних узлов).
На каждом шаге берём самое маленькое дерево с болтом в корне и самое маленькое дерево с гайкой в корне, и сравниваем эти корни.
Если они подходят, то отделяем их, а соответствующие поддеревья возвращаем в общее множество деревьев. Если не подходят, то объединяем эти деревья соответствующим образом.
В конце концов все пары найдутся. Сложность, вроде, получается $N \log N$.

-- Ср июн 22, 2011 18:53:22 --

Увы, всё равно в худшем случае квадрат.

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


01/10/10
54
Все предложенное есть у Д.Кнута - Искусство программирования для ЭВМ, том 3.
Только немного модифицировать надо.
hurtsy предложил метод Быстрой сортировки Хоара, наиболее быстрый в среднем. Но в худшем случае имеет порядок $N^2$
venco - Пирамидальная сортировка, хотя надо разобраться с реализацией - все ли получится. Этот алгоритм и в среднем, и в худшем, да вообще-то всегда имеет время работы порядка $N \ln N $, но очень велики накладные расходы, в несколько раз выше, чем в Быстрой сортировке.

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


14/01/11
2914
Можно попробовать так: сформируем упорядоченный по возрастанию массив, элементами которого являются неупорядоченные множества элементов одного типа(болтов или гаек) и пары подходящих болтов и гаек. Упорядоченность массива означает, что все болты (гайки) n-го элемента меньше всех гаек (болтов) n+1-го элемента. Сначала формируем пустой массив, затем добавляем в него по очереди болты и гайки из исходного набора, сохраняя упорядоченность по возрастанию: добавляя болт или гайку, ищем место вставки в массив бинарным поиском. Сравнивая, к примеру, болт с элементом, представляющим собой неупорядоченное множество гаек, сравниваем его по очереди со всеми гайками этого множества, если при этом какие-то гайки меньше болта, а какие-то больше, разбиваем этот элемент на два, болт помещаем между ними. Если какая-то гайка подходит к болту, помещаем её в один элемент с ним. В итоге должен получиться упорядоченный массив подходящих пар.

Да, в худшем случае получается $O(N^2)$ опять-таки.

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


01/07/08
836
Киев
Psw в сообщении #461300 писал(а):
hurtsy предложил метод Быстрой сортировки Хоара, наиболее быстрый в среднем. Но в худшем случае имеет порядок $N^2$

Официально заявляю, у меня нет претензий на авторство. :D
В таких вещах никогда не знаешь откуда информация попала "в подсознание". Но это дествительно болезнь многих практических алгоритмов, обязательно находится случай для худших ожиданий. Если для "бессмертных" алгоритмов это контрпример, для "коротко живущих " программ, зависящих от версий ОС, версий ПО(языка программирования) да иногда от требований заказчика,(к сожалению давно не встречался с таковым), приходится учитывать малую вероятность "контрпримера".
У меня есть подозрение, что у топик стартера заготовлен ответ. Так сообщите, не томите душу.
С уважением,

 Профиль  
                  
 
 Re: Задача о болтах и гайках
Сообщение23.06.2011, 12:44 
Заслуженный участник
Аватара пользователя


01/08/06
3046
Уфа
hurtsy писал(а):
У меня есть подозрение, что у топик стартера заготовлен ответ.
Увы мне, топикстартеру :-(
Я прочитал о задаче пару недель назад вот здесь:
http://easy-coding.blogspot.com/2011/06/blog-post.html
Несколько раз брался за решение, но у меня ничего не получилось.
Но это ещё не значит, что она очень сложная.
Может быть, здесь есть какой-то простой и изящный ход, который при длительном обдумывании всплывёт из подсознания. Тем более, там пишут, что задача задаётся на собеседовании.

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


04/05/09
4582
Попробовал приспособить сортировки вставкой и слиянием. В любом случае получается худший вариант $O(N^2)$. Похоже, это неизбежно.

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


01/07/08
836
Киев
worm2 в сообщении #461373 писал(а):
Тем более, там пишут, что задача задаётся на собеседовании.


Собеседование, необязательно , преследует цель решить задачу. Там диапазон от фильтрации до селекции собеседуемых. Я уж было на Вас понадеялся. :? С уважением

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


24/05/09

2054
hurtsy в сообщении #461192 писал(а):
Для начала все равно берем наугад гайку и меряем со всеми болтами. В результате болты разбиты на большие гайки, меньшие и один того же размера что и гайка. Этим болтом разобьем множество гаек на две группы. В результате получаем две задачи меньшей размерности. Напоминает метод половинного деления. С уважением,


//модификация метода hurtsy:

Сравниваем две группы рассортированных болтов, если одна сильно превышает другую (первоначальный выбор гайки оказался неудачным) - то найденную пару в ящик готовой продукции и начинаем сначала. Если рассортированные болты поделились примерно поровну, то рассортировываем болтом гайки и продолжаем поиск отдельно в каждой группе.

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


01/07/08
836
Киев
Alexu007 в сообщении #462012 писал(а):
Если рассортированные болты поделились примерно поровну, то рассортировываем болтом гайки и продолжаем поиск отдельно в каждой группе.


А если иначе ... :?: В том то и дело, "сатана никогда не ждет реванша" и опять впереди маловероятное но такое грозное $O(N^2)$.Вот если бы применить метод подобный тому, что если треугольник закрепить в вершине, отвесная линия будет медианой. Остается надежда на быстрые упорядочения.
venco в сообщении #461500 писал(а):
В любом случае получается худший вариант $O(N^2)$. Похоже, это неизбежно.

:wink: С уважением,

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

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



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

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


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

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