|
Есть $%10$% монет разного веса и некоторые весы. При помощи одного взвешивания на весах можно узнать для выбранных двух монет, какая тяжелее. Можно ли за $%20$% взвешиваний узнать, в каком порядке монеты идут по весу? задан 30 Май '15 23:20 
stander |
|
Нельзя. Даже 21 взвешивания здесь не хватит. Для 10 монет имеется $%10!$% возможных расположений их по весу. Заметим, что $%10!=2^8\cdot3^4\cdot5^2\cdot7=2^8\cdot14175$%, то есть $%2^{21} < 10! < 2^{22}$%. Предположим, что у нас есть способ упорядочить все пакеты по весу за 21 взвешивание. Проделав все эти взвешивания, мы имеем их "протокол", который можно представить в виде последовательности символов L и R в зависимости от того, левая или правая чаша весов перевесила. Таких "протоколов" имеется в точности $%2^{21}$% (причём не обязательно все они реализуемы). Этой последовательности должна однозначно соответствовать одна из $%21!$% перестановок, которая представляет собой угаданное упорядочение пакетов по весу, но это невозможно ввиду неравенства $%2^{21} < 10!$% ("протоколов" меньше, чем перестановок). То, что 22 взвешиваний уже хватает, факт верный, но он из вышеприведённого рассуждения не следует. Неравенства там выступают лишь в качестве необходимого условия. отвечен 31 Май '15 3:26 
falcao @falcao Опишите ваш алгоритм сравнения? Я свой наивный описал) Для случая если монеты изначально вам данны в возрастающем порядке, то сравнивая $$1 \vee 2 \Rightarrow 2 \vee 3 \Rightarrow 3 \vee 4 \Rightarrow 4 \vee 5 \Rightarrow 5 \vee 6 \Rightarrow 6 \vee 7 \Rightarrow 7 \vee 8 \Rightarrow 8 \vee 9 \Rightarrow 9 \vee 10$$ используя 9 взвешиваний вы поймете что монеты уже упорядочены в возрастающем порядке.
(31 Май '15 4:12)
void_pointer
Кол-во взвешиваний будет зависить от того в каком порядке вам данны монеты и какой алгоритм вы используете. Если на практике вы сможете выпонить все ходы алгоритма mergesort - http://en.wikipedia.org/wiki/Merge_sort то даже в худшем случае вам понадобится $%n{\log _2}n$% 33-34 взвешивания.
(31 Май '15 4:19)
void_pointer
@void_pointer: я здесь не описываю процедуры сравнения, потому что требуется получить оценку снизу. То есть доказывается, что при каких угодно "хитрых" способах мне не хватит 21 взвешивания в общем случае, как бы я ни старался. Задача рассмотрения способов взвешивания, которые работают на любом наборе, совершенно отдельная: это оценка в другую сторону. И там надо начинать с относительно простых случаев типа $%n=4$% и $%n=5$%. Ответами будут 5 и 7 взвешиваний соответственно, причём последнее не совсем тривиально.
(31 Май '15 4:28)
falcao
А каким методом вы пришли к выводу что минимальное кол-во взвешиваний даже в худшем случае не меньше 21? Ведь это намного быстрее $%O(n{\log _2}n)$% что даст 33-34 взвешивания в худшем случае. Само собой что все сводится к перестановкам и сравнению но чего-то я не пойму через какой алгоритм вы нашли что 22 взвешивания хватает даже для случая когда все 10 монет даны вам в обратном по возрастанию порядке?
(31 Май '15 4:40)
void_pointer
Вот допустим перед вами на столе лежат 10 монет в таком порядке $$\begin{bmatrix}10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\end{bmatrix}$$ Опишите пожалуйста как за 22 взвешивания вы упорядочите их в $$\begin{bmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\end{bmatrix}$$
(31 Май '15 4:42)
void_pointer
@void_pointer: Вы странный вопрос задали -- у меня здесь приведено решение (достаточно короткое), в котором показано, что 21 взвешивания не достаточно. Основой является неравенство $%10! > 2^{21}$%. Это стандартный метод получения нижних оценок -- наподобие того, что за 6 вопросов с ответами типа "да"-"нет" нельзя в общем случае угадать одно из 100 задуманных чисел. Это следует из того, что $%100 > 2^6$%. Описание процедуры для 10 монет, которая работает в общем случае, включая Ваш, достаточно сложно. Это не входит в условие задачи. Я уже говорил, что даже для 5 монет способ нетривиален.
(31 Май '15 5:00)
falcao
@void_pointer: отвечаю здесь на комментарий по поводу "простоты" этой задачи. Предлагаю ознакомиться с этой ссылкой, где можно узнать состояние дел по данной проблеме. Ответ для общего случая там, кстати, известен (я спутал с какой-то другой задачей, думая, что она до конца не решена). Но в любом случае там всё достаточно нетривиально.
(31 Май '15 5:20)
falcao
показано 5 из 7
показать еще 2
|
|
Можно разобрать более простой случай (на примере): Рассмотрим 5 монет разного веса в виде массива $%\begin{bmatrix}5 & 3 & 10 & 1 & 8\end{bmatrix}$%. Все монеты разного веса и не отсортированы по весу. Берем первую монету и сравниваем со второй: $%5 \vee 3$%. Ставим $%3$% вначало а $%5$% на ее место $%\begin{bmatrix}3 & 5 & 10 & 1 & 8\end{bmatrix}$%. Теперь сравниваем $%5 \vee 10$%, так как $%10$% больше $%5$% то мы не меняем местами $%10$% и $%5$%: $%\begin{bmatrix}3 & 5 & 10 & 1 & 8\end{bmatrix}$%. Итак в данный момент $%10$% - самая тяжелая монета. Далее идет цепочка сравнений, чтобы выяснить куда поставить $%1$% $$10 \vee 1 \Rightarrow \begin{bmatrix}3 & 5 & 1 & 10 & 8\end{bmatrix}$$ $$5 \vee 1 \Rightarrow \begin{bmatrix}3 & 1 & 5 & 10 & 8\end{bmatrix}$$ $$3 \vee 1 \Rightarrow \begin{bmatrix}1 & 3 & 5 & 10 & 8\end{bmatrix}$$ Теперь нужно проделать тоже самое с последней монетой: $$10 \vee 8 \Rightarrow \begin{bmatrix}1 & 3 & 5 & 8 & 10\end{bmatrix}$$ $$5 \vee 8 \Rightarrow \begin{bmatrix}1 & 3 & 5 & 8 & 10\end{bmatrix}$$ Итого для сортировки $%5$% монет нам понадобилось $%7$% сравнений, что эквивалентно $%7$% взвешиваниям. Стоит отметить что операция по перемещению монет между позициями в ряду не имеет ресурсовых или временных ограничений. Так как в контексте задачи учитывается только кол-во взвешиваний, то есть сравнений. Вообщем Worst Case: $%O(n^2)$% - это если все монеты изначально отсортированы в обратном порядке. В данном случаем понадобится ровно $%\frac{{{n^2} - n}}{2}$% взвешиваний. Где $%n$% - кол-во монет. В любом другом случае понадобится меньше чем $%\frac{{{n^2} - n}}{2}$% взвешиваний. То есть если на столе лежит 10 монет в таком порядке $%\begin{bmatrix}10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\end{bmatrix}$% то понадобится $%\frac{{{n^2} - n}}{2} = \frac{{100 - 10}}{2} = 45$% взвешиваний чтобы упорядочить их по возрастающему весу. Если на столе лежим 10 монет в таком порядке $%\begin{bmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\end{bmatrix}$% 9 взвешиваний. То есть вытекает закономерность: Если $%n$% монет изначально даны в возрастающем порядке то понадобится $%n - 1$% взвешинаний чтобы это определить, если же монеты даны в убывающем порядке то понадобится $%\frac{{{n^2} - n}}{2}$% взвешиваний чтобы расставить монеты в возрастающем порядке. Так я обозначил нижнюю и верхнюю границы для сортировки $%10$% монет используя наивный метод сравнения. Можно использовать рекурсионный алгоритм, например MergeSort. Но даже с его помощью вам понадобится в худшем случае $%n \cdot {\log _2}n$% сравнений. отвечен 31 Май '15 1:17 
void_pointer @void_pointer: верхняя оценка $%O(2n)$% неверна. Там нужно как минимум $%O(n\log n)$% взвешиваний.
(31 Май '15 3:29)
falcao
@falcao исправил
(31 Май '15 3:53)
void_pointer
@void_pointer: верхняя оценка порядка $%O(n^2)$%, когда каждая монета взвешивается с каждой, хотя и верна сама по себе, но она заведомо не оптимальна. Понятно, что 45 взвешиваний хватает, но можно предложить способ, где требуется меньшее число. Скажем, для 4 монет достаточно 5 взвешиваний, а оценка $%\frac{4^2-4}2=6$% оптимальной не будет.
(31 Май '15 3:57)
falcao
Но нужно все равно учитывать лучший и худший случаи. В задаче не сказано какой именно случай рассматривается. Поэтому если мы имеем дело с оптимальным то есть лучшим случаем то для 10 монет хватит 9 взвешиваний используя наивный $%O({n^2})$% метод выше описанный. А про скорость QuickSort и MergeSort я знаю но обьяснить проще на обычном наивном методе.
(31 Май '15 4:06)
void_pointer
@void_pointer: ясно, что учитываются все случаи, и речь идёт о процедуре, требующей наименьшего количества взвешиваний, и позволяющей упорядочить по весу любые $%n$% монет. Подход, конечно, можно считать компьютеризированным. Важно, чтобы процедура работала для любого случая, а не только для "удачного". При этом получается, что $%O(n)$% -- оценка заниженная (потому что в "плохом" случае этого количества не хватит), а оценка порядка $%C_n^2$% будет завышенной, потому что есть лучшие способы. Я уже говорил, что для 4 монет хватает 5 взвешиваний -- это известная олимпиадная задача.
(31 Май '15 4:24)
falcao
@falcao Я ее рассматривал чисто с точки зрения компьютеризированного подхода, так как считаю что лучший способ доказать чтото это взять какой нить алгоритм и описать все его действия на каком либо примере. Если задачка учитывает любое начальное расположение монет то само собой 20 не получится если конечно вы не изобретете алгоритм который даже в худшем случае справится за 20 сравнений.
(31 Май '15 4:34)
void_pointer
@void_pointer: постановка задачи здесь достаточно ясна. Она, кстати, в общем виде не решена, то есть для заданного $%n$% не известно, какое число взвешиваний будет оптимальным. Это подсчитано только для малых значений $%n$%, а также известны оценки снизу и сверху. "Само собой" здесь не следует ничего: если утверждается, что какого-то числа взвешиваний заведомо не хватит, это надо доказывать.
(31 Май '15 4:56)
falcao
А что такого особого в этой задачке? По мойму любой программист решит ее за пару минут. Монеты рассматриваем как массив с натуральными числами, весы как кондиционную логику сравнения элементов массива. Далее берем любой известный алгоритм для сортировки целых чисел и вот вам решение. Для таких задач есть 2 важных фактора Best Case (лучший случай) то есть когда требуется минимальное кол-во шагов и Worst Case (худший случай) то есть когда потребуется максимальное кол-во шагов.
(31 Май '15 5:05)
void_pointer
@void_pointer - я вот только сейчас добрался до этой задачи и этого диалога. Разница между программистом и математиком - в постановках задачи. Математик спрашивает "какого числа взвешиваний заведомо хватит", а потом комментирует "в общем виде задача не решена". Программист спрашивает "хватит ли $%O(n\log n)$%" и радостно потирает ручки: "конечно, хватит, это же стандартная сортировка". Поэтому для математика задача нетривиальна, а для программиста - тривиальна. Это просто две разные задачи.
(4 Авг '15 19:22)
knop
показано 5 из 9
показать еще 4
|
Откуда задача?
@falcao Насчет этой ссылки - https://oeis.org/A001768, какую именно статью нужно прочесть? Насчет кол-ва сравнений merge sort вроде nlogn тут подтверждают - http://stackoverflow.com/questions/8535540/exactly-how-many-comparisons-does-merge-sort-make . Но эта задача исследовательского типа, потому что никто не знает если кто-то сможет в будущем придумать алгоритм который бы смог отсортировать массив целых чисел сделав сравнений не больше чем удвоенное кол-во элементов данного массива. На сегодняшний день для всех случаев это невозможно. Для частных случаев возможно а для всех нет.
@void_pointer: там довольно большой список литературы, который показывает, что сама проблема достаточно сложна. Ни на какую конкретную статью я при этом не ссылался -- в каждой из них может быть какая-то полезная информация, если кто-то детально интересуется.
Хочу также отметить, что специфика работы конкретных алгоритмов, используемых на практике -- это не то же самое, что математическая задача, с этим связанная. Для алгоритмов "классического" типа важно то, чтобы они асимптотически работали достаточно быстро. Но это не означает их оптимальности строгом смысле, с точностью до единиц.
@void_pointer: судя по всему, у Кнута в томе 3, параграф 5.3.1, есть достаточно подробная информация об этой задаче для произвольного числа монет.
@void_pointer: задача из вступительного экзамена в ШАД Яндекса в 2014 году.(№4)