Здравствуйте, sugarde, Вы писали:
S>Т.е. 2*N +- 1 на четность/нечётность N — должно хватить. S>Два обстрела слева направо гарантировано убивают мыша.
Супер решение!
Маленькое уточнение: мне кажется, что с данным подходом максимальное кол-во необходимых выстрелов будет равно (N-2)*2.
А более точно алгоритм "охоты" можно изложить так (нумерация ящиков с 0 до N-1):
1. Если N нечетно, то стреляем два раза подряд с 1 по N-2
2. Если N четно, то стреляем снаала с 1 по N-2, потом с N-2 по 1 (то есть слева направо, а потом справа налево)
В обоих случаях по "крайним" ящикам (0 и N-1) никогда стрелять не придется
PS Ну и специально для геймеров, новейший шутер "Шредеровска мышь" (на J):
Формат управления огнем (в результате получаем возможное положение мыши в ящиках после пальбы):
[последовательность выстрелов] play [количество ящиков]
Пример (стреляем в первый (второй слева) и во второй ящик — после чего 100% мышь не может быть живой в первом и третьем, но умная (или везучая) может быть в нулевом и во втором)
1 2 play 4
MXMX
Середина охоты в 6-ти ящиках:
1 2 3 play 6
XMXMMM
1 2 3 4 play 6
MXMXMX
1 2 3 4 4 play 6
XMXMXX
Примеры правильных серий выстрелов для разных N:
1 1 play 3
XXX
1 2 2 1 play 4
XXXX
1 2 3 1 2 3 play 5
XXXXX
1 2 3 4 5 6 6 5 4 3 2 1 play 8
XXXXXXXX
_>>Почему не может быть так (если всего 4 коробки — 0, 1, 2, 3, мышь пряталась в 0): V>Для четного количества коробок второй раунд надо начинать с четной коробки, то есть с первой. Мышь без шансов!
Здравствуйте, Кодт, Вы писали:
К>Сейчас мозголомку загадали...
К>N коробок стоят вплотную, в ряд. К>В одной из коробок сидит мышь. К>Между коробками прогрызены переходы.
К>У человека есть ружьё, из которого он стреляет по коробкам. К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).
К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.
К>Хак в виде стрельбы в торец ряда — запрещён.
Стреляем в ячейцу №2 два раза, затем в ячейку №4 два раза и так далее до N
Когда ряд пройден до конца, стреляем в №1 два раза, затем №3 два раза и так до N
В чем же смысл. Если изначально мышь притаилась в четной ячейке, то после каждой пары выстрелов она снова будет оказываться в четной ячейке. B мы будем гнать ее от начала линии ящиков в концу. Аналогичный подход на случай если мышь сидела в нечетной ячейке.
Здравствуйте, Нэчер, Вы писали:
Н>Стреляем в ячейцу №2 два раза, затем в ячейку №4 два раза и так далее до N
1 2 3 4 5 6 7 8 .....
m m m m m m m m ..... - изначально мышь может быть где угодно
\!/ X X X X X X - выстрел в ячейку №2 (!) и перебегания мыши влево-вправо
. m m m m m m m .....
!/ X X X X X X - ещё один выстрел
. m m m m m m m ..... - оказался лишним
/ X \!/ X X X X - после выстрела в №4
m m m m m m m m ..... - мышь снова может быть в любой коробке!
Нужно пойти иным путём.
Выбиваем коробки №2, 3, 4, и т.д. (№1 выбивать бессмысленно, поскольку мышь туда сразу же перебежит).
1 2 3 4 5 6 7 8 .....
m m m m m m m m .....
\!/ X X X X X X
. m m m m m m m
/ \!/ X X X X X
m . m m m m m m
\ / \!/ X X X X
. m . m m m m m
/ \ / \!/ X X X
m . m . m m m m
.....................
m . m . m . m . ..... - мышь сидит в чётных (либо нечётных) коробках
! / \ / \ / \ / - начинаем по-очереди их выбивать
. m . m . m . m
! / \ / \ / \
. . m . m . m .
! / \ / \ /
. . . m . m . m
! / \ / \
. . . . m . m .
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Перекуём баги на фичи!
Re[3]: Дездемона, там мышь!
От:
Аноним
Дата:
07.10.08 15:42
Оценка:
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Нэчер, Вы писали:
Н>>Стреляем в ячейцу №2 два раза, затем в ячейку №4 два раза и так далее до N
К>
К>1 2 3 4 5 6 7 8 .....
К>m m m m m m m m ..... - изначально мышь может быть где угодно
К> \!/ X X X X X X - выстрел в ячейку №2 (!) и перебегания мыши влево-вправо
К>. m m m m m m m .....
К> !/ X X X X X X - ещё один выстрел
К>. m m m m m m m ..... - оказался лишним
К> / X \!/ X X X X - после выстрела в №4
К>m m m m m m m m ..... - мышь снова может быть в любой коробке!
К>
Допустим, что изначально мышь в четной коробке. После двух подряд выстрелов в 4, мышь не может быть в 2 и в 4 (живой, по крайней мере).
Если мышь в нечетной коробке, то она будет подстрелена на втором заходе, когда стрелять будем по нечетным.
К>Нужно пойти иным путём. К>Выбиваем коробки №2, 3, 4, и т.д. (№1 выбивать бессмысленно, поскольку мышь туда сразу же перебежит). К>
К>1 2 3 4 5 6 7 8 .....
К>m m m m m m m m .....
К> \!/ X X X X X X
К>. m m m m m m m
К> / \!/ X X X X X
К>m . m m m m m m
К> \ / \!/ X X X X
К>. m . m m m m m
К> / \ / \!/ X X X
К>m . m . m m m m
К>.....................
К>m . m . m . m . ..... - мышь сидит в чётных (либо нечётных) коробках
К>! / \ / \ / \ / - начинаем по-очереди их выбивать
К>. m . m . m . m
К> ! / \ / \ / \
К>. . m . m . m .
К> ! / \ / \ /
К>. . . m . m . m
К> ! / \ / \
К>. . . . m . m .
К>
Если делать только один выстрел по коробке, то мышь может легко перебежать в толькочто обстреленную коробку.
Здравствуйте, <Аноним>, Вы писали:
А>Допустим, что изначально мышь в четной коробке. А>После двух подряд выстрелов в 4, мышь не может быть в 2 и в 4 (живой, по крайней мере).
Да щас!
1 2 3 4 5 6 7
. m m m m m m - мышь может быть в любой коробке, кроме первой
! - стреляем
. m m . m m m - сразу после выстрела
/ X \ / X X - мышь перебегает налево-направо (направление показано чёрточкой)
m m m m m m m
Компактно это записывается так:
1 2 3 4 5 6 7
. m m m m m m
/ X \!/ X X
m m m m m m m
Правила записи очень просты: косая черта не может выходить из пустой коробки (.) и из коробки, по которой произведён выстрел (!)
А>Если делать только один выстрел по коробке, то мышь может легко перебежать в толькочто обстреленную коробку.
Зато она не может выбежать из только что обстрелянной коробки.
А>Рассмотрим для примера случай с N=4
Рассмотрим.
1 2 3 4
m m m m
\!/ X - первый выстрел
. m m m
!/ X - второй выстрел...
. m m m ...был лишним, так как состояние осталось тем же самым
/ X \! - третий выстрел - по коробке №4...
m m m m ...привёл нас в исходную позицию
А правильнее было так
1 2 3 4
m m m m
\!/ X - №2
. m m m
/ \!/ - №3
m . m .
! / \ - №1
. m . m
! / - №2
. . m .
! - №3
. . . .
Для каждой коробк найдём, вероятность того что на К-м ходе мышь находится в ней, будем стрелять в коробку где мышь находится с максимальной вероятностью.
На первом ходе вероятности равны для всех коробок, всё равно куда стрелять. На втором и последующих, если ничего не путаю, максимум вероятноятности будет смещаться к краям ряда коробок, т.е. будем стрелять по правой и левой коробкам поочерёдно.
Посчитал полным перебором для небольших N — оптимальных стратегий совсем немного.
Коробки нумеруем от 0 до N-1, в каждой строчке — серия выстрелов минимальной длины, приводящая к гарантированной гибели мыша.
является оптимальным.
Только нужна небольшая поправка: если первая серия выстрелов была слева направа, то на втором этапе стрелять надо не "слева направо", а "справа налево" — тогда решение будет универсальным, не зависящим от чётности N.
Число требуемых выстрелов, как уже упоминалось
Здравствуйте, Кодт, Вы писали:
К>Сейчас мозголомку загадали...
К>N коробок стоят вплотную, в ряд. К>В одной из коробок сидит мышь. К>Между коробками прогрызены переходы.
К>У человека есть ружьё, из которого он стреляет по коробкам. К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).
К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.
К>Хак в виде стрельбы в торец ряда — запрещён.
Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Здравствуйте, Кондраций, Вы писали:
К>Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.
Здравствуйте, Cider, Вы писали:
C>Здравствуйте, Кондраций, Вы писали:
К>>Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.
C>Гранатой ее, чего уж мелочиться
Это не по условиям задачи. А вот светошумовой патрон (есть такие?) не помешал бы! Главное, чтобы мышь испугалась конкретно .
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Здравствуйте, gbear, Вы писали:
G>Т.е. как уже говорилось для четных N отсреливать со 2ой по N-1ую и с N-1ой по 2ую.
Замечательно то, что этот рецепт универсален, он работает как для четных N, так и для нечетных!
В самом деле, рассмотрим оба случая (нумерация ячеек от 1 до N):
N четно.
После прохода со 2-й по N-1ую ячейку имеем два возвоможных исхода: либо мышь уже убита, либо она изначально находилась в нечетной ячейке. Если мышь еще жива, то, поскольку мы совершили четное количество выстрелов, в настоящий момент времени она находится снова в нечетной ячейке. Поскольку N четно, то N-1 нечетно. И если мы теперь выполним серию выстрелов N-1ой по 2ую, то мышь будет убита наверняка.
N нечетно.
После прохода со 2-й по N-1ую ячейку имеем точно такие же возвоможные исходы, как и для первого случая: либо мышь уже убита, либо она изначально находилась в нечетной ячейке. Если мышь еще жива, то, поскольку мы совершили нечетное количество выстрелов, в настоящий момент времени она находится уже в четной ячейке. Поскольку N нечетно, то N-1 четно. И если мы теперь выполним серию выстрелов N-1ой по 2ую, то мышь будет убита наверняка.
Кроме того, что это алгоритм автоматически разруливает четность/нечетность общего числа ячеек, он гарантирует решение задачи за минимальное количество итераций — N*2 — 4. Может кто-нибудь предложить более быстрое решение?
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, Кодт, Вы писали:
К>Сейчас мозголомку загадали...
К>N коробок стоят вплотную, в ряд. К>В одной из коробок сидит мышь. К>Между коробками прогрызены переходы.
К>У человека есть ружьё, из которого он стреляет по коробкам. К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).
К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.
К>Хак в виде стрельбы в торец ряда — запрещён.
Возможно покажусь Вам немного банальным, но... "поджечь с двух сторон" (с)
Здравствуйте, Кодт, Вы писали:
К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.
Как-то сложно все решают: автоматы, двойные проходы, анализы четности... Я решил, почитал ответы и ужаснулся
Пронумеруем коробки от 1 до N (N>2). Тогда последовательность выстрелов будет:
2,2,3,3,...,N-1,N-1. Максимум 2N-4 выстрела.
Здравствуйте, Sinus, Вы писали:
S>Как-то сложно все решают: автоматы, двойные проходы, анализы четности... Я решил, почитал ответы и ужаснулся
Вот абсолютно согласен! У каждой задачи есть решение — очевидное, простое...
S>Пронумеруем коробки от 1 до N (N>2). Тогда последовательность выстрелов будет: S>2,2,3,3,...,N-1,N-1. Максимум 2N-4 выстрела.
... и неверное.
мышь до выстрел мышь после
4 2 3
3 2 2
2 3 1
1 3 2