Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.11.2006, 17:30
Новичок

Отправить личное сообщение для Pioneer Посмотреть профиль Найти все сообщения от Pioneer
 
Регистрация: 23.11.2006
Сообщений: 2

подскажыте алгоритм решения задачи
Задача:Есть 15 шариков,среди которых 2 радиоактивных,и есть прибор, который позволяет измерять уровень радиации(есть она или её нет).За какое минимальое количество измерений можно найти эти 2 шарика?

P.S.точно не уверен но ответ кажется должен быть 4. но как???
  #2  
Старый 29.11.2006, 17:46
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

сдается мне, что нужно 7 измерений:
15-битовых чисел,в которых только 2 бита установлены в единицу - с(15,2) = 105, округляем до степени двойки вверх - 128=2^7
  #3  
Старый 29.11.2006, 18:00
Стас

 
Сообщений: n/a

Ре
имхо бред полнейший, все равно количество измерений в худшем случае будет 14. прибор ведь измеряет радиоактивоность только одного шарика, и знание об одном шарике почти всегда нам ничего не говорит. это уже задача не на алгоитм, а на теорвер)
  #4  
Старый 29.11.2006, 18:26
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Задача решается с использованием минимизации энтропии - на каждом шаге мы должны выбирать такой набор шариков, при котором варианты делятся пополам (для нечетного количества - примерно пополам).
Пример для 4 шариков - 6 вариантов, 3 измерения.
Пронумеруем шарики от 0 до 3, и нарисуем на коорд. плоскости точки, соответствующие возможным вариантам, где X - номер меньшего радиоактивного, Y - большего. Получится треугольник из точек, отделим половину из них прямой - например, прямой x=0.5.
Получаем слева варанты 01 02 03, справа 12 13 23
Значит, для первого измерения достаточно проверить один шарик 0. Если шарик активен, то из трех оставшихся легко за 2 оставшихся опыта найти активный, иначе ищем 2 активных - тоже 2 измерения.
Для большого количества шариков, конечно, дерево решений будет сложнее. Можно перенумеровывать шарики из актуальной ветви решений.
Для 15 шариков можно попробовать вначале отделить 49 вариантов слева и 56 справа с некоторой растратой запаса миллибитов...
  #5  
Старый 30.11.2006, 12:54
Новичок

Отправить личное сообщение для Gost_ Посмотреть профиль Найти все сообщения от Gost_
 
Регистрация: 16.10.2006
Сообщений: 12

Сообщение от MBo Посмотреть сообщение
Пример для 4 шариков - 6 вариантов, 3 измерения.
Пронумеруем шарики от 0 до 3, и нарисуем на коорд. плоскости точки, соответствующие возможным вариантам, где X - номер меньшего радиоактивного, Y - большего. Получится треугольник из точек, отделим половину из них прямой - например, прямой x=0.5.
Получаем слева варанты 01 02 03, справа 12 13 23...
Неудачный пример, т.к. за 3 измерения можно решить задачу, просто измерив любые 3 шарика, не обращая внимания ни на какую энтропию и варианты "слева и справа".
  #6  
Старый 30.11.2006, 13:20
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>неудачный пример, т.к. за 3 измерения можно решить задачу
эт я понимаю, но для большого числа шариков лень просчитывать дерево решений и писать
  #7  
Старый 30.11.2006, 19:23
Новичок

Отправить личное сообщение для EfremovAleksei Посмотреть профиль Найти все сообщения от EfremovAleksei
 
Регистрация: 30.11.2006
Сообщений: 8

это со сборов?
  #8  
Старый 04.12.2006, 15:49
k_const

 
Сообщений: n/a

вариант с ассимптотически оптимальным временем.
пусть шариков N. берем из них P шариков, чтобы P было ближайшим
к решению уравнения
N(n-1)/2=x(x-1).
если нет радиоактивных, то аналогично для N-p шариков, если есть, то
среди N-p шариков не более 1 радиоактивного и количество вариантов
P(p-1)/2 - что оба радиоактивных шарика в первой группе+p(n-p), что
один из них во второй группе. теперь легко получить формулу для деления шариков второй группы, так, чтобы количество вариантов все время делилось примерно пополам. и т.д.
  #9  
Старый 12.11.2009, 01:45
гость

 
Сообщений: n/a

я думаю, что всё намного проще. Из условия задачи мы видим, что прибор можно использовать 7 раз помещая в него определённое количество шаров, но можно просто поместить определённую группу шаров в прибор и больше его не использовать, а просто вынимать по одному шару пока прибор не покажет отсутствия радиации. 15 шаров делим на три кучи по 5 шаров и замеряем каждую, в любом случае 5 шаров отбрасываем, использовав прибор максимум 3 раза. осталось 10 шаров, которые делим на две кучи по пять. Помещаем 5 шаров в прибор, использовав его в 4-ый раз, и просто вынимаем из него шары по одному и после какого шара прибор не покажет радиацию тот и радиоактивный. Также и вторая пятёрка шаров, и того всего 5 раз использован прибор.
  #10  
Старый 15.11.2009, 17:27
Аватар для pavlinux
Пользователь

Отправить личное сообщение для pavlinux Посмотреть профиль Найти все сообщения от pavlinux
 
Регистрация: 16.11.2008
Сообщений: 93

Сообщение от гость Посмотреть сообщение
Из условия задачи мы видим, что прибор можно использовать 7 раз помещая в него определённое количество шаров
Них...я мы не видим такие условия задачи

* 15 шаров.
* Шары независимы. (хоть на разных планетах)
* Два радиоактивных.
* 13 не радиоактивных.
* Одна процедура измерения, показывает или нет наличие радиоактивности.
* Если доп. условия не описаны в задании, считаем, что их нет.

Пример, самый худший, последние два шара радиоактивны.

0000000000000 XX - этот порядок отображает не расположение шаров, а именно порядок проверки.

To: MBo, как ты собрался за 7 раз проверить шары, если первые 7 измерений показали 0, осталось ещё 8.

Я вот гарантировано, проверю 14 шаров. Либо афтор давай доп условия.


Аналогичный пример:
у Юпитера 63 спутника, на 2-х из них есть вода.
Есть только один спускаемый многоразовый космический аппарат?
На скольких спутниках надо взять пробы грунта, чтоб однозначно сказать - Тут есть вода!?!?!

По методу MВo - C(63,2) = 1953. или до ближайшей двойки 2^11, то есть 11 раз.

Последний раз редактировалось pavlinux, 15.11.2009 в 18:04.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм решения линейного уравнения n-й степени Destrifer Реализация, исходники, языки 9 07.07.2009 10:04
волновой алгоритм, подскажите как оптимизировать для задачи NewRon Реализация, исходники, языки 4 20.05.2009 19:03
нужен алгоритм решения задачи Neeka Математические алгоритмы 4 17.05.2008 19:09
подскажыте алгоритм решения задачи Pioneer Оффтопик 8 18.07.2007 03:52