Euler № 15 проекта

Несмотря на то, что динамическое программирование выглядит привлекательным способом решения проблемы (и делает его интересной задачей кодирования), немного творческого мышления в отношении структур данных дает чтобы дать немедленный ответ.

[остальная часть этого, по сути, является объяснением того, почему ответ Тима Гудмана лучший, для некоторого значения "лучший"]
Если у нас есть сетка nXm, мы можем представить каждый допустимый маршрут из угла в угол в виде битовой строки n + m, используя либо 0, либо 1 для представления «вниз». Немного подумав, можно подумать, что точное количество маршрутов - это количество способов взять N элементов из N + M элементов, и это, для удобства, оказывается стандартным простым комбинаторным M над N.

Итак, для любого N + M прямоугольник, количество возможных маршрутов из верхнего левого угла в нижний правый угол равно (n + m) (n + m-1) ... (m + 1) / ( п * (п-1) * ... 1).

Самая быстрая программа - это та, которая не должна хранить очень много, много использовать для хранения и (в идеале) имеет ответ в закрытой форме.

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

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

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

Быстрое решение без программирования (на основе комбинаторики)

Я так понимаю, что «без возврата» означает, что мы всегда либо увеличиваем x, либо увеличиваем y.

Если это так, то мы знаем, что всего у нас будет 40 шагов, чтобы достичь финиша - 20 увеличений по x, 20 увеличений по y.

Единственный вопрос в том, какие из 40 увеличивают x. Проблема сводится к следующему: сколькими различными способами вы можете выбрать 20 элементов из набора из 40 элементов. (Элементы: шаг 1, шаг 2 и т. Д., И мы выбираем, скажем, те, которые увеличиваются по x).

Для этого есть формула: это биномиальный коэффициент с 40 сверху и 20 снизу.Формула 40! / ((20!) (40-20)!) , другими словами 40! / (20!) ^ 2 . Вот ! представляет собой факториал. (например, 5! = 5 * 4 * 3 * 2 * 1 )

Отмена одного из 20! и часть 40 !, это становится: (40 * 39 * 38 * 37 * 36 * 35 * 34 * 33 * 32 * 31 * 30 * 29 * 28 * 27 * 26 * 25 * 24 * 23 * 22 * 21) / (20 * 19 * 18 * 17 * 16 * 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) . Таким образом, задача сводится к простой арифметической. Ответ: 137 846 528 820 .

Для сравнения обратите внимание, что (4 * 3) / (2 * 1) дает ответ из их примера, 6 .

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

Вы можете увидеть проблему в расположении ряда «правильных» и «вниз», при этом опасаясь, что не следует пересчитывать несколько раз идентичные расположения.
Например, решения проблемы размера 2 (указанные на изображениях в вопросе) можно увидеть следующим образом:

→→↓↓  
→↓→↓
→↓↓→
↓→→↓
↓→↓→
↓↓→→

Итак, для любой сетки со стороной n вы можете найти решение с помощью комбинаторики :

from math import factorial
n = 20
print factorial(2*n)/(factorial(n)*factorial(n))

2n! это количество комбинаций 20 → + 20 ↓, а два n! учитывать идентичные способы расположения знаков → и ↓.

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

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

long Fib(n) 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
}

Вы просите это вычислить Fib (5). Это вычисляет Fib (4) и Fib (3). Вычисление Fib (4) вычисляет Fib (3) и Fib (2). Вычисление Fib (3) вычисляет Fib (2) и Fib (1). Вычисление Fib (2) вычисляет Fib (1) и Fib (0). Теперь вернемся и снова вычислим Fib (2) . Затем мы возвращаемся и снова вычисляем Fib (3) . Огромное количество пересчетов.

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

static Func<A, R> Memoize(this Func<A, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<A, R>();
    return (A a)=>
    {
        R r;
        if(!dictionary.TryGetValue(a, out r))
        { // cache miss
            r = f(a);
            dictionary.Add(a, r);
        }
        return r;
    };
}

Теперь мы немного переписываем Fib:

Func<long, long> Fib = null;
Fib = (long n) => 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
};

Хорошо, у нас есть немемоизованная функция. Теперь волшебство:

Fib = Fib.Memoize();

И бум, когда мы вызываем Fib (5), теперь мы выполняем поиск по словарю. 5 отсутствует в словаре, поэтому мы вызываем исходную функцию. Это вызывает Fib (4), который выполняет еще один поиск в словаре и пропускает. Это вызывает Fib (3) и так далее. Когда мы возвращаемся к вызову Fib (2) и Fib (3) во время секунд , результаты уже находятся в словаре, поэтому мы не вычисляем их повторно.

Написание версии с двумя аргументами:

static Func<A1, A2, R> Memoize(this Func<A1, A2, R>) { ... }

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

progress = progress.Memoize();

, и внезапно ваша производительность увеличится без потери читабельности исходного алгоритма.

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

Кстати, вы можете еще больше повысить свою производительность, осознав, что 2x3 будет иметь такое же количество путей, что и 3x2. Ваша функция запоминания, похоже, учитывает только строку, которая представляет собой точно столбцы x строки. Однако вы можете включить в свое запоминание, чтобы указать общие пути для ключа 2x3, а также 3x2.

Таким образом, когда вы запоминаете 4x2 и т. Д., Он автоматически заполняет 2x4 таким же количеством путей. Это сократит ваше время, так как вы уже вычислили все пути через эту область поверхности однажды, так зачем делать это снова?

Мое решение было неожиданным, но довольно легким для понимания:

Количество маршрутов к данному перекрестку в сетке - это сумма количества маршрутов к двум его соседям.

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

для x или y = 0: сетка [x, y] = 1
для x и y> = 1: сетка [x, y] = сетка [x-1, y] + сетка [x, y -1]

Итак, после перебора всех квадратов окончательный ответ содержится в сетке [20,20].

Вы фактически вычисляете каталонские числа , для которых доступна замкнутая формула с использованием ряда Тейлора.

Итак, одна программа, вычисляющая решение, могла бы вычислить биномиальные коэффициенты, которые сложно получить правильно, если у вас нет класса BigInt ...