|
|||||||||||||||||||||||||||||
|
← Студенты
|
Обьявление →
22 апреля 2007
| добавил: Serge
Имеется четыре монеты различных весов. Какое минимальное количество взвешиваний необходимо произвести на рычажных весах (весы без гирь), чтобы расставить монеты в порядке возрастания (или убывания) их масс?
Метки → Математические
| просмотров: 1455
Комментарии:23 апреля 2007 - 09:35
SusAnna (вст)
А у меня получилось 4!
 бе-бе-бе…1) берем по 2 монеты. Здесь могут быть 3 варианта: а)1,2 — 3,4; б)1,3 — 2,4; в)1,4 — 2,3. Теперь взвешиваем 2 кучки (по 2 монеты в каждой). В первых двух случаях одна кучка тяжелее, чем другая, в третьем — они одинаковы. Запомним, которая из кучек тяжелее (или они равны). 2) вешаем монеты из легкой кучки (для 3-го случая все равно из какой). Здесь могут быть варианты: а) 1-2; б) 1-3; в) 2-3 или 1-4. Запомнили, которая монетка легче. 3) то же самое делаем со второй кучкой. Варианты: а) 3-4; б) 2-4; в) 1-4 или 2-3. Запомнили, которая монетка легче. 4) Теперь, если на первом шаге кучки были не равны по весу, то взвешиваем (ВНИМАНИЕ) легкую монету из тяжелой кучки (это может быть 2 или 3) и тяжелую монету из легкой кучки (3 или 2). Соответственно по исходу определяем, кто из них 2, а кто 3, так как легкая монета из легкой кучки — 1, тяжелая монета из яжелой кучки — 4. Теперь рассмотрим вариант, если на первом шаге кучки были равны. Вешаем любые монеты из обеих кучек — либо обе легкие, либо обе тяжелые. Если брали легкие, то та монета, которая легче — 1, оставшаяся из ее кучки — 4, взвешенная та, которая тяжелее — 2, оставшаяся из ее кучки — 3. Если брали тяжелые, то наоборот, (по аналогии) тяжелее — 4, оставшаяся — 1, легче — 3, оставшаяся 2.
действие:
ответить
25 апреля 2007 - 15:49
Vb (вст)
ох неверен твой метод, SusAnna, хоть и ответ верен (если кто меньше чем за 4 не найдёт((-: )
Предположим, что веса монет таковы: m1 = 2 m2 = 3 m3 = 4 m4 = 8 и пусть при раскладывании на кучи у нас получились кучи (m1; m4) и (m2; m3) Взешивая их на шаге1 имеем: (m1; m4) > (m2; m3) Далее (шаг2 и шаг3) определяем порядок внутри куч (m1 < m4 и m2 < m3, соответсвенно) На шаге4 берём m1, как лёгкую монету из тяжёлой кучи и m3, как тяжёлую монету из лёгкой кучи. Сравнив их, получаем (так сказано в шаге4), что m1 стоит на втором месте, а m3 -- на третьем, m2 -- на первом, а m4 -- на четвёртом, то есть получаем такой порядок: m2 m1 m3 m4, что не есть правильно.
действие:
ответить
25 апреля 2007 - 15:58
Vb (вст)
а вот саособ на 4 взвешивания, но другой (позаимствован из алгоритма быстрой сортировки Хоара):
Произвольно выбираем монету. Сравниваем её вес с остальными тремя (3 взвештвания), складывая слева от неё те монеты, что лнгче, а справа -- что тяжелее. Тут возможно два варианта: 1) слева оказалось две монеты, а справа одна -- тогда взвешиваем (четвёртое взвешивание) пару монет слева и упорядочиваем их, в итоге получаем искомый порядок монет 2) слева оказалась одна монета, а справа два -- аналогично взвешиваем (четвёртое взвешивание) пару монет справа, упорядочиваем и получаем искомый порядок
действие:
ответить
|
|
||||||||||||||||||||||||||||
pgt 0.05542 сек. / запросов: 6 / кэширование: включено |
|||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||
1) взвешиваем 1 и 2 монеты. Выбираем из них самую тяжелую.
2) взвешиваем ее и монету №3. Берем тяжелую.
3) взвешиваем ее и монету №4. Берем тяжелую. Допустим, это монета №1. Она самая тяжелая их всех.
4) взвешиваем монеты 2 и 3. Берем легчайшую.
5) взвешиваем ее и монету №4. Берем легчайшую. Допустим, это монета №4. Она — самая легкая.
6) теперь взвесим монеты 2 и 3, чтобы узнать соотношение их весов. Допустим, монета №3 легче.
Тогда соотношение весов(в порядке убывания): №1, №2, №3, №4.
Номера, взятые в качестве «допустим» условны и имеют целью лишь облегчение навигации между монетами.
Итак, я угадаю эту мелодию с 6 нот. Кто меньше? Дерзайте!