|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Malashonok 2:4635/1024.64 24 Aug 2002 14:56:14
To : Sergey Vasenin
Subject : 12 монеток
--------------------------------------------------------------------------------
Пятница Авг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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
