Добро пожаловать на сайт любителей кино!

Фильмы, рецензии, рейтинги и общение.

Входите или Регистрируйтесь.
Facebook 32 Vk 32 Twitter 32

Кинофорум

Форумы → Болтология → Мозголомки Задачки на смекалку, Весёлые головоломки

Сообщения (2602)

Pochemuk

Тогда считай, что я вообще ничего не писал.
Писаниной пол ночи заниматься не хочу.

— trex

Я просто попросил пояснить, откуда из строчки

3,2-3,2 ... 2

получилась строчка

2,1-2,1 ... 2

И что вв них эти цифры обозначают, если не число шаров в кучке?

Pochemuk

Пойдем "от обратного" ...

Сколько может понадобиться испытаний, чтобы проверить 3 шара и найти среди них 2 радиоактивных?
А если шаров 4? А если 5, 6?

Легко показать. что в случае 6 шаров нам может понадобиться 6 испытаний. А если шаров 7, то и этого мало.

А теперь попробуй за 1 испытание уменьшить число шаров с 15 до 6 ... То-то ... так что за 7 испытаний ну никак нельзя. Да и за 8 тоже.

9-10 - где-то так ...

trex7373
  • trex
  • Киновед
  • Thu, 04 Oct 2012 21:06:51 +0400

Я просто попросил пояснить, откуда из строчки

3,2-3,2 ... 2

получилась строчка

2,1-2,1 ... 2

И что вв них эти цифры обозначают, если не число шаров в кучке?

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

Все ты правильно понял. Зачем лишние вопросы?

trex7373
  • trex
  • Киновед
  • Thu, 04 Oct 2012 21:16:52 +0400

Пойдем "от обратного" ...

Сколько может понадобиться испытаний, чтобы проверить 3 шара и найти среди них 2 радиоактивных?
А если шаров 4? А если 5, 6?

Легко показать. что в случае 6 шаров нам может понадобиться 6 испытаний. А если шаров 7, то и этого мало.

А теперь попробуй за 1 испытание уменьшить число шаров с 15 до 6 ... То-то ... так что за 7 испытаний ну никак нельзя. Да и за 8 тоже.

9-10 - где-то так ...

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

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

rammsteinfan
  • RAMMSTEIN
  • Киновед
  • Thu, 04 Oct 2012 21:25:52 +0400

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

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

Pochemuk

Сейчас покажу теоретически, что 8 испытаний может не хватить.

Не очень строго, но, по моему, достаточно ...

rammsteinfan
  • RAMMSTEIN
  • Киновед
  • Thu, 04 Oct 2012 21:51:23 +0400

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

Pochemuk

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

Т.к. следует находить не 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-ти испытаний?

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

rammsteinfan
  • RAMMSTEIN
  • Киновед
  • Thu, 04 Oct 2012 21:59:36 +0400

9-и хватит... я ж привел вам пример худшего расклада... 8-и конечно не обойтись, но 9 точно хватит, при любом раскладе... что такое "sqrt"? корень?

Pochemuk

9-и хватит... я ж привел вам пример худшего расклада... 8-и конечно не обойтись, но 9 точно хватит, при любом раскладе... что такое "sqrt"? корень?

— RAMMSTEIN

Да, это корень.

Тема закрыта.