_sk_
_sk_ личный блог
04 января 2017, 07:55

Re: Тестик. Наивный Теорвер.

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

Большая просьба, особенно к А.Г.))), не писать сразу решение)))

Поскольку времени подумать над задачкой всем заинтересовавшимся было достаточно, пора разобраться с тем, каков же правильный ответ. Ниже приводится решение методом Монте-Карло.


Применим java. Код программы, которую можно написать за 10-15 минут, приведён ниже. Идея проста: моделируем ходы робота по листу и регистрируем, сколько раз он вышел за край страницы 108, а сколько раз перешёл на страницу 107, исходя из координат его текущего положения. После многократного моделирования можно определить частоту попадания на 107-ю страницу, которая по закону больших чисел будет приближаться к вероятности события при увеличении числа независимых экспериментов.

package com.company.experiments;

import java.util.Random;

class Walker {
    /**
     *  Датчик случайных чисел.
     */
    final Random rnd = new Random(1L);
    /**
     * Количество попаданий на 107-ю страницу.
     */
    int successes = 0;
    /**
     * Количество выходов за край страницы.
     */
    int failures = 0;

    public static void main(final String[] args) {
        final Walker walker = new Walker();
        walker.test(100_000_000);
        System.out.println(walker.getFrequency());
    }

    void test(final int iterations) {
        for (int i = 0; i < iterations; i++) {
            walk();
        }
    }

    void walk() {
        int x = 5;
        int y = 5;
        while (true) {
            // Определить направление движения и сделать шаг
            final int d = rnd.nextInt(4);
            if (d == 0) {
                x++;
            } else if (d == 1) {
                x--;
            } else if (d == 2) {
                y++;
            } else if (d == 3) {
                y--;
            }
            // Проверить выход за пределы 108-й страницы
            if (y == -1 || y == 11 || x == 11) {
                failures++;
                return;
            }
            // Проверить попадание на 107-ю страницу
            if (x == -1) {
                successes++;
                return;
            }
        }
    }

    double getFrequency() {
        return (double) successes / (successes + failures);
    }
}

Запускаем программу, через некоторое время видим ответ: после 100 млн. итераций частота попадания на 107-ю страницу равна 0.25003493.

Мы знаем, что метод Монте-Карло даёт погрешности, так что можно предположить, что ответ задачи — это 0.25.

А вот теперь можно уже, зная ответ, попытаться доказать его математически. Пусть существует какая-то траектория, двигаясь по которой робот приходит на страницу 107. Если повернуть эту траекторию на 90 градусов, 180 градусов или 270 градусов, то робот по повёрнутой траектории выйдет за пределы 108-й страницы. Тут существенно используется факт того, что страница квадратная, а робот стартует из центра. Если же изначально взять траекторию, приводящую к выходу за границу, то её всегда можно повернуть так, чтобы в результате робот пришёл на 107-ю страницу. Итого имеем разбиение всех траекторий на 4 класса: выход на 107-ю страницу, выход за верхний край, выход за нижний край и выход за боковой край 108-й страницы. В каждом классе одинаковое число траекторий. Для каждой траектории одного класса имеются по одной траектории из каждого из оставшихся 3-х классов с той же вероятностью движения по ней. Поскольку выход куда-нибудь происходит наверняка, то вероятности каждого из классов одинаковы, так что ответом задачи будет 1/4 = 0.25.

А можно просто поиграться с программой. Например, узнать, что будет, если листы книги не квадратные и/или робот стартует не из центра.

Чаще используйте метод Монте-Карло! Он и в трейдинге тоже полезен.
30 Комментариев
  • finstrateg
    04 января 2017, 08:22
    Можете посчитать то же самое с условием, что роботу разрешено «перелистывать страницы»? т.е. поле страницы имеет бесконечный боковой размер (можно ограничиться, например 1000 клеточек).
    У меня логически получилось 1/3
  • П М
    04 января 2017, 09:43
    действительно, если страница квадратная, и нам нужен 1 из 4х исходов, с равными вероятностями...
    но без программы это было не так понятно. видать я не обратил внимание на квадратность.

    а как это пересекается с графиками.?..
  • Igr
    04 января 2017, 10:02

    я рассуждал так, у робота 4 направления, они равновероятны, значит вероятность 1 направления 25% 

    вот и всё

  • wrmngr
    04 января 2017, 10:23
    Это не спортивное поведение)

Активные форумы
Что сейчас обсуждают

Старый дизайн
Старый
дизайн