Задачка

28?

Откуда 28?

Это если муравей бегает целенаправленно. А если он случайным образом блуждает по квадратам? Мат. ожидание какое?

Если случайно, то тогда не решусь ответить. Это да, если целенаправленно

Прикинув самый оптемальный путь, посчитал. Хотя могу жестоко ошибатся

Мат. ожидание какое?

Да, там точный ответ давать не нужно. Есть даже решение на яве с использованием Markov Chain:

http://luckytoilet.wordpress.com/2010/03/06/project-euler-280/

Только, блин, проблема в том, что мы яву еще не учили )))

2+(4+4+1)*2+4+3+4+4+4+1+4 вроде...

>Это если муравей бегает целенаправленно.. А если он случайным образом блуждает по квадратам? Мат. ожидание какое?

фак, я думал наименьшее число шагов нужно искать...

5!*4⁴ = 120*256 = 30720 ?

А можешь объяснить откуда такой вывод?

Блин, на 2 забыл умножить (муравью-то и обратно надо возвращаться).

Вспоминать тервер лень, поэтому просто предполагаю: 4⁴ - количество ходов, необходимых для продвижения с самой нижней клетки к самой верхней (всего на пути 4 клетки, из каждой можно попасть в 4 соседних). Возможно, конечно, что вариантов меньше, например, 4!.

5! я тоже сдуру ляпнул: первая «ходка» принесет 1 зерно, вторая с вероятностью в 4/5 попадет, куда надо (умножаем 1 на 5/4), далее - 5/3 и т.п., т.е. получаем 5⁴/4! . А вообще, что-то лень думать. Вторник - день тяжелый...

Минимум нужных шагов - можно найти. Максимум - бесконечность, хотя вероятность этого стремится к нулю.

В уме вышло 44, правда не гарантирую, что это оптимально.

Даже если бы он бегал по одному столбцу с равной вероятностью перехода вверх и вниз, все равно ваш результат слишком занижен.

А оптимально и не нужно.

Представьте, что у муравья «нет GPS» и он не запоминает откуда пришел ;)

всего на пути 4 клетки, из каждой можно попасть в 4 соседних

А если он по крайнему ряду идет, то возможности у него 3. Если в углу, то 2. Если развернулся и пошел обратно? если туда сюда ходит тупо?

Вот еще одно решение на яве:

http://luckytoilet.wordpress.com/2010/03/27/project-euler-280-revisited/

Я и говорю, что лень высчитывать точно.

выпил фанты, накидал решатель задачки на с++

в результате, при случайном блуждании получается около 260 ходов. Распределение полученных результатов явно не нормальное. Медиана - 240, ст. отклонение в несколько мильенов ходов, что-то тут не так.

оригинальное условие:

There is a 5×5 grid. An ant starts in the center square of the grid and walks randomly. Each step, the ant moves to an adjacent square (but not off the grid).

In each of the five bottom-most squares, there is a seed. When the ant reaches such a square, he picks up the seed (if he isn’t already carrying one).

When the ant reaches a square in the top-most row while carrying a seed, he drops off the seed (if there isn’t already a seed there).

This ‘game’ ends when all five seeds are in the five squares of the top-most row.

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

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

Вопрос темы в решении без использования языков программирования.

Для этого надо вспоминать помимо тервера еще и физику брауновской частицы (вычисление средней длины пробега), а там и Марковские цепи попрут...

Ага, уже «вспоминаю»:

http://kossi.physics.hmc.edu/courses/p170/Metropolis.pdf

по теме ничего сказать не могу, но в который раз убеждаюсь, что java — это жуткое зло. вот почти тоже самое, но короче и на C:

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

struct ant {
        int seed;
        int x;
        int y;
} ant = { 0, 2, 2 };

int     top[5] = { 0, 0, 0, 0, 0 };
int     bottom[5] = { 1, 1, 1, 1, 1 };

enum    { N, E, S, W, Nworld };

int
main()
{
        int     ntop = 0;
        int     step = 0;
        int     moved;

        srandom(getpid());

        while (ntop < 5) {
                moved = 0;
                do {
                        switch (random() % Nworld) {
                        case N: if (ant.y > 0) { --ant.y; moved = 1; } break;
                        case E: if (ant.x < 4) { ++ant.x; moved = 1; } break;
                        case S: if (ant.y < 4) { ++ant.y; moved = 1; } break;
                        case W: if (ant.x > 0) { --ant.x; moved = 1; } break;
                        }
                } while (moved == 0);
                ++step;

                if (ant.y == 4 && ant.seed == 0 && bottom[ant.x] == 1) {
                        bottom[ant.x] = 0;
                        ant.seed = 1;
                }

                if (ant.y == 0 && ant.seed == 1 && top[ant.x] == 0) {
                        top[ant.x] = 1;
                        ant.seed = 0;
                        ++ntop;
                }
        }

        printf("steps: %d\n", step);

        return 0;
}

Классические цепи Маркова. Нумеруешь ячейки от «1» до «25». Строишь стохастическую матрицу размером 25*25. Матрица выйдет разреженной (ведь переход возможен лишь с соседних клеток).

Суммируешь по всем интересующим тебя траекториям, получится громоздень в виде суммы произведений тех или иных элементов степеней стохастической матрицы. Там может аналитически что-нибудь упростится, хотя вряд ли - условия слишком кривые, чтобы ответ был «ровным».

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

А ещё можно найти предел стохастической матрицы P^inf, просуммировать её строки (отвечающие переходу «из»), нормировать их на единицу если нужно, и получить 25 величин P_(i,j), равных средней вероятности нахождения муравья на той или иной клетке за ход. Тогда приближенно ожидаемое число ходов равно A*(1/P_(5,1)+1/P_(5,2)+...+ 1/P_(5,5)+1/P_(1,1)+1/P_(1,2)+... +1/P_(1,5)) где A - множитель, равный 10!/(5!)^2 и возникающий из-за того, что нам нужна определенная последовательность посещения клеток.

Выражение получится заниженным, так как он всегда стартует с краев.

Матрица выйдет

10265*10265 - вот таким размером?

У чувака это съело 2 гига оперативы и 19 минут используя яву.

Спасибо огромное )

Извиняюсь, что все таки лезу с вопросом по теме, но что нужно добавить в этот код, чтобы он дал ответ точностью до шестой цифры после запятой? Я просто не весь вопрос в шапке написал... Если лень разбираться, не берись.

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

>>10265*10265 - вот таким размером?

Да нет же, 25*25. Откуда 10265?

Кстати, грубая оценка дает ~13334 ходов, а еще грубее - 30720.

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

44

Без коэффициента A выходит 499 шагов, что идеально совпадает с результатами эксперимента. С учетом A получается 125665 ходов - неправдоподобно.

Так что A тут, видимо, не нужен. Ответ (1/P_(5,1)+1/P_(5,2)+...+ 1/P_(5,5)+1/P_(1,1)+1/P_(1,2)+... +1/P_(1,5)) = ~ 499 шагов.

A:10!/(5!)^2;

st:matrix(
[0,0.5,0,0,0,0.5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0.33,0,0.33,0,0,0,0.33,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0.33,0,0.33,0,0,0,0.33,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0.33,0,0.33,0,0,0,0.33,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0.5,0,0,0,0,0,0.5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0.33,0,0,0,0,0,0.33,0,0,0,0.33,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0.33,0,0,0,0.33,0,0,0,0,0,0.33,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0.33,0,0,0,0,0,0.33,0,0,0,0.33,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0.33,0,0,0,0.33,0,0,0,0,0,0.33,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0.33,0,0,0,0,0,0.33,0,0,0,0.33,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0.25,0,0,0,0.25,0,0.25,0,0,0,0.25,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.33,0,0,0,0.33,0,0,0,0,0,0.33],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.5,0,0,0,0,0,0.5,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.33,0,0,0,0.33,0,0.33,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.33,0,0,0,0.33,0,0.33,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.33,0,0,0,0.33,0,0.33],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.5,0,0,0,0.5,0]
);

st_inf:st^^100;

P:matrix(
[sum(st_inf[i,1],i,1,25)/25,sum(st_inf[i,2],i,1,25)/25,sum(st_inf[i,3],i,1,25)/25,sum(st_inf[i,4],i,1,25)/25,sum(st_inf[i,5],i,1,25)/25],
[sum(st_inf[i,6],i,1,25)/25,sum(st_inf[i,7],i,1,25)/25,sum(st_inf[i,8],i,1,25)/25,sum(st_inf[i,9],i,1,25)/25,sum(st_inf[i,10],i,1,25)/25],
[sum(st_inf[i,11],i,1,25)/25,sum(st_inf[i,12],i,1,25)/25,sum(st_inf[i,13],i,1,25)/25,sum(st_inf[i,14],i,1,25)/25,sum(st_inf[i,15],i,1,25)/25],
[sum(st_inf[i,16],i,1,25)/25,sum(st_inf[i,17],i,1,25)/25,sum(st_inf[i,18],i,1,25)/25,sum(st_inf[i,19],i,1,25)/25,sum(st_inf[i,20],i,1,25)/25],
[sum(st_inf[i,21],i,1,25)/25,sum(st_inf[i,22],i,1,25)/25,sum(st_inf[i,23],i,1,25)/25,sum(st_inf[i,24],i,1,25)/25,sum(st_inf[i,25],i,1,25)/25]
);

otvet_1:(1/P[5,1]+1/P[5,2]+1/P[5,3]+1/P[5,4]+1/P[5,5]+1/P[1,1]+1/P[1,2]+1/P[1,3]+1/P[1,4]+1/P[1,5]);

otvet_2:A*otvet_1;

Мне тоже кажется маловато.

Эксперимент в кодом beastie http://www.linux.org.ru/jump-message.jsp?msgid=5455786&cid=5457443 дает 430 и стандартное отклонение ~100, что сходится с грубыми прикидками тут http://www.linux.org.ru/jump-message.jsp?msgid=5455786&cid=5458317.

Все-таки неочевидно, что факториалы не нужны. Ну и ответ вышел завышенным, а не заниженным, как можно было ожидать.