Есть $%10$% монет разного веса и некоторые весы. При помощи одного взвешивания на весах можно узнать для выбранных двух монет, какая тяжелее. Можно ли за $%20$% взвешиваний узнать, в каком порядке монеты идут по весу?

задан 30 Май '15 23:20

Откуда задача?

(31 Май '15 5:12) void_pointer

@falcao Насчет этой ссылки - https://oeis.org/A001768, какую именно статью нужно прочесть? Насчет кол-ва сравнений merge sort вроде nlogn тут подтверждают - http://stackoverflow.com/questions/8535540/exactly-how-many-comparisons-does-merge-sort-make . Но эта задача исследовательского типа, потому что никто не знает если кто-то сможет в будущем придумать алгоритм который бы смог отсортировать массив целых чисел сделав сравнений не больше чем удвоенное кол-во элементов данного массива. На сегодняшний день для всех случаев это невозможно. Для частных случаев возможно а для всех нет.

(31 Май '15 6:14) void_pointer

@void_pointer: там довольно большой список литературы, который показывает, что сама проблема достаточно сложна. Ни на какую конкретную статью я при этом не ссылался -- в каждой из них может быть какая-то полезная информация, если кто-то детально интересуется.

Хочу также отметить, что специфика работы конкретных алгоритмов, используемых на практике -- это не то же самое, что математическая задача, с этим связанная. Для алгоритмов "классического" типа важно то, чтобы они асимптотически работали достаточно быстро. Но это не означает их оптимальности строгом смысле, с точностью до единиц.

(31 Май '15 6:40) falcao

@void_pointer: судя по всему, у Кнута в томе 3, параграф 5.3.1, есть достаточно подробная информация об этой задаче для произвольного числа монет.

(31 Май '15 7:12) falcao

@void_pointer: задача из вступительного экзамена в ШАД Яндекса в 2014 году.(№4)

(31 Май '15 15:40) stander
10|600 символов нужно символов осталось
1

Нельзя. Даже 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 Опишите ваш алгоритм сравнения? Я свой наивный описал) Для случая если монеты изначально вам данны в возрастающем порядке, то сравнивая $$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

@falcao

Кол-во взвешиваний будет зависить от того в каком порядке вам данны монеты и какой алгоритм вы используете. Если на практике вы сможете выпонить все ходы алгоритма 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

@falcao

А каким методом вы пришли к выводу что минимальное кол-во взвешиваний даже в худшем случае не меньше 21? Ведь это намного быстрее $%O(n{\log _2}n)$% что даст 33-34 взвешивания в худшем случае. Само собой что все сводится к перестановкам и сравнению но чего-то я не пойму через какой алгоритм вы нашли что 22 взвешивания хватает даже для случая когда все 10 монет даны вам в обратном по возрастанию порядке?

(31 Май '15 4:40) void_pointer

@falcao

Вот допустим перед вами на столе лежат 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
10|600 символов нужно символов осталось
1

Можно разобрать более простой случай (на примере):

Рассмотрим 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

изменен 31 Май '15 4:56

@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

@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

@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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×19

задан
30 Май '15 23:20

показан
1740 раз

обновлен
4 Авг '15 19:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru