Кинофорум

trex? по моим расчетам вы ошиблись не в первом пункте, где 5-5-5, а во втором, где 2 кучки по 5 из первого пункта делятся по 3 и 2 шарика... вы расчитали не худший из возможных вариантов...

при худшем раскладе мы узнаем в первом пункте что в одной из куч по 5 нет радиации, а во второй есть, но количество радиактивных шаров не известно, третья же остается неизвестной, есть там один шарик, и один во второй, или же третья тоже пуста, и оба шара во второй... но это уже не важно... измерили первую и вторую кучу, отбросили первую, оставили вторую и третью кучу по 5 шаров... использовали 2 измерения... теперь делим их, как вы писали, по 3 и 2 шара, каждую... теперь измеряем 3 шара из первой кучи...есть радиация, допустим, один или оба шара найдены... теперь нужно мерить остальные, чтоб найти второй или убедиться что его нет... разумеется, мерим вторую тройку... нет радиации... ладно, мерим первую двойку, тоже нет радиации... а вот теперь на этом этапе полюбому придется использовать уже 4 измерение ( итого 6-е), мерим вторую двойку, чтоб узнать, есть ли тут нужный шар, или оба они в первой тройке... повезет, если тут не будет радиации, но мы то рассматриваем худший вариант... получается что вам нужно затратить еще одно измерение, чтоб узнать какой из второй двойки радиактивен (уже 7), и как минимум еще 2 измерения, чтоб найти шар в первой тройке... итого 9 измерений, ваш вариант не худший.

— RAMMSTEIN

а что вообще значит "минимально возможное", и почему 4? если вы имели ввиду "при самых благих обстоятельствах", то можно и 2-мя измерениями обойтись... скажем так, мне нереально прет, отобрал 2 из 15, измерил, на те, оба заражены... а если серьезно, то это глупый вопрос...

— RAMMSTEIN

Не совсем такой алгоритм.
Так много писать не хочется.

— trex

Задача, по сути, сводится к отделению радиоактивных шаров от нерадиоактивных. Испытания следует проводить так, чтобы на каждом этапе отсеивать максимальное число нерадиоактивных шаров, тогда пространство поиска будет сужаться наиболее эффективно.

Т.к. следует находить не 1 шар, а 2, то в ХУДШЕМ случае каждый этап должен состоять из двух испытаний. В первом испытании (в худшем случае) мы обнаруживаем наличие радиоактивного шара (или двух) в первой испытуемой группе, а во втором испытании мы делим оставшиеся шары так, чтобы в любом случае исключить как можно больше, т.е. пополам. При любом исходе второго испытания мы можем исключить практически половину шаров из оставшихся после первого испытания. И это исключаемое кол-во должно быть в любом случае максимально. Поэтому нужно стремиться, чтобы число шаров после испытания первой группы оставалось как можно больше.

Но с другой стороны, если первое испытание показало отсутствие радиации, то мы можем сразу исключить эту первую группу. Отсюда следует, что группа в первом испытании так же не может быть слишком маленькой. Иначе исключено будет слишком мало шаров.

Оптимальным является такое деление шаров на группы, при которым отсеивается примерно одинаковое количество шаров как после этапа, состоящего из двух испытаний (первое испытание показало радиацию), так и после двух этапов, показавших отсутствие радиации в первом же испытании каждое.

Пусть в начале каждого этапа у нас N шаров. Для первого испытания отбираются a*N шаров.
Тогда, если первое испытание покажет радиацию, то после второго испытания (с делением остатка попалам) останется для следующего этапа

a*N + (1-a)*N/2 = (1+a)*N/2 шаров.

А если и в первом и во втором этапе первое же испытание показало отсутствие радиации, то в результате этих двух испытаний останется

(1-a)^2*N шаров.

Т.к. первая функция монотонно возрастает, а вторая монотонно убывает на диапазоне a=[0..1], то оптимальным является такое значение a, при котором значения обоих этих функций равны. При любом другом значении a либо в одном, либо в другом случае (т.е. в худшем случае) число не отсеянных шаров будет больше.

Решая уравнение (1+a)/2 = (1-a)^2 получим a = (5-sqrt(17))/2=0,21944.

Т.е. для испытания следует брать в каждом случае 0,219 от оставшихся шаров (округленно).
Если это испытание не показывает радиации, то группа откидывается и испытание повторяется аналогичным образом.
Если первое испытание показывает радиацию, то оставшиеся шары делятся примерно пополам и откидывается та половина шаров, в которой не может быть радиоактивного шара (по результатам следующего испытания).

После каждого испытания количество шаров уменьшается примерно в

1/(1-0,21944)=1,2811 раз.

Т.к. нам нужно уменьшить число шаров с 15 до 2, т.е. в 7,5 раз, то число испытаний равно логарифму от 7,5 по основанию 1,2811, т.е. равно 8,133.

Таким образом, даже в идеальном случае может понадобитьсябольше 8 испытаний в худшем случае.

В реале, когда шары делить нельзя ни на 1,2811, ни даже пополам, энтропия возрастает по сравнению с идеально делимой системой. Таким образом каждое испытание позволяет получить меньше информации по сравнению с идеальным. И уже встает вопрос: а хватит ли 9-ти испытаний?

Сейчас буду разбираться в предложенных алгоритмах и предлагать свои.

— Тень капитана Сильвера

Кстати, брать в первом испытании 5 шаров, кажется, очень далеко от оптимального. В случае неудачи (первое испытание показало радиацию), мы за 2 испытания отсеем только 5 шаров.

А если в первом испытании взять 3 шара (15*0,21944=3,2916 - округляем до 3), то если оно покажет радиацию, то после второго отсеем сразу 6.

А если первое испытание не покажет радиации, то ко второму испытанию у нас останется 12 шаров. И если снова взять 3 шара, то либо после него останется всего 9, либо после третьего останется 8. А вот это уже немного хуже. Так что надо сравнивать внимательно.

— Тень капитана Сильвера

Мин возможное по первому алгоритму измерений

— trex

Кстати, минимально возможное число испытаний сильно зависит от применяемого алгоритма.

Только это лучше на другом примере продемонстрировать.

Допустим, дан упорядоченный по возрастанию массив неповторяющихся значений.

Есть два алгоритма: 1) последовательный просмотр; б) делением пополам.

При последовательном просмотре мы можем в худшем случае обнаружить элемент на последнем месте, а в лучшем - на первом. Т.е. N и 1 операций соответственно.

При делении пополам и в лучшем и в худшем случае понадобится около log2(N) операций.

Т.е., оптимизируя алгоритм для повышения эффективности, т.е. для уменьшения числа операций в худшем случае, мы тем самым ухудшаем его работу в лучших случаях.

— Тень капитана Сильвера