Взвешиваение монет

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Vanush
Сообщения: 50
Зарегистрирован: 10 янв 2008, 22:18

02 июн 2008, 17:01

Есть 12 мячей.Один из них меньше или больше по массе(мы не знаем меньше или больше) чем другие.У вас есть весы.Можно свешивать три раза.
Найдите мяч который меньше или больше по массе(мы не знаем меньше или больше) чем другие.
Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

02 июн 2008, 18:27

Вопрос точно не по С++. Переношу в другой раздел.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

02 июн 2008, 18:34

Задача старая, ориентирована на знание троичной системы. В теории можно найти мяч даже среди 13(!). В инете довольно много страниц и решений этой задачи.
It's a long way to the top if you wanna rock'n'roll
BHy4ok
Сообщения: 229
Зарегистрирован: 01 май 2007, 09:03
Откуда: г.Находка
Контактная информация:

02 июн 2008, 18:53

Задача похожа про монеты, только там было 2 хода.
1) Бъешь 6-6. Затем одну из них отсеиваешь.
2) Взвешываешь 3-3. Также отсеиваешь.
3) Взвешываешь 1-1 (один просто откладываешь в сторону).
Если равны тогда отложенный шар больше или меньше. Если не равны значит тот, что на весах исходный.
< L3X. (ICQ: 8721378, Mail - l3x@list.ru)
Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

02 июн 2008, 19:01

BHy4ok, подумайте, это не так - потому что неизвестно тяжелее она или легче. Задача отнюдь непростая.
It's a long way to the top if you wanna rock'n'roll
Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

02 июн 2008, 19:19

Смысл следующий. Разбить монеты на 3 группы по 4 монеты. Произвести два взвешивания. 1-я группа со 2-й, затем 2-я группа с 3-й. Полученной информации будет достаточно для того, чтобы сказать в какой именно группе находится фальшивая монета а, также, для того чтобы выяснить больше или меньше фальшивая монета весит, чем настоящая (подробнее не буду, просто проверь все варианты, и поймёшь, что это так).

[Это не читай, если не хочешь решать с 13-ю монетами] Если два взвешивания дали два раза равные чаши весов, то фальшивая монета 13-я. Больше она весит или меньше, чем настоящая, можно узнать путём последнего сравнения с эталонной монетой из отброшенной массы монет.

Если группу из 4-х монет с фальшифкой смогли выделить, то делим группу пополам и ракладываем на чаши весов (на одной чаше 2 монетки, и на другой 2). Одну (любую) монетку меняем с эталонной монеткой из оставшихся. Последнее взвешивание тоже даёт однозначное определение фальшивой монетки (нужно рассмотреть три случая >, <, =, а также вспомнить, что мы уже знаем больше весит фальшивая монета, чем настоящая, или меньше)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

02 июн 2008, 19:22

BHy4ok, для бинарного поиска информации недостаточно. При первом же взвешивании ты не смошь определить какие монеты следует отбросить по той причине, что ты не знаешь больше весит фальшивая монета настоящей или меньше.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
Vanush
Сообщения: 50
Зарегистрирован: 10 янв 2008, 22:18

02 июн 2008, 20:32

Когда мы группу из 4-х монет с фальшифкой смогли выделить уже сделали 2 взвешивания,потом делим группу пополам и раскладываем на чаши весов (на одной чаше 2 монетки, и на другой 2) здесь мы сделали уже 3 взвешивания,а когда монетку меняем с эталонной монеткой из оставшихся будет уже 4?????????????
Но надо 3.
chur
Сообщения: 195
Зарегистрирован: 17 фев 2004, 10:44
Откуда: Riga, Latvia

02 июн 2008, 21:01

Romeo писал(а):Если группу из 4-х монет с фальшифкой смогли выделить, то делим группу пополам и ракладываем на чаши весов (на одной чаше 2 монетки, и на другой 2). Одну (любую) монетку меняем с эталонной монеткой из оставшихся. Последнее взвешивание тоже даёт однозначное определение фальшивой монетки (нужно рассмотреть три случая >, <, =, а также вспомнить, что мы уже знаем больше весит фальшивая монета, чем настоящая, или меньше)

По-моему, одного взвешивания для группы из 4 монет может не хватить. Допустим, выянили, что фальшивка тяжелее и в последнем взвешивании оказалась тяжелее чаша, где нет эталонной монеты. Остаются две монеты
chur
Сообщения: 195
Зарегистрирован: 17 фев 2004, 10:44
Откуда: Riga, Latvia

02 июн 2008, 22:11

Я предлагаю так.
Делим на три кучи: А(4), В(4) и С(4). (в скобках - кол-во монет в куче)
1. А(4) и В(4) - сравниваем.
Возможные варианты - а) равно и б) неравно

а) Фальшивка куче С(4).
2а. Сравниваем две монеты из С(4) и две стандартные.
После этого мы знаем 2 монеты, одна из которых фальшивка (если второе взвешивание покажет "равно", то фальшивка в тех двух из кучи С(4), которые не взвешивали, если "неравно", то в тех двух которые взвешиавли)

3а. Сравнением любой из двух монет со стандарной отпределяем фальшивку


б) Фальшивка в куче А(4) или В(4).
Делаем следующие кучки по пять монет
1-ая, Д1(5): три монеты из А(4) и две монеты из В(4)
2-ая, Д2(5): одна монета из А(4) и вся куча С(4)

2б. Сравниваем Д1(5) и Д2(5)
Врзможные ваприанты в), г) и д)

в) если Д1(5) равно Д2(5) то фальшивка в двух монетах из В(4), которые не взвешивали
3в. Сравнением любой из двух монет со стандарной отпределяем фальшивку


г) Если Д1(5) тяжелее чем Д2(5), а А(4) тяжелее чем В(4) (из первого взвешивания), то фальшивка в трех монетах из А(4), попавших в кучу Д1(6) и фальшивка тяжелее
3г. Сравнением между собой любых двух монет из этих трех отпределяем фальшивку

д) Если Д1(5) тяжелее чем Д2(5), а А(4) легче чем В(4), то фальшивка либо в двух монетах из В(4), попавших в кучу Д1(5) и фальшивка тяжелее, либо фальшивка это монета из кучи А(4), попавшая в кучу Д2(5), и она легче
Т.о. сейчас мы наверняка знаем 3 монеты (разбитые на А"(2)+В"(1)), в которых фальшивка, при этом если фальшивка в группе А"(2), то она тяжелее, а если одна (В"(1)) то легче.
3д. Сравниваем одну монету из А"(2) вместе с монетой В"(1) с двумя стандарными.
Если равно, то фальшивка - оставшаяся монета А"(2)
Если одна монета из А"(2) + монета В"(1) тяжелее стандартных - фальшивка монета из группы А"(2)
Если одна монета из А"(2) + монета В"(1) легче стандартных - фальшивка В"(1)
Закрыто