Простенькая задачка для всех

← →
Johnmen (2002-04-23 15:13) [0]

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

← →
gek (2002-04-23 15:23) [1]

Ну я так думаю минимум за три, если повезет
1.Взвешиваем первую монету.
2.Взвешиваем вторую монету.
3.Если вес не равен, значит одна из них фальшивая
4.Взвешиваем третью и определям первая или вторая фальшивая

← →
Johnmen (2002-04-23 15:34) [2]

Не понял...? Монет-то 12 (двенадцать) !

← →
McSimm (2002-04-23 15:38) [3]

>gek © (23.04.02 15:23)

Я так понимаю "если повезет" тут не подходит. Вопрос за какое мин. кол-во взвешиваний однозначно можно ее найти

← →
sudiv (2002-04-23 15:38) [4]

3 кучи по 4 монеты
за 1 взвешивание определяем кучу с фальшивой

осталось 4 монеты где 1 фальшивая

выбираем 2 - 2 взвешивание.
остальные 2 - третье.

Итого три, но это навскидку, может можно и за 2.

← →
gek (2002-04-23 15:38) [5]

Вес монеты настоящей конечно не должен быть равес весу настоящей.
Ну если вес первой не равен весу второй, значит одна из них фальшивая. Для ее определения взвешиваем третью.
Ну этот вариант подходит только если вес двух первых взвешиваемых монет не совпадает.

А может я вопрос немного не понял?

← →
sudiv (2002-04-23 15:39) [6]

Вообще эти задачи решаются в школе классе в 6

По крайней мере я решал когда учился в школе

← →
sudiv (2002-04-23 15:41) [7]

Насчет того легче или тяжелей это отдельный вопрос. То что другого веса это факт, иначе взвешивай не взвешивай ничего не выйдет.

← →
sudiv (2002-04-23 15:44) [8]

Тот алгоритм если известно что она тяжелее или легче.

Для выяснения тяжелее или легче монета фальшивая
надо еще одно взвешивание с любой монетой из первых двух куч

Итого 4 взвешивания.

← →
MBo (2002-04-23 16:00) [9]

4 взвешивания - 3 кучи,за два раза определяем легче или тяжелее и в какой куче, дальше делим 2 раза пополам

← →
McSimm (2002-04-23 16:00) [10]

>sudiv © (23.04.02 15:38)
>за 1 взвешивание определяем кучу с фальшивой
Как ?
Если окажется что на весах одна кучка тяжелей другой?

← →
Johnmen (2002-04-23 16:13) [11]

Небольшая подсказка -
1.обратите внимание на тип весов
2.в процессе взвешиваний напрягайте свою память...
:-)

← →
sudiv (2002-04-23 16:39) [12]

McSimm © (23.04.02 16:00)
>sudiv © (23.04.02 15:38)
>за 1 взвешивание определяем кучу с фальшивой

Нет, это если известно, что монета тяжелее или легче.
Если неизвестно, то надо много помнить. Что из какой кучи бралось и сравнивать.

← →
Johnmen (2002-04-23 17:08) [13]

Какие будут еще варианты, уважаемые господа программеры ?

← →
McSimm (2002-04-23 17:12) [14]

> Какие будут еще варианты, уважаемые господа программеры ?

В каком смысле?
Вариантов на 4 взвешивания можно придумать достаточно много.

Что, разве есть вариант на 3 ???

← →
Malder (2002-04-23 17:42) [15]

А что вы обсуждаете ? sudiv уже ответил на вопрос.

Минимальное число взвешиваний - три.
Если кто не понял его ответа - расстолковываю.

Делим 12 монет на 3 кучки по 4 монеты в каждой.

1) Взвешиваем две кучки. Если перетягивает одна - значит фальшивая в этой куче. Если другая - значит в той. Если вес одинаковый, то монета в куче, котороую мы не взвешивали. Далее.

2) Осталось 4 монеты и 2 попытки.
Отбираем две кучи из 2-ух монет.
Взвешиваем. Определяем в какой куче фальшивка.

3) Остается две монеты и одно взвешивание. Тут уже и объяснять не надо =)

← →
Johnmen (2002-04-23 17:46) [16]

>McSimm © : есть вариант короче...:)
>Malder © : С чего ты взял, что...Если перетягивает одна - значит фальшивая в этой куче...

← →
McSimm (2002-04-23 18:00) [17]

>Johnmen ©
Я правильно понимаю, что весы позволяют только сравнить (легче или тяжелее), но не позволяют определить насколько.

← →
Malder (2002-04-23 18:01) [18]

Ивзиняюсь. Я не увидел приписки "сказать, легче она или тяжелей настоящей ?"

Тогда 4 взвешивания.

Алгоритм долго описывать, да еще есть варианты.

Смысл тот же.Делим 12 монет на 3 кучки по 4 монеты в каждой.

Потом сравниваем одну из куч с двумя остальными. Отсюда можно узнать в какой куче из 4 монет лежит фальшивая и тяжелее или легкче она настоящей. Потом двуия взвешиваниями определяем фальшивку. Итого: 4 взвешивания.

P.S. Если есть решение из 3 попыток (хотя это нереально), то скажи об этом, но не говори само решение. Я поломаю себе голову над этим...

← →
Johnmen (2002-04-23 18:08) [19]

Существует решение за 3 взвешивания, и это минимум (реальный !).

← →
Лёша (2002-04-23 18:14) [20]

> Существует решение за 3 взвешивания, и это минимум (реальный
> !).

Истинная правда.

← →
Malder (2002-04-23 18:47) [21]

Я подумал - нельзя определить за 3 взвешивания. То есть, если повезет, то можно и за два. Но при ЛЮБОМ раскладе нельзя определить какая фальшивка и тяжелее или легкче настоящей она...
прошу вас перепроверить ваш алгоритм решения, так как такое невоможно...

← →
Johnmen (2002-04-23 18:53) [22]

>Malder © : Алгоритм железный - за 3 взвешивания ! При любых раскладах т.е. независимо от везения ! :)

← →
Johnmen (2002-04-23 19:00) [23]

>Malder © : Ты же фанат StarCraft ! Как и я !
А там для победы просто необходима бетонная логика и нестандарная стратегия + продуманная тактика....

← →
Malder (2002-04-23 19:25) [24]

Johnmen ну если алгоритм железный, то погодь с ответом. Я еще помучаюсь.

P.S. И вообще название топика не соответствует содержанию =)

← →
Лёша (2002-04-23 19:41) [25]

1. Взвешиваем 4+4. Если чашечки в равновесии, то из оставшихся 4-х монет определить фальшивую за 2-а раза легко.

2. Допустим левая перевешивает. Снимаем с неё 2-е монеты, откладываем их в сторону; перекладвыаем в левую из правой чашки любые две монеты; из нетронытых монет на левой чашке перекладываю на правую одну монету.

Если весы уравновесились - среди отложенных двух одна фальшивая. 3. Её можно определить взесив любую из них с настоящей.

Если остались в том же состоянии - фальшивая находится среди тех, что небыли тронуты. Т.е. одна в левой внизу, две в правой вверху. 3. Взвешиваем правые две. Если фальшивая среди них, то она будет легче.

Если чашки весов поменялись - Фальшивая находится среди тех, что были перемещены. Одна левая вверху, две правые внизу. 3. Взвешиваем правые две. Если фальшивая среди них, то она будет тяжелее.

← →
Лёша (2002-04-23 19:49) [26]

Сори, труднее описать, чем придумать.
Последний абзац должен быть такой:

Если чашки весов поменялись - Фальшивая находится среди тех, что были перемещены. Две левых вверху, одна правая внизу. 3. Взвешиваем левые две. Если фальшивая среди них, то она будет тяжелее.

← →
Malder (2002-04-23 20:00) [27]

Лёша, алшоритм неправильный с самого начала. "Взвешиваем 4+4. Если чашечки в равновесии, то из оставшихся 4-х монет определить фальшивую за 2-а раза легко." - а вот в том то и дело, что невозможно.

Задача сводится к тому, что есть 4 монеты и два взвешивания. И что вы будете делать ? Вы за два раза можете определить какая фальшивая. Но не сможете определить легкче или тяжелее она настоящей (если ошибаюсь - попробуйте опровергнуть)...

Все таки мне кажется, что задача нерешаемая. Я могу определить за 3 хода фальшивку. Но не могу сказать легкче она или тяжелее настоящей...

← →
McSimm (2002-04-23 20:01) [28]

>1. Взвешиваем 4+4. Если чашечки в равновесии, то из оставшихся 4-х монет определить фальшивую за 2-а раза легко
А как?

← →
McSimm (2002-04-23 20:19) [29]

← →
Malder (2002-04-23 20:45) [30]

McSimm, вот тут ты не прав. Можно за три хода найти фальшивку...

← →
Malder (2002-04-23 20:51) [31]

...но легкче она или тяжелее не определить...

P.S. Я сдаюсь

← →
Лёша (2002-04-23 21:20) [32]

2 Malder © (23.04.02 20:00)

> Задача сводится к тому, что есть 4 монеты и два взвешивания.
> И что вы будете делать ? Вы за два раза можете определить
> какая фальшивая. Но не сможете определить легкче или тяжелее
> она настоящей (если ошибаюсь - попробуйте опровергнуть)...

ПРОБУЮ ОПРОВЕРГНУТЬ.

1. На левую чашку ложим две монеты, на правую одну плюс добавляем на правую не фальшивую монету.

Если равновесие - фальшивка та, что не взвешивали. 2. Взвешиваем фальшивку с настоящей. (это для определения, легче она или тяжелее).

Допустим левая чашка перевесила.
2. Взвешиваем две монеты из тех, что на левой. Если среди них фальшивка, то она тяжелее. Если они равны, то фальшивка на правой чашке и она легче.

P.S. Русские не здаются.

← →
Malder (2002-04-23 23:15) [33]

>Лёша, Ок.Согласен алгоритм проверки 4-х монет верный.

Просматриваю основной алгоритм...

← →
Malder (2002-04-23 23:30) [34]

Лёша ! Гениально !!! БРАВО ! Основной алгоритм правильный. Ты все таки сделал это =) я б ни за что не догадался !

P.S. Johnmen, осталось выяснить, у тебя алгоритм тот же ?

← →
Di_wind (2002-04-24 00:12) [35]

2 Лёша
Снимаю шапку прерд вами сэр.

← →
Мальфет (2002-04-24 09:00) [36]

Всё на много проше.
0. ГОСПОДА!!!! Тяжёлая монета не может быть фальшивой!!! А если фальшивая тяжелее, то, пордон, эта фальшивка дороже настоящих монет!!!
1. 6 + 6
2. 3 + 3
3. 1 + 1 - если равновесие, то фальшифка - оставшаяся монета!

← →
McSimm (2002-04-24 10:13) [37]

← →
Malder (2002-04-24 18:58) [38]

Johnmen, так каков ваш алгоритм ?

ау-у-у

← →
Di_wind (2002-04-24 20:08) [39]

2 Мальфет "ГОСПОДА!!!! Тяжёлая монета не может быть фальшивой!!! А если фальшивая тяжелее, то, пордон, эта фальшивка дороже настоящих монет!!!"
Толковый ты парень.... :)
Если бы она не могла буть тяжелле условие задачи было так и поставленно бы. Посмотри алгоритм Леши там нету левых дагадок, что может а что нет...и вообще правда куда-это Johnmen пропал.

← →
igorr (2002-04-25 07:08) [40]

Тоже решил сабж. И полностью согласен с Лешей.
Только хочу предложить более упрощенный алгоритм на

McSimm © (23.04.02 20:01)
>1. Взвешиваем 4+4. Если чашечки в равновесии, то из оставшихся 4-х монет определить фальшивую за 2-а раза легко
А как?

Оставшиеся четыре монеты кладем на левую чашу.

1. Откладываем одну. И кладем 3 настоящих на правую чашу.
Если равны, то фальшивая та, которую отложили.
Если не равны, то фальшивая находится в левой чаше. Причем если левая чаша легче, то фальшивка легче и наоборот.

2. На левой чаше осталось три монеты. Взвешиваем любые две и определяем фальшивку.

Простенькая задачка для всех Найти похожие ветки