ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : ЈагЇЇ   ўв®¬ вЁЄЁ                    2:5020/400     23 Aug 2002  10:48:29
 To : All
 Subject : 12 монеток
 -------------------------------------------------------------------------------- 
 

 
 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    12 монеток   ЈагЇЇ   ўв®¬ вЁЄЁ   23 Aug 2002 10:48:29   12 монеток   Paul Batuev   23 Aug 2002 18:49:38