Намери радиоктивните

[hackman]

Играта е сравнително сложна

Имате 15 топчета. Две от тези топчета са радиоактивни. Дава ви се уред с който можете да установите къде има радиоактивни топчета, но за съжаление уреда не отчита колко са.

Въпросът е да се намерят двете топчета с възможно най-малко замервания. От надежден източник знам че, това може да стане със 7 замервания.

Ние с приятели го бистрихме 1 час и успяхме да намерим алгоритъм за решаване със 6-7 замервания, но за съжаление открихме и ситуации при които алгоритмът решава проблема със 8 замервания.

Някой да предложи по-добро решение

[Стефан]

От: Намери радиоктивните

Не знам нищо за ЗАмерванията. Както и за останалите технологии на неграмотните хора.
Колкото до мигновенните измервания - въпросът ви е решим.
Казва се вариационно смятане, по мое време се учеше в Х клас.

[hackman]

От: Намери радиоктивните

Не съм казал, че въпросът е нерешим

Идеята е да се направи с възможно най-малък брой замервания. И алгоритмът винаги да работи. Интересно е да го докараш до под 8 опита.

[artefekt]

От: Намери радиоктивните

Разделяш топчетата на 5 купчинки в прогресия, съответно №1(5бр.),№2(4бр),№3(3бр.),№4(2бр.) и №5(1бр.)
Стъпка1-ва:
Намираш в кои две купчинки има радиоактивно топче.
Стъпка2-ра:
Ако са в №1 и №2(две измервания), разделяш на нови 3купчинки по 3бр. топчета. Ако купчинката не реагира(максимум едно измерване), минаваш на следващата. Намираш купчинка с р.топчета, мериш топчетата поотделно. Първо - не, второ - не, третото е търсеното без да се мери за радиация(максимум две измервания на купчинка). Общо максимум 5бр. измервания+2бр.(от началото)=max7бр.

Ако са в №1 и №3(три измервания), разделяш на нови 2купчинки по 3бр.+1 топче. Ако купчинката не реагира(максимум едно измерване), минаваш на следващата. Намираш купчинка с р.топчета, мериш топчетата поотделно. Първо - не, второ - не, третото е търсеното без да се мери за радиация(максимум две измервания на купчинка). Общо 4бр. измервания+3бр.(от началото)=max7бр.

Ако са в №1 и №4(четири измервания), Намираш кое топче е радиоактивно в купчина №4(още едно измерване) Разделяш купчинка №1 на две нови купчинки от съответно три и две топчета. Намираш кои са радиоактивните по познатия начин(максимум две измервания). Общо 3бр. измервания+4бр.(от началото)=max7бр.

Останалите случаи са по аналогичен начин.
Това решение измислих, може да има и по-добро...не зная.

[Yordan]

От: Намери радиоктивните

...

Този номер с "ако купчинката не реагира" явно не го броиш за измерване. А трябва

[artefekt]

От: Намери радиоктивните

Този номер с "ако купчинката не реагира" явно не го броиш за измерване. А трябва

Броя го, броя го..."Ако купчинката не реагира=(максимум едно измерване)"
Виж алгоритъмът, не съм описал добре, а именно ако топчетата са в една купчинка, свеждането до последния случай...ама ме домързя, пък и не знам верно ли е решението.

[Yordan]

От: Намери радиоктивните

Ето какво сам си написал (един от случаите):

Ако са в №1 и №2(две измервания), разделяш на нови 3купчинки по 3бр. топчета. Ако купчинката не реагира(максимум едно измерване), минаваш на следващата [това са ти още три мерения]. Намираш купчинка с р.топчета, мериш топчетата поотделно. Първо - не, второ - не, третото е търсеното без да се мери за радиация(максимум две измервания на купчинка). Общо максимум 5бр. измервания+2бр.(от началото)=max7бр.

Тоест, имаш 2 в началото + 3 на второ ниво + 2 за фин анализ на всяка "присветнала" тройна купчинка (общо 2), или тотално 2+3+2х2 = 9 измервания.
При късмет, ще нацелиш двете активни тройни купчинки една след друга, спестявайки си едно измерване за последната и така ще се реши с 8 измервания. При още повече късмет, една тройна ще съдържа и двете топчета - така вече стават общо 7 мерения, обаче не е честно, тъй като не се разглежда най-неблагоприятният вариант.
Отделно, ако и двете топчета се паднат да са в №1, имаш 5 измервания само на първо ниво, докато разбереш това. После купчинка с 5 топчета, от които 2 са радиоактивни, не може да се реши в рамките на само 2 измервания, освен при късмет разбира се (тоест, пак скачаш над 7 измервания общо).
Аналогични разсъждения имаш и в останалите случаи (№1 + №3... и т.н.).

При първоначално разделяне 4+4+4+3, задачата се решава с 8 измервания при абсолютно всякакво стечение на обстоятелствата. Според мен, ключов момент е това, че купчинка с 3 или 4 топчета, която сме сигурни че съдържа само едно р.топче, се решава с 2 измервания (е, тройната пак е с две мерения, дори и да съдържа 2 р.топчета). Тоест, по-изгодно е да се търсят купчинки от по 4, отколкото по 3 топчета, тъй като зорът е същия, а пък броят на купчинките - по-малък при четворното разделяне.
Обаче, не мога да го докарам под 8 измервания... А трябва да може, инак язък за задачата - твърде лесно се свеждат до 8, значи трябва да има хитрост някаква за по-нисък брой мерения. Някакви други идеи, някой ?!

[artefekt]

От: Намери радиоктивните

Ех Йордане...
Още миналият път казах, че не съм разгледал случая когато двете топчета са в една купчинка.
Идеята ми за разделяне в прогресия е като се увеличават измерванията на първо ниво, да намалява броя на топчетата на второ и финно.
Отделно загубих интерес и ясно е вече, че съм решил само частен случай.
Давай твое решение, мойто явно не е работи...

[Yordan]

От: Намери радиоктивните

Идеята ти за прогресията я разбрах аз, лошо няма. Въпросът е, че не ги виждам как стават 7 измерванията с твоята схема (нито пък с моята)...

Аз мое решение за под 8 измервания нямам, то в това е въпросът... Ако няма такова - язък за задачата, защото до 8 се свеждат лесно.

[BulAf]

От: Намери радиоктивните

Хах интересна главоблъсканица (за мен поне е такава ).
Аз измъдрих, че работата ще стане при максимално стечение на късмета с 3 измервания,а при най-неблагоприятното ще са 9 измерванията.
Разделяме 15 бр. на 5 групи по 3 бр. във всяка и сега :
1.) Най-късметлийския вариант -започваме да измерваме и още първата група показва радиоактивност (1 изм.);продължаваме да да измерваме топчетата в нея и още с първите две измервания откриваме двете радиоактивни топчета (2 изм.) или общо 3 изм.
2.) Най-каръшкия вариант -след като сме измерили всички групи (5 изм.) се оказва,че последните две са радиоактивни;измерваме всяко едно от топчетата във всяка като първо попадаме на "чистите" топчета (т.е. още 2 + 2 изм.) или общо 9 измервания.
Между двата варианта има няколко вариации от 4 до 7 измервания (интересно, че вариант с 8 не ми излезна).

Варианта даден по-горе с разделяна на групи по 4+4+4+3 има и ситуация,при която измерванията ще са 10,а не 8.
А именно: измерваме всяка от групите (4 изм.),оказва се че "мръсни" са две групи по 4 топчета,започваме да измерваме всяко едно топче от тях и откриваме "мръсните" последни (т.е. още 3+3 изм.) или общо 10 измервания.

[Yordan]

От: Намери радиоктивните

Варианта даден по-горе с разделяна на групи по 4+4+4+3 има и ситуация,при която измерванията ще са 10,а не 8.
А именно: измерваме всяка от групите (4 изм.),оказва се че "мръсни" са две групи по 4 топчета,започваме да измерваме всяко едно топче от тях и откриваме "мръсните" последни (т.е. още 3+3 изм.) или общо 10 измервания.

Е, хайде сега... Взимаш двете "мръсни" четворки и разделяш всяка на 2х2 (стават 4 купчинки), ето така:

(А) о о (Б) о о (В) о о (Г) о о

А и Б са дошли от първата мръсна четворка, а В и Г - от другата.
Мериш А: Ако ДА - после мериш едно топче от нея. Ако НЕ - мериш едно топче от Б. Така неминуемо разбираш кое е мръсното, с две измервания.
Респективно правиш същото за В и Г.
Стават 4 измервания общо. И още 4 от първата фаза (4+4+4+3) - тотално 8. Тоест, винаги не повече от 8, при каквото и да е стечение на обстоятелствата. При късмет, и двете топчета са в една четворка и тогава имаш 4+3=7 измервания, но това е само частен случай.
Как да станат 7 при всяко положение, се пита в задачката...

Аз измъдрих, че работата ще стане при максимално стечение на късмета с 3 измервания,а при най-неблагоприятното ще са 9 измерванията.

Пък аз мислех, че максимално стечение на късмета ще бъде с 2 измервания - теглиш едно топче и то се оказва мръсно. После още едно и, о чудо, и то така )))))
А най-неблагоприятното ще да е с 14 измервания. Или с 15, ако си наистина пиян и не мислиш даже колкото за бог да прОсти. А Б.Б. може да има нужда и от 16.

[Yordan]

От: Намери радиоктивните

С малка модификация на варианта (4+4+4+3) в новия (4+4+4+2+1), задачата постига решение от 7 измервания почти във всички случаи, освен ако и двете топчета се паднат в една от четворните купчини, когато ще са нужни 8 измервания...

[Стефан]

От: Намери радиоктивните

На това в катедрата Вероятности му казват "урнова схема". А в катедрата Ядрена физика се прозяват, броят стотинките, бутат батерия в дозиметъра, и додето чакат мисли от някви тесноочилати червеногъзи низши примати с вратовръзки, ловят топчетата.
Зер нали радиоактивни? Не можеш да ги скриеш току-така.
Да не ви пука, стига да говорите пискливо, и на американски английски. Ако се казвате и дянков - печелите.
Моето вечно презрение, но това е ария от друга опера.

[Niger]

От: Намери радиоктивните

Аз си направих една функция която си я викам рекурсивно и намира замърсените топчета. Броя както на всички така и на замърсените топчета може да бъде произволен.
Истина е обаче, че измерванията могат да станат много. Минималните са 5 при условие, че замърсените топчета са първите 2 в редицата.

Кода е на някакъв псевдоезик

Global int how_many_left;
Global int number_of_checks;

func check_group(array group) {
    if (how_many_left == 0) {
        return
    }
    if (check(group)) {
        number_of_checks++;
        if (elementi na group > 1) {
            deli_grupata_na_2(group, first_half, second_half)
            check_group(first_half)
            if (how_many_left > 0) {
                check_group(second_half)
            }
        } else {
            На това място може да се отбележи заразеното топче, но това са технически подробности.
            how_many_left--
            return
        }
    } else {
        return
    }
return
}
Print number_of_checks;