Условия требуют определить сколько выстрелов необходимо произвести, чтобы убить мышь, теперь нужно убить всех мышей, ранее(по условию) мыши плодились только при промохе, теперь и при поподании.
Цитатаnebo ()
Не понимаю про чётность-нечётность
Ну типа при каждом выстреле мыши меняют номера своих посадочных мест, если были в чётных коробках то при промахе(а теперь и при поподании) переходят в нечетные, а то, что это нихера не даёт, т.к не известно начальное положение мыши, это до них не доходит.
К слову, Kreativshik, в рассмотренном Вами варианте, Ваш ответ вроде тоже не совсем верен. Так, при достаточно большом N, отстреляв N/4+1 раз коробку № N/4, охотник смело может переходить на коробку № 3/4 N и гарантированно убить 1 мышь еще 2-3 выстрелами. При этом, охотник знает каково N изначально, а мы нет.
Так, при достаточно большом N, отстреляв N/4+1 раз коробку № N/4
никник, о чем Вы. Если есть N коробок, то чтобы гарантираванно убить мышь нужно произвести ⌊N/2⌋+1 выстрелов постоянно стреляя в ⌈N/2⌉ коробку, оптимальность этого алгоритма очевидна при малых N, для больших N доказывается по индукции. В чем у Вас проблемы?
что убив клон, мы запускаем клонирование других оставшихся.
Из этого можно сделать вывод, что при попадании мышь тоже клонируется. Хотя, конечно,включив фантазию, можно прочесть так: что убив клон, мы запускаем клонирование других оставшихся, допустив затем холостой выстрел.
Сообщение отредактировал никник - Воскресенье, 04.10.2015, 00:13
Переделана мною классическая задача. На одном из форумов она выложена, но пока никто не справился))
Есть N картонных коробок, стоящих вплотную друг к другу в один ряд. В одной из них суперпозиционная мышь, прогрызшая себе ходы из каждой коробки в соседние. Из крайних коробок прохода наружу нет. Охотнику дали ружье и неограниченное количество патронов, чтобы убить клонирующуюся мышь при следующих условиях: 1) изначально охотник не знает, в какой коробке сидит мышь; 2) если охотник выстрелил в коробку, где сидит мышь, то мышь считается убитой (на её клоны это не распространяется); 3) если охотник выстрелил в какую-либо коробку,то после выстрела мышь ( не убитая , см. п.2) материализуется в двух соседних коробках, но так, что в одной коробке более одной мыши находиться не может. Сколько выстрелов понадобится охотнику, чтобы гарантированно убить мышь?
Так опровергните. Если есть 20 коробок, то сделав 11 выстрелов в 10-ю коробку, я однозначно могу заявить, что мышь убита, т.к где бы она не находилась изначально, 10 выстрелов будет достаточно, чтобы мышь попала в 10-ю коробку, а 11-ым выстрелом она будет убита.
Сообщение отредактировал Kreativshik - Воскресенье, 04.10.2015, 00:19
