Зарегистрирован: 06.06.2007 Сообщения: 2133 Откуда: Планета Плюк, 215 в Тентуре, галактика Кин-дза-дза в Спирали
: 14-05-2008, 11:29 Тема:
Пришелец Прораб
А ведь ты прав! log3 N взвешиваний потребуется только в самом благоприятном случае, когда фальшивка каждый раз оказывается в отложенной части (в первый раз - в девятке, во второй раз - в тройке, в третий раз - единственная). А в остальных случаях требуется ещё одно взвешивание, т.к. остаются 2 подозрительные.
Таким образом, нам потребуется:
log3 N взвешиваний, с вероятностью 1/3^N
log3 N + 1, во остальных случаях.
В среднем, log3 N + 1-1/3^N
При N -> бесконечности, log3 N +1
Пусть N=12, тогда log3 N + 1-1/3^12 = 3.262
Т.е. мой метод даёт почти всегда решение за три взвешивания и лишь с малой вероятностью могут потребоваться 4.
Тогда нужно применить другой метод.
Кстати, Пришелец Прораб, а вы не рассмотрели случай, когда на чашах весов в первый или второй раз будет равенство. В этом случае ваше решение не проходит:
Цитата:
берётся 6 монет на одну чашу ложатся 3 и на другую три, если какая-нибудь перевешивает
значит та монета которую мы ищем в этой шестерки,иначе в другой.Потом из той 6 где мы выивили монету берется 3 монеты
и берется 3 монеты из той 6 в которой все монеты равны,сравнивается и из этого мы можем сделать два вывода:
1)если опять неравенство на весах то монета в этой 3 или же в другой.
2)мы узнаем точно в какую сторону отличается монета так как эта тройка либо перевесит либо наоборот.Соответсвенно монета либо тяжелее либо легче.
А дальше ваще просто есть 3 монеты и последняя попытка и мы знаем например што монета оказалась тяжелее.Сравниваются две из этой тройки находиться тяжелая либо они равны значит это та монета которую мы не сравнивали.Спасибо за вниманию.
Смотрите, если в первый раз равенство, то мы знаем, что фальшивка в другой шестёрке, но не имеем уже информации, какая тройка из неё тяжелее, а какая легче, на чём строится ваше решение. То же самое, если равенство во втором взвешивании...
Моё решение строится на том, что мы делим N не пополам, а на три части. Третью часть откладываем, а две оставшихся трети раскладываем на разные чаши весов. Если весы не показывают равенство, то количество монет на каждой чаше опять делим на три части. Треть откладываем, треть оставляем, а остальные перекладываем с одной чаши на другую.
Смотрите, если в первый раз равенство, то мы знаем, что фальшивка в другой шестёрке, но не имеем уже информации, какая тройка из неё тяжелее, а какая легче, на чём строится ваше решение. То же самое, если равенство во втором взвешивании...
Никак нет.Если мы взвешиваем первые две тройки и они получаются равны то значит монета в другой шестерки так?.Из этой шестерки мы выбираем 3 монеты на свой вкус приравниваем и все равно мы может сделать два вывода:
1)если равенство на весах значит монета в оставшейся тройке.
2)мы же знаем что при первом взвешивании монеты равны значит если перевешывают то монета в этой тройке и она тяжелее,потому как остальные все равны значит легче.
Ну дальше из трёх находим одну.
Единственный вариант когда при первом взвешивании равны и при втором равны тогда у нас остается три монеты но мы не знаем легче они или тяжелее .Тогда потребуется четвертое взвешивание.
Мы делим количество монет на 3 кучки.
Две одинаковые и одну либо больше на одну монету, либо меньше на одну монету, либо такую же.
Взвесив равные кучки мы определяем есть ли монета в отложенной кучке. Если есть (т.е. взвешиваемые кучки равны), то все клевою, а если нет, то сложнее ибо мы не знаем в какой из кучек монета, так как не знаем легче фальшивая монета или тяжелее.
Действительно Log3 получается только, если мы знаем легче или тяжелее фальшивая монета.
В случае равенства кучек можно обойтись еще одним взвешиванием с отложенной кучкой, после которого мы точно знаем в какую сторону отклонение.
А вот в случае 26 монет у нас только 8 эталонных монет - значит при плохом варианте остаются непроверенными 10.
И мы по-прежнему не знаем кто тяжелее.
Насчет задачи с 12 монетками среди которых 1 фальшивая.
На досуге занялся этой задачей, но начал решать ее немного по другому. Сначала я рассмотрел аналогичную задачу для меньшего числа монет. Т.е. найти фальшивую монету не более чем за 3 взвешивания, если количество монет:
3
4
5
...
12
Задачу удалось решить для количества монет 3...10. Для 11 и 12 монет задача уже не решается за 3 взвешивания. Точнее, решается, но только с определенной вероятностью - если "повезет" - с 3, если нет - с 4 взвешиваний.
Для 11 и 12 монет неопределенность слишком высока, чтобы фальшивку можно было гарантированно определить за 3 взвешивания. Правда, строго доказать не берусь. Интуитивно это будет понятно, если вы проделаете ту же работу, что и я - т.е. решите задачи с меньшим числом монет.
Кстати, для случая 10 монет решение будет достаточно интересным.
Зарегистрирован: 06.06.2007 Сообщения: 2133 Откуда: Планета Плюк, 215 в Тентуре, галактика Кин-дза-дза в Спирали
: 26-05-2008, 09:53 Тема:
А я, кажется, вспомнил как решал!
1. Делим 12 монет на 3 части по 4 штуки. Одну часть откладываем, 2 других располагаем на разные чаши весов.
2. Если на весах равенство, переходим к п. 7, иначе отложенную часть считаем эталонной.
3. Снимаем с одной чаши весов (например, которая тяжелее) 1 монету, с другой - 2 монеты (и откладываем их не перемешивая с другими и друг с другом), и докладываем туда одну монету из эталонной части. Одну монету тяжелой части обмениваем с одной монетой с лёгкой.
4. Если на весах равенство, переходим к п. 5. Если неравенство осталось прежним, то фальшивая монета - среди 2х, которые мы не трогали на "тяжелой" чаше весов или та, которую мы не трогали на "лёгкой чаше. Этот случай рассмотрен в п.5. Если неравенство поменяло знак, то фальшивая монета - одна из двух перемещённых. Какая именно из них проверяется третьим взвешиванием (сравнением любой из них с эталонной).
5. Если при втором взвешивании было равенство, возвращаем на весы снятые монеты, на те же чаши, откуда мы их сняли. Если при втором взвешивании знак не поменялся, оставляем монеты на месте. В любом случае мы имеем на одной чаше 2 подозрительные монеты, на другой - одну, и знаем какой был знак при взвешивании. Теперь отложим одну монету из той чаши, где были 2, переложим на эту чашу оставшуюся монету из другой чаши, а на опустевшую чашу положим 2 эталонных монеты.
6. Если на весах равенство - фальшвая монета - отложенная, если неравенство осталось прежним, то фалишивая монета та, которую мы не трогали на "подозрительной" чаше весов, а если неравенство поменяло знак, то фальшивая монета - та, которую мы переместили.
7. Если в первом взвешивании было равенство, то осталось 4 подозрительных монеты и 2 взвешивания.
Откладываем 1 монету, две располагаем на одной чаше, одну - на другой и добавляем к ней эталонную (из оставшейся восьмёрки).
8. Если на весах равенство - фальшивая монета та, что мы отложили. В противном случае мы имеем ситуацию, аналогичную п.5.
Введу обозначения:
0 - монетка, про которую мы не знаем - фальшивая она или настоящая.
+ - настощая монета
@ - фальшивая монета
В начале мы имеем:
0000 0000 000@
1)
Допустим в певром взвешивании мы получили следующий результат:
0000>0000
++++ (четыре оставшиеся монеты - настоящие)
Результат возможен в 2-х случаях:
1. Фальшивая монета тяжелее. Тогда имеем:
000@>0000
2. Фальшивая монета легче. Тогда имеем:
0000>000@
2)
Допустим при втором взвешивании мы пользуемся приемом :
Снимаем с одной чаши весов (которая тяжелее) 1 монету, с другой - 2 монеты, и докладываем туда одну монету из эталонной части. Одну монету тяжелой части обмениваем с одной монетой с лёгкой.
Допустим также, что в результате всех этих перестановок фальшивая монета осталась на весах и неравенство на весах сохранило знак. Итак, что мы получили:
000>00+
+ (снятая с левой чащи монета)
++ (снятые с правой чаши монеты)
+++ (монеты, отложенные с первого раза)
Результат возможен в 2-х случаях:
1. Фальшивая монета тяжелее. Тогда имеем:
00@>00+
2. Фальшивая монета легче. Тогда имеем:
000>0@+
3)
А вот теперь самое веселое.
Как за 1 взвешивание определить, какая из 5 оставшихся монет фальшивая? По-моему, это невозможно.
В общем, путем переброса монет можно уменьшить неопределенность. Я сам пользовался этим приемом для 10 монет. А вот использовать это прием дважды для 12 - не догадался.
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Личные сообщения
Вход
Репутация: 3
Репутация: 57
Репутация: 4
Репутация: 13
