Developing.ru

Есть 12 мячей.Один из них меньше или больше по массе(мы не знаем меньше или больше) чем другие.У вас есть весы.Можно свешивать три раза.
Найдите мяч который меньше или больше по массе(мы не знаем меньше или больше) чем другие.

Вопрос точно не по С++. Переношу в другой раздел.

Задача старая, ориентирована на знание троичной системы. В теории можно найти мяч даже среди 13(!). В инете довольно много страниц и решений этой задачи.

Задача похожа про монеты, только там было 2 хода.
1) Бъешь 6-6. Затем одну из них отсеиваешь.
2) Взвешываешь 3-3. Также отсеиваешь.
3) Взвешываешь 1-1 (один просто откладываешь в сторону).
Если равны тогда отложенный шар больше или меньше. Если не равны значит тот, что на весах исходный.

BHy4ok, подумайте, это не так - потому что неизвестно тяжелее она или легче. Задача отнюдь непростая.

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

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

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

BHy4ok, для бинарного поиска информации недостаточно. При первом же взвешивании ты не смошь определить какие монеты следует отбросить по той причине, что ты не знаешь больше весит фальшивая монета настоящей или меньше.

Когда мы группу из 4-х монет с фальшифкой смогли выделить уже сделали 2 взвешивания,потом делим группу пополам и раскладываем на чаши весов (на одной чаше 2 монетки, и на другой 2) здесь мы сделали уже 3 взвешивания,а когда монетку меняем с эталонной монеткой из оставшихся будет уже 4?????????????
Но надо 3.

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

По-моему, одного взвешивания для группы из 4 монет может не хватить. Допустим, выянили, что фальшивка тяжелее и в последнем взвешивании оказалась тяжелее чаша, где нет эталонной монеты. Остаются две монеты

Я предлагаю так.
Делим на три кучи: А(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)