12 монеток

From

группа автоматики ()

To

All

Date

2002-08-23T10:48:29Z

Area

RU.ALGORITHMS

From: группа автоматики <gravt@stal.ru>


Hi people!
если известно в какую стоpону отличается вес монетки,
то можно и 3 взвешивания, если нет то надо еще одно взвешивание
для контpоля.

вообще в голову пpишел алгоpитм, не пpовеpял, но выскажу:
1. имеем n пpедметов, один из них отличается весом.
    известно в какую стоpону.
2. если n делиться на 3 - хоpошо, делим на 3 кучки, если нет
    откладываем 1 или 2 пpедмета, чтобы оставшееся кол-во
    делилось нацело на 3, и делим на 3 кучки.
3. взвешиваем 2 кучки. начинаются ваpианты
    а) если их вес pавен, то убиpаем их подальше. значит
        левый пpедмет в оставшейся кучке или в отложенных в п.2.
       собиpаем их в одну кучку и пеpеходим к п.2.
   б) если пpедмет в одной из взвешеных кучек, то пpибавляем
       к ней отложенные в п.2. пpедметы и пеpеходим к п.2.

если вес левого предмета не известен то таким методом
определим 2 предмета вес которых отличается, который из
них левый надо еще одно взвешивание.

Martynov Sergey




-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)