Задачи по взвешиванию монет

← →
Харченко (2006-04-26 10:56) [0]

Подскажите, есть ли общий алгоритм решения таких задач? Конкретно нужно решить такую задачу: в 12 монетах есть одна фальшивая (неизвестно, легче или тяжелее)ю Как за три взвешивания найти фальшивку?

← →
pavel_guzhanov © (2006-04-26 10:58) [1]

Видел я такой алгоритм в книге Тихомирова "Visual C++6". Давно это было... если надо, дома посмотрю...

← →
palva © (2006-04-26 11:01) [2]

Уж эту-то задачу здешние любители наверняка обсуждали.

← →
McSimm © (2006-04-26 11:04) [3]

эту решали, а вот общий алгоритм - здесь кажется не пробегал

← →
Харько © (2006-04-26 11:06) [4]

А как хоть эта задача решается?

← →
McSimm © (2006-04-26 11:17) [5]

первая половина решения, кажется так :

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

Это баян. С большой бородой...
При желании легко находится в инете. Причём и теория и общий алгоритм.
Здесь уже неоднократно флудились на эту тему :)

Если при первом не равны, то, например так:

Убираем из тяжелой кучки 3 монеты, перекладываем из легкой 3 монеты в тяжелую и добавляем в легкую 3 не Ф. монеты

Взвешиваем
1) Если уравновесились, то Ф тяжелая и находится среди 3х убранных
2) Если весы изменили показания на противоположное, то Ф легкая среди 3х перенесенных монет из легкой кучки в тяжелую
3) Если весы остались в том же состоянии, то Ф - одна из 2х нетронутых монет в кучках.

за одно взвешивание можно любой из этих случаев решить. 1 и 2 случаи - Ф среди 3х монет и известно легче она или тяжелее. Просто взвесить две из них
3й случай тривиален.

В данном случае нужно выполнить 3 взвешивания кучек по 4 монеты.
При соответствующей их перегруппировке это может дать 24 различных исхода (типа > > >, > = = и т.д., всего вариантов таких сочетаний 27, из них 3 невозможны), что и позволяет определить одну из 12 монет и легче она, или тяжелее
Подойдет такая последовательность:
1234/5678
1479/35AB
267A/45BC
Тогда для исходов > < < понятно, что 7 монета легче и т.д.

Задачи по взвешиванию монет Найти похожие ветки