Имеется 25 гирек различной массы. Какое минимальное количество взвешиваний на чашечных весах необходимо для того, чтобы найти самую тяжёлую и самую лёгкую гирьки?

задан 11 Май '15 16:03

Задача с действующего конкурса до 01 июня - http://kvantik.com/concurs.html

(11 Май '15 17:23) EdwardTurJ

@EdwardTurJ: задача конкурса несколько отличается. Там 18 гирек, и надо за 25 взвешиваний определить "крайние". Здесь же гирек 25, а сколько взвешиваний нужно -- не сказано. Это может быть сложнее.

(11 Май '15 20:52) falcao

@EdwardTurJ: задача из "Квантика" совсем простая: там проходит самый естественный план взвешиваний. А вот в общем случае получение нижних оценок представляется весьма нетривиальным. Скажем, в задаче об упорядочении гирек по весу за наименьшее число взвешиваний, насколько я знаю, решение для общего случая не известно.

(12 Май '15 16:52) falcao
10|600 символов нужно символов осталось
6

В общем случае для $%2n$% монет ответ равен $%3n-2$%.
Алгоритм:

1) сравним все монеты попарно - $%n$% взвешиваний;

2) среди $%n$% более тяжелых монет найдем самую тяжёлую $%(n-1)$%;

3) среди $%n$% более легких монет найдем самую легкую $%(n-1)$%.
Итого ровно $%3n-2$%.

Нижняя оценка: рассмотрим Соперника, который действует против любого алгоритма взвешиваний следующим образом. Соперник помечает каждую монетку, которая может оказаться самой тяжёлой, знаком $%+$%, и каждую монетку, которая может быть самой лёгкой, знаком $%-$%. Вначале каждая монетка помечена дважды, т.е. всего есть $%2 \cdot 2n=4n$% пометок. В конце пометка $%"+" $% должна остаться всего у одной монеты, и пометка $%"-"$% тоже должна остаться только одна. Значит, по ходу действия алгоритма должны быть стёрты $%4n-2$% пометки. Теперь вопрос в том, КАК именно Соперник их стирает.

1) Если алгоритм пробует сравнить две дважды помеченные монетки, то Соперник произвольно назначает одну из них более тяжёлой и стирает у нее $%"-"$%, а другую назначает более легкой и стирает у нее $%"+"$%.

2) Во всех остальных случаях Соперник действует так, чтобы стирать не более одной пометки. Например, если алгоритм сравнивает монету с двумя пометками и монету с одной пометкой $%"-"$%, то Соперник сохраняет пометку $%"-"$% у второй монеты и стирает ее у первой, т.е. объявляет, что первая монета оказалась тяжелее второй.

Действий типа 1) не может быть более $%n$%, потому что каждое из них уменьшает число дважды помеченных монет на 2, а всего таких монет было $%2n$%. Действия типа 2) стирают не более одной пометки. Поскольку нам нужно стереть всего $%4n-2$%, а действиями типа 1) можно стереть не более $%2n$%, то требуется не менее $%2n-2$% действий типа 2), а всего - не менее $%3n-2$% взвешиваний.

Для нечетного числа монет и алгоритм, и оценка совершенно аналогичны, ответ для $%2n+1$% монеты равен $%3n-1$%.

ссылка

отвечен 5 Июн '15 14:20

изменен 24 Июл '15 22:23

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Каким образом вы отсортируете массив из 25 различных элементов за линейное время, учитывая все случаи начального расположения гирек? Чтобы сравнить каждую гирьку с каждой другой, вам понадобится в худшем случае $%\frac{{{n^2} - n}}{2}$% взвешиваний и в лучшем случае $%n - 1$% взвешивание. Чтобы выполнить пункты 2) и 3) вы должны знать, в каком порядке гири идут по весу, а для этого нужно сначала их отсортировать. То есть все равно все упирается в скорость сортировки гирек по весу. А быстрее, чем $%n\log n$%, учитывая наихудший расклад, это невозможно сделать.

(6 Июн '15 1:09) night-raven
(6 Июн '15 1:14) night-raven
1

Зачем мне сортировать все, когда мне нужно сделать всего N сравнений? Я разбиваю 2N объектов на пары и сравниваю друг с другом две монеты в каждой паре. После этого у меня есть всего N кандидатов в самые тяжелые монеты и N кандидатов в самые легкие. И для нахождения тяжелой/легкой тоже вовсе не нужно делать все сравнения.

(6 Июн '15 1:54) knop

@knop да, вы правы, походу, чтобы найти самую тяжелую и самую легкую, не нужно сортировать. Это я поспешил с выводом.

(6 Июн '15 2:11) night-raven
1

@knop а если бы в условии требовалось найти вторую, третью и т.п. по тяжести гирьку, как бы ваш метод и кол-во сравнений бы изменились?

(6 Июн '15 2:15) night-raven
1

@void_pointer Ну, слегка изменились бы. Задачу о нахождении двух самых тяжелых гирек я вчера тут тоже решал. Наверное, вопрос о добавлении к ним третьей гирьки лучше обсуждать там, а не тут. Там же ответ не 3n/2, а n + Clog(n).

(6 Июн '15 3:57) knop
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×40

задан
11 Май '15 16:03

показан
2310 раз

обновлен
6 Июн '15 3:58

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

по почте:

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

по RSS:

Ответы

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

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