theJam.ru
|
Разделы:
Lifehack12
Данетки95
Игры139
Игры на бумаге17
Книги14
Конкурсы8
Логические задачи346
Люди3
Новости6
Познавательно33
Почемучки14
Притчи4
Работа сайта10
Разное10
Сделай сам10
С праздником16
Страшно жить10
Творчество41
Тесты14
Фото4
Хобби2
Юмор105
 Логические задачи → Сортировка гирек
2 августа 2008 | Добавил: Serge
Пять различных по весу гирек требуется расположить в порядке убывания их веса. В распоряжении, как обычно, только простые весы с двумя чашами. За какое минимальное число взвешиваний это можно сделать? Опишите алгоритм действий.
Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
|
Случайное:
Обсуждения:
Ogra → Инспектор Варнике
Carcass → Тест советского восьмиклассника
Руслан → Слова, оканчивающиеся на “зо”.
ололошин → Незадачливый рыбак
lisicanasta → Инквизиция в наши дни
Ogra → И все же, они вертятся?
SM → Последовательность
Nastya → Бесконечная игра
SpAwN# → Самая трудная игра в мире
Полезное:
Карта сайта:
|
7 августа 2008 в 19:52
Нутром чую, что можно за 7, а пока получается только за 8...
Мое нутро ошибается?
31 августа 2008 в 12:27
За 7 получилось, но не думаю, что это минимум...
однако 6 раз накак не выходит
(алгоритм могу описать, но наверно раное,если он абсолютно верен,а зашифровоть его, как некоторые делают не представляю возможным)
1 сентября 2008 в 13:32
rin, напишите алгоритм для нашей критики :) а зашифровывают обычно просто. читайте ЛС.
1 сентября 2008 в 17:01
Хорошо! В общем вот:
1. взвесим сначала эти пары \12/-\34/ к примеру вторая пара тяжелее
2. затем взвешиваем \1/-\2/ пусть тяжелее 2
3. взвешиваем \3/-\4/ тяжелее 4
4. теперь взвесим лёгкую гирю из "тяжелой" пары(3) с тяжелой гирей из "лёгой"(2) \3/-\2/ по традиции пусть тяжелее 3
5. самое интересное с чем взвесить 5 гирю? Взвесим её с 3, а вот тут могут возникнуть два различных исхода
5а. \5/-\3/ тяжелее 5
6а. \5/-\4/ без разницы, что тяжелее, задача решена за 6 взвешиваний! Но может и так:
5б. \5/-\3/ тяжелее 3
6б. \5/-\2/ тяжелее 2 (если легче,то задача решена)
7б. \5/-\1/ задача решена
Не дай Бог опять что-нибудь промаргал)
1 сентября 2008 в 18:23
rin, а почему Вы не рассматриваете наихудший вариант, когда \12/ == \34/?
И еще, рассмотрим вариант гирек \12/ - \34/
1. определили, что 34 тяжелее
2. Определили, что 2 тяжелее 1
3. Определили, что 4 тяжелее 3
4. а теперь по Вашему алгоритму мы определяем 3 и 2. Определили, что 3 тяжелее 2, а если 2 тяжелее 3? Получаем 2>3, 2>1 и 4>3, но мы не знаем как относятся 1 и 3 и как относятся 2 и 4. Для примера рассмотрите вариант весов гирек 3+4 и 1+7.
1 сентября 2008 в 18:49
Да об этом не подумал...
это значительно усложнит нашу жизнь! Гирьки различные и впинципе может и произойти такая комбинация, надо подумать, существуют ли в реале такие пары гирек, они же стандартизованны и возможно таковых не найдётся...
1 сентября 2008 в 21:12
Я знаю 2 алгоритма: один носит имя пузырька, а другой не помню как, но там все попорядку сравниваются, пока не отсортируются. :) Кажется так.
1 сентября 2008 в 23:27
Предыдущее моё замечание касалось первой части замечания SusAnnы
По поводу второй части:
мы ведь берём лёгкую гирю из тяжёлой пары, а тяжёлую гирю из лёгкой, поэтому если вдруг выйдет 2>3 то гирьки расположатся по убыванию массы так: 4>2>...(это уж точно), а затем действительно возникает ещё одно лишнее взвешивание \1/-\3/...
тогда тоже только 8
2 сентября 2008 в 13:37
вооот, за 8 я уже давно решила, но вот почему-то кажется что можно за 7 по одной такой логике интересной, выношу свои мысли на о(б)суждение:
Всего вариантов расположения гирек 5! = 125. Обозначим результат сравления "больше" как "1", а "меньше" - "0". Таким образом, после n случаев сравнения мы получим некоторое число в двоичном представлении. Так вот, чтобы однозначно по этому двоичному числу определить выбранное разположение гирек необходимо 7 измерений (т.к. 2^7 = 128, и 3 двоичных числа сравнений - запрещенные комбинации, то есть такие результаты, которых быть не может). Вопрос в том, чтобы найти такую последовательность сравнений, в которой ни один результат не выводился из другого (например 2>3, 3>1, то что 2>1 очевидно и такое измерение будет лишним).
2 сентября 2008 в 22:13
Такой вариант я попробовал(обозначил наконец гирьки буквами A B C D E)
A>B
C>D
D>B в противном случае ситуация будет симметричной
A>B<D<C
остается еще 4 взвешивания, начал просчитывать варианты и при некоторых раскладах вылазеет 5 взвешивание...
Кстати не сказал: четвёртое взвешивание сделал А с Е, а затем в одном случае начинал взвешивать А с С, в другом Е с С...
2 сентября 2008 в 22:14
не то жирным выделил:)
3 сентября 2008 в 13:55
rin, ну и опять та же ошибка...
"A">"B", "C">"D"
1. "D">"B" => "A">"B"< "D"<"C", НО! отсюда не известно "A">"D"? и "A">"C"?
2. "D"< "B" => "A">"B">"D", НО! не известно "C">"B"?
Блин, это не Вы не то жирным выделили, это надпись <"B" (только без кавычек) воспринимает как тег "жирный" :)
3 сентября 2008 в 19:27
Я понимаю что ситуация с А(в первом случае) не ясна, поэтому и говорю, что следующим шагом взвешиваю А с Е , а потом в зависимости, что тяжелее либо А, либо Е, взвешиваю поочередно эту гирьку с гирьками D, C.
3 сентября 2008 в 20:17
что-то я Вас не пониамю... Можно весь алгоритм в студию
3 сентября 2008 в 21:05
Я целый лист А4 изрисовал, а итог всё равно 8, так что думаю не стоит...
Гирьки, видимо, не "моё" :)
16 сентября 2008 в 17:02
Предлагаю следующее решение:
-Первое взвешивание: сравним любые 2 из 5 данных предметов. Пусть A - более легкий, а B - более тяжелый предмет. Тогда результат первого взвешивания запишем в виде A<B (читается: «A легче В»).
-Второе взвешивание: сравним два других предмета и обозначим более легкий D а более тяжелый - E: D<E.
Пятый предмет обозначим C.
-Третье взвешивание: сравним предметы B и E. Обе возникающие здесь возможности приводят к аналогичным рассуждениям, поэтому мы ограничимся рассмотрением случая B<E. В итоге после трех взвешиваний мы знаем, что A<B<E и D<E.
-Четвертое взвешивание: сравним пятый предмет C с предметом B. Необходимо различать два случая:
а) B<C;
б) C<B.
В первом случае (B<C)
A<B<E, D<E и B<C.
-Пятое взвешивание: сравним предметы C и E. Здесь также необходимо различать два возможных случая: E<C или C<E.
Если A<B<E<C, то место предмета D, более легкого, чем E, можно определить, сравнив A с D и B с D. Таким образом, для полного упорядочения пяти предметов по весу в этом случае необходимо произвести 7 взвешиваний.
В случае A<B<C<E для определения места D также достаточно произвести два взвешивания, а именно: сначала сравнить D с B, а затем в зависимости от результата взвешивания сравнить D либо с A либо с C. В итоге мы снова производим 7 взвешиваний.
16 сентября 2008 в 19:20
2 сентября 2008 в 22:13 размышлял подобно, но какого то черта взвешивал 5й элемент(4е взвешивание) с крайней по весу гирькой А! Какого чёрта не догадался взвешивать её с какой-нибудь стоящей внутри гирькой?
17 сентября 2008 в 10:55
Все нормально, все свои.
rin именно Вы и другие на 99,9% решили данную задачи ну потом осталось самая малость.
23 сентября 2008 в 19:01
А Serge так и не удосужился ни прокомментировать ответы публики, ни правильный ответ дать на задачу :(
У него самого-то есть правильное решение этой задачи?
Так каково минимальное количество подходов и как полагается правильно их взвешивать?
23 сентября 2008 в 19:19
Pantheon, сомневаться в правильности своего решения может только тот, кто не просчитал другие варианты :)
23 сентября 2008 в 20:23
Pantheon, а я не знаю ответ, вместе с вами думаю
31 октября 2008 в 19:25
медианная сортировка даёт 8
. +1 сорт =>
.. +2 сорт =>
... +2 сорт =>
.... +3 сорт =>
..... done
мидиана не оптимальна, ибо 1 к 1 cmp
1 ноября 2008 в 19:30
x4m, чет я не понял что вы хотели сказать :)
4 ноября 2008 в 16:34
я описал сортировку близкую к qsort, которая допускает сравнение элементов 1к1
с допущением сравнения 2к2 один из шагов можно соптимиздить на одно сравнение. будет 7
3 декабря 2008 в 16:49
гм..
я так понял что решение за 7ходо так и не описано?
1) 1<2 (берем любые две и в зависимости от показаний нумеруем легкую 1 тяжелую 2)
2) 4<5 (аналогично берем еще 2 гири)
3) 25 то {452})
для определенности будем считать {125} (второй случай анологично)
т.е грубо говоря мы определили порядок 3 гирь
теперь возьмем гирю 3 (ни разу не взвешанную и определим ее мемто минимум 2 взвешивания)
4) 3>2
5) 3<5 {1235}
теперь осталось установить 4 при этом из 2) известно что оно меньше 5 т.е нужно поределить место чреди {123}
6) 2<4
7) 3<4 {12345}
24 июня 2011 в 01:09
SusAnna пишет:…
вооот, за 8 я уже давно решила, но вот почему-то кажется что можно за 7 по одной такой логике интересной, выношу свои мысли на о(б)суждение:
Всего вариантов расположения гирек 5! = 125.
SusAnna, 5! = 120. Это конечно не влияет на Ваше рассуждение.
А комментарии видно никто не читает!?