PermLUG
|
Пермская группа пользователей Linux |
|
ОблакоВход для пользователейНавигация |
Задачка про шары и весы Третьего дня спросонья забыл взять с собой книжку, чтобы в метро почитать. Включившийся по привычке мозг требовал пищи и думал о всяком. Извилистая дорожка мыслей случайно вывела мозг на известную многим задачку про 6 шаров и весы. Звучит она примерно так: есть 6 внешне одинаковых шаров, один из которых тяжелее других; есть весы с двумя чашами, которые могут показывать только больше, меньше или равно, без конкретных значений; за какое минимальное число взвешиваний можно точно определить, какой из шаров тяжелее других? А теперь внимание:
|
Новые записи в блогах |
| Пермская группа пользователей Linux, 2003—2008 |
Комментарии
По-моему при любом N решить задачу можно однозначно.
Самый простой вариант вариант: если N - степень двойки, то M собственно равно этой степени
Вариант посложнее, возможны 2 ситуации:
Ситуация 1: N делится на 2, тогда делим до тех пор пока делится и выбираем кучку, что тяжелее
Ситуация 2: N на 2 нацело не делится, тогда вычитаем 1 и спокойно делим на 2. Получаем 2 кучки и шар. По приведенному в решении алгоритму определяем, в кучке ли искомый шар и в какой кучке или этот шар уже найден.
Приходим снова к одной из ситуаций и повторяем итеративно до нахождения шарика
Максимальное необходимое число взвешиваний при этом будет равно логарифму по двойке ближайшей снизу степени двойки. То есть для 7 это будет log 4 по 2, то есть 2.
Может чего-то напутал, но вроде так
Когда я имел в виду неоднозначность, я как раз говорил про ситуацию 2, когда мы получаем две кучки и шар. В этой ситуации всегда есть вероятность (P = 1 / N) угадать с первого раза, но горазде больше вероятность того, что мы не угадаем.
мда, не особо внимательно читаю условие.
Тогда для нечетных N минимальное число взвешиваний с вероятностью 1/N = 1
Если и N div 2 нечетно, то
(N-1)/N * 1/(N div 2) = 2
Если N div 4 нечетно, то
(N-1)/N * (N div 2 - 1)/(N div 2) * 1 / (N div 4) = 3
и так далее.
Однозначно о минимальном числе взвешиваний получается можно сказать только для степеней двойки, иначе случайность выбора приходится учитывать
Ты уже близко ;) Про степени двойки ты угадал, но ещё кое-чего не хватает для полного счастья.
У меня получилось так:
N = 2^A x 3^B, где:
A >= 0,
B = 0 | 1
Тогда M = A + B
Чертовы математики. Вы ломаете мне моск :-)