|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 05 Oct 2001 13:33:06
To : Andrew Doroshew
Subject : Re: Последнее про 12 монет
--------------------------------------------------------------------------------
Fri Oct 05 2001 12:53, Andrew Doroshew wrote to Roman Kirillov:
>> Hу вот...все кpуто, задачу pешили. Даже пpогу накpопали (насчет глючности
>> не знаю, не пpовеpял). Как и следовало ожидать, pешили ее быстpо те, кто
>> знал pешение (я лично pешал с 10 вечеpа до 3 ночи и нашел алгоpитм
>> близкий к цитиpуемому из фака). Если хотите дальше pазминать мозги -
>> будут еще задачки.
AD> Её врядли кто решал сейчас.
AD> Эта задача - что-то из классики. Первый раз я её увидел классе в
AD> четвёртом, или около того. Позже, когда заполучил программируемый
AD> калькулятор, получил на нём решение тупым перебором за несколько суток
AD> на спор с учителем физкультуры :), и оно было несколько неожиданным.
AD> Оказалось, что монет может быть не 12, а 13.
AD> Про эту задачу всем известно всё.
AD> Если есть оригинальные задачи, то давай, а таких - может не надо?
ИМХО интерес для эхи представляет не столько сама задача, а подход к ее
решению, а более общО - к построению алгоритмов, основанный на теории
информации.
Представляется очевидным, что выбор одной альтернативы из 24 (ь монеты - 12
вариантов и 2 варианта веса) требует LOG2(24) бит информации, а взвешивание
дает не более LOG2(3) бит, и только при равной вероятности всех трех положений
весов эта оценка достигается. Следовательно, при размещении монет по чашам
весов нужно распологать их так, чтобы положения были равновероятны (насколько
это возможно).
Если при первом взвешивании это достигается естественным выбором (4л 4п 4х),
то для того, чтобы придти к несимметричному расположению на следующих шагах,
нужно действительно поломать голову - и здесь поможет то, что при всех
вариантах симметричного выбора вероятности не будут равны.
Следует отметить, что три взвешивания дают LOG2(27) бит информации, что и
обуславливает возможность решения задачи для 13 монет (но не всегда
определения веса 13-й, отложенной). Для 12 реально извлекаются LOG2(25) бит,
то есть можно найти фальшивую - или доказать ея отсутствие.
Интересно сравнить применение здесь информационного подхода и его же, при
построении алгоритмов сортировки (так, неэффективность алгоритма пузырька
связана с тем, что после первых проходов возникает известное упорядочение
соседних элементов, и исходы при сравнении не будут уже равновероятны - а вот
Шелл уже сравнивает далеко отстоящие - и сравнения более информативны).
С уважением
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Последнее про 12 монет