Мобильная
версия

Логическая задачка

Дата: Категория: Разное

Сегодня наткнулся на довольно интересную вариацию детской задачи о 12 монетах. Для тех кто не в курсе - напомню.

"Имеется 12 монет и одна из них фальшивая (она легче). Даны весы без гирь. Нужно за минимальное количество взвешиваний определить какая монета фальшивая."

Задача достаточно простая, и с ее решением должен справиться любой школьник. 
Ответ - 3 и думаю решение объяснять не требуется.

Я же наткнулся на чуть измененную задачу и условие в ней звучит практически также

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


За исключением того, что мы не знаем вес фальшивой монеты. Она может быть как легче так и тяжелее.
Вначале я подумал что тоже не сложная задача, решаемая 4мя взвешиваниями. Какого было мое удивление когда я узнал что тут количество взвешиваний не изменилось, и также равно 3.

Тут мне стало интересно.

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

Приступим

Для начала разбиваем монеты на 3 кучки по 4 монеты

oooo oooo oooo

и взвешиваем 2 из них.

Если нам повезло и у нас самый простой вариант

Если чаши весов находятся в равновесии, то монета в 3 кучке. Обозначим взвешенные монеты буквой Н (нормальные), а те 4 монеты, которые мы еще не взвешивали обозначим буквой Х (хрен знает. Шучу, это ИКС)

Теперь взвешиваем их, положив на весы таким образом

НX - XX

Если чаши весов равны, то фальшивая та монета, которая не взвешивалась.
Если поднялась правая чаша весов (ХХ легче) то либо легкая монета на правой части весов, либо тяжелая монета на левой.
Зная это мы можем взвести правую часть, и если эти 2 монеты не равны в весе, то фальшивая более легкая (мы выяснили что если фальшивая среди этих монет то она может быть только легкой)
Если они равны, то фальшивая монета на левой стороне весов.
Аналогично поступаем если правая часа весов тяжелее, только теперь при взвешивании правой части фальшивая монета будет та, которая тяжелее.
Если при взвешивании НX - XX чаши не сдвинулись с места (по весу они равны), то фальшивая монета - 4 из кучки которая не участвовала во взвешивании.

PROFIT!

Если одна из чаш весов перевесила

В таком случае у нас есть следующие группы монет

  • 4 нормальных (в той кучке которую мы не взвешивали нет фальшивых). Обозначим их буквой Н (нормальные)
  • 4 легких (буква Л)
  • 4 тяжелых (буква Т)

Осталось 2 взвешивания.
Теперь взвешиваем их положив на весы следующим образом.

ЛЛТ - ЛЛТ

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

PROFIT!

А если чаши весов (ЛЛТ - ЛЛТ) не перевесили, то фальшивой монеты среди этих 6ти нету, и она - одна из двух оставшихся тяжелых.
В таком случае просто сравниваем одну из них с нормальной. Если она тяжелее/легче, то фальшивая она. Если нет, то монета не участвовавшая во взвешивании.

Вот, в целом, и все. Достаточно интересный алгоритм решения задачи разобран.
Надеюсь я объяснял не слишком сложно.

Спасибо за внимание.

Теги: #Алгоритмы, #задачки

Ваша оценка:

Рейтинг: 7.6 (Оценок: 4)

Комментарий:

Copyright © DOC_tr 2015-2017 г. Все права защищены
Яндекс.Метрика
Перейти к мобильной версии