Re[5]: Дездемона, там мышь!
От: Аноним  
Дата: 04.10.08 03:30
Оценка: 4 (1)
Здравствуйте, 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):
   mmove =: [: +./ _1 1 (|.!.0"0 1) ]
   shot =: 0:`[`]}
   play =: ([: {&'XM' [: > [: mmove @ shot&.>/ |.@(;;/)~) $&1

Формат управления огнем (в результате получаем возможное положение мыши в ящиках после пальбы):
[последовательность выстрелов] 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


Enjoy
Re[6]: Дездемона, там мышь!
От: russian_bear  
Дата: 04.10.08 16:14
Оценка: :))) :))
_>>Почему не может быть так (если всего 4 коробки — 0, 1, 2, 3, мышь пряталась в 0):
V>Для четного количества коробок второй раунд надо начинать с четной коробки, то есть с первой. Мышь без шансов!

Все-таки все математики чокнутые люди
Re[2]: Дездемона, там мышь!
От: Кодт Россия  
Дата: 06.10.08 07:12
Оценка:
Здравствуйте, Хэлкар, Вы писали:

Х>По простреленным коробкам мышь не бегает?


Бегает.
Стреляем вслепую, через дырки от старых пуль не смотрим.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Перекуём баги на фичи!
Re[7]: Дездемона, там мышь!
От: Трурль  
Дата: 06.10.08 09:00
Оценка:
Здравствуйте, russian_bear, Вы писали:

_>Все-таки все математики чокнутые люди


Это программисты чокнутые. Математик не стал бы с нуля нумеровать.
Re: Дездемона, там мышь!
От: Нэчер  
Дата: 07.10.08 11:56
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Сейчас мозголомку загадали...


К>N коробок стоят вплотную, в ряд.

К>В одной из коробок сидит мышь.
К>Между коробками прогрызены переходы.

К>У человека есть ружьё, из которого он стреляет по коробкам.

К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.


К>Хак в виде стрельбы в торец ряда — запрещён.


Стреляем в ячейцу №2 два раза, затем в ячейку №4 два раза и так далее до N
Когда ряд пройден до конца, стреляем в №1 два раза, затем №3 два раза и так до N

В чем же смысл. Если изначально мышь притаилась в четной ячейке, то после каждой пары выстрелов она снова будет оказываться в четной ячейке. B мы будем гнать ее от начала линии ящиков в концу. Аналогичный подход на случай если мышь сидела в нечетной ячейке.
Re[2]: Дездемона, там мышь!
От: Кодт Россия  
Дата: 07.10.08 13:43
Оценка:
Здравствуйте, Нэчер, Вы писали:

Н>Стреляем в ячейцу №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 .
К>


Если делать только один выстрел по коробке, то мышь может легко перебежать в толькочто обстреленную коробку.

Рассмотрим для примера случай с N=4
Re[4]: Дездемона, там мышь!
От: Кодт Россия  
Дата: 07.10.08 16:30
Оценка:
Здравствуйте, <Аноним>, Вы писали:

А>Допустим, что изначально мышь в четной коробке.

А>После двух подряд выстрелов в 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
. . . .
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Перекуём баги на фичи!
Re[5]: Дездемона, там мышь!
От: Нэчер  
Дата: 07.10.08 16:54
Оценка:
Здравствуйте, Кодт, Вы писали:

Re[5]: Дездемона, там мышь!
От: gbear Россия  
Дата: 08.10.08 09:55
Оценка: 10 (1)
Здравствуйте, Кодт, Вы писали:


К>А правильнее было так

К>
К>1 2 3 4
К>m m m m
К> \!/ X   - №2
К>. m m m
К> / \!/   - №3
К>m . m .
К>!  / \   - №1
К>. m . m
К>  !  /   - №2
К>. . m .
К>    !    - №3
К>. . . .
К>


Таки правильнее:
1 2 3 4
m m m m
 \!/ X   - №2
. m m m
 / \!/   - №3
m . m .
\   !    - №3
. m . .
  !      - №2
. . . .


Т.е. как уже говорилось для четных N отсреливать со 2ой по N-1ую и с N-1ой по 2ую. И в принципе, понятно почему...

---
С уважением, Сиваков Константин.
Re: Дездемона, там мышь!
От: WinterMute Россия http://yarrr.ru
Дата: 10.10.08 12:41
Оценка:
Для каждой коробк найдём, вероятность того что на К-м ходе мышь находится в ней, будем стрелять в коробку где мышь находится с максимальной вероятностью.

На первом ходе вероятности равны для всех коробок, всё равно куда стрелять. На втором и последующих, если ничего не путаю, максимум вероятноятности будет смещаться к краям ряда коробок, т.е. будем стрелять по правой и левой коробкам поочерёдно.
Re[2]: Дездемона, там мышь!
От: WinterMute Россия http://yarrr.ru
Дата: 10.10.08 13:55
Оценка:
Вообще, вот программа которая расчитывает вероятность нахождения мыши, на каждом шаге:

Вывод который можно сделать -- на практике, стрельба по центральному ящику очень неплохая стратегия.

#include "stdafx.h"
#include <vector>

void calc_mouse_place( const std::vector<double>& init_prob, std::vector<double>& res )
{
    if( init_prob.empty() ) return;

    const size_t sz = init_prob.size();

    res.clear();
    res.resize( sz, 0.0 );

    for( int i = 0; i < int(sz); i++ )
    {
        double v = init_prob[i] / 2;

        int prev = i - 1;
        int next = i + 1;

        if( prev < 0 ) // слева стенка
        {
            prev = i + 1;
            if( prev >= sz ) prev = i; // мышке некуда дёргаться
        }
        
        if( next >= sz ) // направо стенка
        {
            next = i - 1;
            if( next < 0 ) next = i; // мышке некуда дёргаться
        }

        res[ prev ] += v;
        res[ next ] += v;
    }
}

void calc_mouse_place( std::vector<double>& arr, size_t sz, int steps )
{
    const double init_prob = 1.0 / double(sz);

    arr.clear();
    arr.resize( sz, init_prob );

    std::vector<double> arr2;

    for( int s = 0; s < steps; s++ )
    {
        calc_mouse_place( arr, arr2 );
        arr = arr2;
    }
}

void print_prob( const std::vector<double>& arr )
{
    for( size_t i = 0; i < arr.size(); i++ )
    {
        printf( "%2d - %f\n", (int)(i+1), arr[i] );
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<double> arr;

    calc_mouse_place( arr, 20, 2 );
    print_prob( arr );

    return 0;
}
Re: И ты, брутфорс! :)
От: andy1618 Россия  
Дата: 11.10.08 01:31
Оценка: +1
Посчитал полным перебором для небольших N — оптимальных стратегий совсем немного.
Коробки нумеруем от 0 до N-1, в каждой строчке — серия выстрелов минимальной длины, приводящая к гарантированной гибели мыша.

N=4 (0123)
1221
2112

N=5 (01234)
123123
123321
321123
321321

N=6 (012345)
12344321
43211234

N=7 (0123456)
1234512345
1234554321
5432112345
5432154321

Т.е. для чётных N всего 2 оптимальных стратегии, для нечётных — 4.

Таким образом, создаётся впечатление, что решение с "мышами Шрёдингера"
Автор: sugarde
Дата: 03.10.08
является оптимальным.
Только нужна небольшая поправка: если первая серия выстрелов была слева направа, то на втором этапе стрелять надо не "слева направо", а "справа налево" — тогда решение будет универсальным, не зависящим от чётности N.
Число требуемых выстрелов, как уже упоминалось
Автор:
Дата: 04.10.08
— (N-2)*2.
Re: Дездемона, там мышь!
От: Кондраций Россия  
Дата: 14.10.08 12:23
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Сейчас мозголомку загадали...


К>N коробок стоят вплотную, в ряд.

К>В одной из коробок сидит мышь.
К>Между коробками прогрызены переходы.

К>У человека есть ружьё, из которого он стреляет по коробкам.

К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.


К>Хак в виде стрельбы в торец ряда — запрещён.


Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Re[2]: Дездемона, там мышь!
От: Cider Россия  
Дата: 14.10.08 13:19
Оценка:
Здравствуйте, Кондраций, Вы писали:

К>Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.


Гранатой ее, чего уж мелочиться
Cider
Re[3]: Дездемона, там мышь!
От: Кондраций Россия  
Дата: 15.10.08 04:21
Оценка:
Здравствуйте, Cider, Вы писали:

C>Здравствуйте, Кондраций, Вы писали:


К>>Стреляем разрывными в крайнюю, скажем, слева. Испуганная мышь сваливает в крайнюю правую позицию. Там то мы её на втором выстреле и уничтожаем.


C>Гранатой ее, чего уж мелочиться

Это не по условиям задачи. А вот светошумовой патрон (есть такие?) не помешал бы! Главное, чтобы мышь испугалась конкретно .
Сообщение заговорено потомственным колдуном, целителем и магом в девятом поколении!
Модерирование или минусование сообщения ведет к половому бессилию, венерическим заболеваниям, венцу безбрачия и диарее!
Re[6]: Дездемона, там мышь!
От: rg45 СССР  
Дата: 16.10.08 07:52
Оценка:
Здравствуйте, 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. Может кто-нибудь предложить более быстрое решение?
--
Не можешь достичь желаемого — пожелай достигнутого.
Re: Дездемона, там мышь!
От: vadimcher  
Дата: 16.10.08 21:11
Оценка: :))
Здравствуйте, Кодт, Вы писали:

К>Сейчас мозголомку загадали...


К>N коробок стоят вплотную, в ряд.

К>В одной из коробок сидит мышь.
К>Между коробками прогрызены переходы.

К>У человека есть ружьё, из которого он стреляет по коробкам.

К>После каждого выстрела мышь, если в неё не попали, перебегает в соседнюю коробку (какую именно — неизвестно).

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.


К>Хак в виде стрельбы в торец ряда — запрещён.


Возможно покажусь Вам немного банальным, но... "поджечь с двух сторон" (с)

А вот зайца кому, зайца-выбегайца?!
Re: Дездемона, там мышь!
От: Sinus Россия  
Дата: 11.11.08 06:50
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Нужно найти стратегию, позволяющую за минимальное количество ходов гарантированно пристрелить мышь.


Как-то сложно все решают: автоматы, двойные проходы, анализы четности... Я решил, почитал ответы и ужаснулся
Пронумеруем коробки от 1 до N (N>2). Тогда последовательность выстрелов будет:
2,2,3,3,...,N-1,N-1. Максимум 2N-4 выстрела.
Re[2]: Дездемона, там мышь!
От: Кодт Россия  
Дата: 11.11.08 08:58
Оценка: 1 (1)
Здравствуйте, 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

Дальше понятно, что мышь выживет.
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Перекуём баги на фичи!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.