Упорядочить объекты (Взвешивания, Алгоритм)

[Евгений Б.]

Имеется n объектов.
Все они различного веса.
Как нужно взвешивать их, чтобы потребовалось минимальное число взвешиваний для того, чтобы расположить их в порядке возрастания(убывания) веса?

Например для 3-х объектов я рассуждаю так:
· За одно взвешивание можно установить правее или левее один объект относительно другого
· После одного взвешивания имеется три различных варианта расположения третьего объекта относительно первых двух
· Если бы имелось два варианта—хватило бы ещё одного взвешивания
· С каким бы из двух объектов не сравнили третий—он или правее или левее него
· Правее или левее одного из двух объекта может находиться два варианта расположения третьего
· После третьего взвешивания неопределённостей не останется

Для 4-х:
· Четвёртый объект надо сравнивать так, чтобы после результата взвешивания было минимальное число вариантов расположения
· Очевидно, если сравнить со вторым, то их всего два.
· После этого для точного определения расположения четвёртого объекта нужно ещё одно взвешивание

А вот для 5-ти алгоритм немного меняется, хотя для 6-ти вроде такой же.

Непонятно как можно вывести общий алгоритм.

[TOTAL]

Евгений Б. писал(а):

А вот для 5-ти алгоритм немного меняется, хотя для 6-ти вроде такой же.[/color]
Непонятно как можно вывести общий алгоритм.

Разве меняется? Мне кажется, что для любого количества чисел их надо сортировать методом деления пополам
(т.е. любой другой метод сортировки в худшем случае будет не лучше, чем делением пополам).
Почитайте где-нибудь про сортировку.

[Евгений Б.]

Цитата:

Разве меняется? Мне кажется, что для любого количества чисел их надо сортировать методом деления пополам

Вот Я так же думал, но здесь получается что таким методом для 5-ти объектов надо 8 взвешиваний, а на самом деле минимальное число 7.

[TOTAL]

Евгений Б. писал(а):

Цитата:

Разве меняется? Мне кажется, что для любого количества чисел их надо сортировать методом деления пополам

Вот Я так же думал, но здесь получается что таким методом для 5-ти объектов надо 8 взвешиваний, а на самом деле минимальное число 7.

Как получается 7?

[Евгений Б.]

Цитата:

Как получается 7?

(1,2,3)сначала упорядочить 3 тремя взвешиваниями
(4)затем взвесить 4-ый и 5-ый
(5)потом 4-ый и 2-ой
(6)4-ый и 3-ий или 4-ый и 1-ый
(7)5-ый с 1-ым или с 3-им

[TOTAL]

Евгений Б. писал(а):

Цитата:

Как получается 7?

(1,2,3)сначала упорядочить 3 тремя взвешиваниями
(4)затем взвесить 4-ый и 5-ый
(5)потом 4-ый и 2-ой
(6)4-ый и 3-ий или 4-ый и 1-ый
(7)5-ый с 1-ым или с 3-им

Пусть 4-ый < 5-ый. И окажется, что 4-ый < 1-ый. Остался один ход, его не хватит.

Если 4-ый < 5-ы, то надо
(5) потом 4-ый и 1-ой,
тогда 7-ми ходов хватает.

[Евгений Б.]

И действительно правда..

Цитата:

Пуст 4-ый < 5-ый. И окажется, что 4-ый < 1-ый. Остался один ход, его не хватит.

в книге "Логические задачи" автор Жан-Клод Байиф есть такая таблица:

написано что для 5-ти 7 взвешиваний надо но не написано как

[Руст]

Всё подтверждается, количество взвешиваний $1+[log_2(n!-1)]$.

[Евгений Б.]

Цитата:

Всё подтверждается, количество взвешиваний $1+[log_2(n!-1)]$.

Ну формула-то конечно верна. Но алгоритм взвешивания не ясен. Не понятно как выбирать следующий объект для взвешивания.

[scorpio]

Ага, формула то верна. Она показывает минимум числа взвешиваний, но с чего вы взяли, что он всегда достежим?

[Евгений Б.]

Цитата:

но с чего вы взяли, что он всегда достежим?

если он есть, значит достижим. Всё зависит от того как мы взвешиваем. В этом и вопрос.
Ну сравните например:
чтобы упорядочить 5 объектов можно взвешивать как при пузырьковой сортировке
чтобы определить самый тяжёлый - 4 взвешивания
чуть легче - 3 взвешивания
ещё легче - 2
и ещё одно
10 получилось
и

методом деления пополам 8 взвешиваний




нашёл Вот здесь наконец-то.
Значит для любого количества подходит такой вариант? И является оптимальным?

[scorpio]

Евгений Б. писал(а):

если он есть, значит достижим. Всё зависит от того как мы взвешиваем.

В том-то и дело, что можно оценить снизу, но это не будет фактическим минимумом. До тех пор, пока не будет доказательста. Я пока такого не знаю.

[Руст]

Вообще то это оценка снизу. Легко получается оценка сверху. Упорядочивая последовательно k -ый элемент приводим в порядок с ранее приведёнными k-1 за $1+[log_2(k-1)]$ шагов. Поэтому оценка сверху есть

$$U_n=\sum_{k=1}^{n-1}(1+[log_2k])=n-1+\sum_{k=1}^{n-1}[log_2k].$$

По видимому для малых n оценка сверху совпадает с оценкой снизу $L_n=1+[log_2(n!-1)].$

[General]

О! Это ещё одна из задачек, которые любит мой учитель, а теперь и коллега, Сергей Тихонович Кузнецов. Действиетльно, 5 предметов можно рассортировать за 7 взвешиваний. Сейчас напишу как.

Добавлено спустя 2 минуты 23 секунды:

//а , увидел, нашли уже
Но мы учим курсантов искать решение так: после первых трёх измерений начинаем выписывать возможные варианты и смотреть, какое измерение разобьёт их на две более-менее равные группы.

[Евгений Б.]

Цитата:

Но мы учим курсантов искать решение так: после первых трёх измерений начинаем выписывать возможные варианты и смотреть, какое измерение разобьёт их на две более-менее равные группы

значит смысл в делении на равные группы.
Я, например, использовал такой метод, при котором группы или равные или в одной на 1 больше. И получалось 8 взвешиваний для 5 объектов.
А если сравнивать сначало пары, потом наибольшие из пар, то при таком методе вроде быстрее получается.