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

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

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

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

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

P.S.точно не уверен но ответ кажется должен быть 4. но как???
  #2  
Старый 11.12.2006, 13:35
Новичок

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

http://forum.algolist.ru/images/smilies/smile.gif
Мне кажется надо попробовать в конструкции
For n = 1 to 15 проверить каждый шарик.
  #3  
Старый 11.12.2006, 14:02
Новичок

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

. Хотел бы попытаться помочь.

Dim Ball1 as Integer, Ball2 as Intrger
For n = 1 to 15
If Шарик(n) радиоактивен then
If Ball1 = Empty And Ball2 = Empty Then[/color]
Ball1 = n 'Номер этого шара
Elseif Ball1 >0 And Ball2 = Empty Then
Ball2 = n 'Второй шар
Elseif Ball1 > 0 And Ball2 > 0 Then
MsgBox " Радиоактивных шаров больше 2"
End if
End If
next n

За 15 вычислений VB Вычилсит.
  #4  
Старый 15.01.2007, 22:18
незарегистрированный

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

думаю нельзя за 4 сделать, самый быстрый способ - делить на примерно равные кучи и смотреть, в какой из их радиация, но такой способ в худшем случае даёт больше 4 измерений, вот если бы был 1 шарик то 5 хватило бы...
  #5  
Старый 23.01.2007, 23:58
Новичок

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

Да интересная задачка, у меня меньше 9 не получается. Неужели ответ 4
  #6  
Старый 24.01.2007, 19:28
Аватар для CD_Eater
Пользователь

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

log2(число возможных пар из 15) = 7 с копейками.
Поэтому меньше 8 никак
  #7  
Старый 29.05.2007, 14:12
jssj

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

за 4 получается
Сообщение от незарегистрированный Посмотреть сообщение
думаю нельзя за 4 сделать, самый быстрый способ - делить на примерно равные кучи и смотреть, в какой из их радиация, но такой способ в худшем случае даёт больше 4 измерений, вот если бы был 1 шарик то 5 хватило бы...
тест 1. из 15 выбираем и тестируем любые 8. если группа радиоактивна, подвергаем ее второму тесту. если нет, тестируем группу из остальных 7 (для простоты рассуждений добавим к ней один шарик из первой группы).
тест 2. радиоактивную группу из 8 шариков делим пополам и опять одним тестом выбираем радиоактивную из 4. применяем к ней тест 3.
тест 3. аналогично, радиоактивную группу из 4 делим пополам опять и выбираем радиоактивную подгруппу из 2.
тест 4. из 2 находим радиоактивный.
  #8  
Старый 24.06.2007, 02:23
Аватар для CD_Eater
Пользователь

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

jssj
Это решение задачи для одного радиоактивного шарика. А по условию из 15 таковых ДВА.


И ещё я ошибся: log2(C(15,2)) < 7, поэтому теоретически может существовать способ за 7 измерений

Путь решения такой: пронумеровать пары шариков и проводить измерения тех подмножеств шариков, которые разделят множество "подозреваемых" на радиоактивность пар примерно пополам.
Например, первым ходом нужно взять любые 4 шарика и измерить их радиоактивность. В принципе, можно написать программу, которая будет искать дерево решения - получим разветвляющийся список из операций тестирования наборов и ветвлений по результату тестирования.
Но как получить просто описываемое и интуитивно понятное решение задачи?
  #9  
Старый 18.07.2007, 03:52
Новичок

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

Перебор - дело не хитрое
Алгоритм прост) Сначала рекурсивно делим пополам и проверяем на радиацию О6Е части, до тех пор, пока не будут ОБЕ радиоактивными! Затем каждую из радиоактивных частей рекурсивно делим пополам и проверяем на радиацию лишь ОДНУ из частей!
И что нам стоит рассмотреть все варианты расположения этих радиоактивных шаров.
Вот пример на паскале. Я не проверял на компе, пишу с мобы, но должно работать вроде . . .
Код:
uses crt;
var
mas:array[1..15] of byte;
a,b,max,res,x,y:byte;

function rad(i1,i2:byte):boolean;
var i:byte;
BEGIN
rad:=false;
for i:=i1 to i2 do
if mas[i]>0 then rad:=true;
res:=res+1;
END;

procedure go(aa,bb:byte);
var
    cc:byte;
    v1,v2:boolean;
BEGIN
cc:=(aa+bb) div 2;
if r=2 then
begin
    v1:=rad(aa,cc);
    v2:=rad(cc+1,bb);
    if v1 and v2 then
    begin
    go(aa,cc,1); go(cc+1,bb,1);
    end else
    if v1 and (not v2) then
    go(aa,cc,2) else
    if (not v1) and v2 then
    go(cc+1,bb,2);
end else
if r=1 then
begin
    if bb=aa then exit;
    if rad(aa,cc) then go(aa,cc,1)
    else go(cc+1,bb,1);
end;
END;

BEGIN
clrscr;
for a:=1 to 14 do
for b:=a+1 to 15 do
begin
    for i:=1 to 15 do mas[i]:=0;
    mas[a]:=1; mas[b]:=1;
    res:=0;
    go(1,15,2);
    if res>max then max:=res;
end;
write(max);
readkey;
END;
 


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

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


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