Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Оффтопик (http://forum.algolist.ru/offtopic/)
-   -   подскажыте алгоритм решения задачи (http://forum.algolist.ru/offtopic/127-podskajyte-algoritm-resheniia-zadachi.html)

Pioneer 29.11.2006 17:28

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

IgNik500 11.12.2006 13:35

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

IgNik500 11.12.2006 14:02

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

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 Вычилсит.

незарегистрированный 15.01.2007 22:18

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

BreakPoint 23.01.2007 23:58

Да интересная задачка, у меня меньше 9 не получается. Неужели ответ 4:eek:

CD_Eater 24.01.2007 19:28

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

jssj 29.05.2007 14:12

за 4 получается
 
Цитата:

Сообщение от незарегистрированный (Сообщение 835)
думаю нельзя за 4 сделать, самый быстрый способ - делить на примерно равные кучи и смотреть, в какой из их радиация, но такой способ в худшем случае даёт больше 4 измерений, вот если бы был 1 шарик то 5 хватило бы...

тест 1. из 15 выбираем и тестируем любые 8. если группа радиоактивна, подвергаем ее второму тесту. если нет, тестируем группу из остальных 7 (для простоты рассуждений добавим к ней один шарик из первой группы).
тест 2. радиоактивную группу из 8 шариков делим пополам и опять одним тестом выбираем радиоактивную из 4. применяем к ней тест 3.
тест 3. аналогично, радиоактивную группу из 4 делим пополам опять и выбираем радиоактивную подгруппу из 2.
тест 4. из 2 находим радиоактивный.

CD_Eater 24.06.2007 02:23

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


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

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

k06a 18.07.2007 03:52

Перебор - дело не хитрое
 
Алгоритм прост) Сначала рекурсивно делим пополам и проверяем на радиацию О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;



Часовой пояс GMT +4, время: 11:56.