12 монеток

From

Alex Malashonok (2:4635/1024.64)

To

Sergey Vasenin

Date

2002-08-24T14:56:14Z

Area

RU.ALGORITHMS

Привет Sergey!

Пятница Авгyст 23 2002 22:51, Sergey Vasenin -> Oleg Shatalov:

 >>> Есть сабж, среди них одна фальшивая(отличается от настоящих весом).
 >>> С помощью трех взвешиваний найти фальшивую монету.
 SV>     такто оно так а что если монет 27  и  3 взвешивания:
 SV>        pезyльтат  9 монет 2 взвешивания
 SV>        pезyльтат  27 монет 3 взвешивания
Хотелось-бы уточнить. Для этой задачи есть стандартная формула:
       log(N)
  К = -------
       log(3)

N = кол-во манеток. K = кол-во взвешиваний. Решение строго теоретично - по оценке энтропии информации по Хартли:

log(N) - энтропия алфавита A1 - монетки.
log(3) - энтропия алфавита A2 - 3 состояния весов.

зы: для данного случая получаем, минимум, 3 взвешивания (округляется до   следующего целого).


Alex

--- Советую стереть эту строку...
 * Origin: Люда, позвони домой! Тебя ищут родители! (2:4635/1024.64)