c# - 欧拉计划 #15

Question

昨晚我试图解决challenge #15 from Project Euler :

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

_{(source: projecteuler.net)}

How many routes are there through a 20×20 grid?

我觉得这不应该这么难，所以我写了一个基本的递归函数:

const int gridSize = 20;

// call with progress(0, 0)
static int progress(int x, int y)
{
    int i = 0;

    if (x < gridSize)
        i += progress(x + 1, y);
    if (y < gridSize)
        i += progress(x, y + 1);

    if (x == gridSize && y == gridSize)
        return 1;

    return i;
}

我验证了它适用于较小的网格，例如 2×2 或 3×3，然后将其设置为运行 20×20 网格。想象一下我的惊讶，5 小时后，该程序仍在愉快地处理数字，但只完成了大约 80%(基于检查其在网格中的当前位置/路线)。

很明显，我的做法是错误的。你会如何解决这个问题？我认为应该使用方程而不是像我这样的方法来解决它，但不幸的是，这不是我的强项。

更新:

我现在有一个工作版本。基本上它缓存之前获得的结果，当一个 n×m block 仍然有待遍历时。这是代码以及一些注释:

// the size of our grid
static int gridSize = 20;

// the amount of paths available for a "NxM" block, e.g. "2x2" => 4
static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>();

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static long progress(long x, long y)
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // create a textual representation of the remaining
    // block, for use in the dictionary
    string block = (gridSize - x) + "x" + (gridSize - y);

    // if a same block has not been processed before
    if (!pathsByBlock.ContainsKey(block))
    {
        // calculate it in the right direction
        if (x < gridSize)
            i += progress(x + 1, y);
        // and in the down direction
        if (y < gridSize)
            i += progress(x, y + 1);

        // and cache the result!
        pathsByBlock[block] = i;
    }

    // self-explanatory :)
    return pathsByBlock[block];
}

调用它 20 次，对于大小为 1×1 到 20×20 的网格产生以下输出:

There are 2 paths in a 1 sized grid
0,0110006 seconds

There are 6 paths in a 2 sized grid
0,0030002 seconds

There are 20 paths in a 3 sized grid
0 seconds

There are 70 paths in a 4 sized grid
0 seconds

There are 252 paths in a 5 sized grid
0 seconds

There are 924 paths in a 6 sized grid
0 seconds

There are 3432 paths in a 7 sized grid
0 seconds

There are 12870 paths in a 8 sized grid
0,001 seconds

There are 48620 paths in a 9 sized grid
0,0010001 seconds

There are 184756 paths in a 10 sized grid
0,001 seconds

There are 705432 paths in a 11 sized grid
0 seconds

There are 2704156 paths in a 12 sized grid
0 seconds

There are 10400600 paths in a 13 sized grid
0,001 seconds

There are 40116600 paths in a 14 sized grid
0 seconds

There are 155117520 paths in a 15 sized grid
0 seconds

There are 601080390 paths in a 16 sized grid
0,0010001 seconds

There are 2333606220 paths in a 17 sized grid
0,001 seconds

There are 9075135300 paths in a 18 sized grid
0,001 seconds

There are 35345263800 paths in a 19 sized grid
0,001 seconds

There are 137846528820 paths in a 20 sized grid
0,0010001 seconds

0,0390022 seconds in total

我接受丹本的回答，因为他帮助我找到了这个解决方案。但也赞成 Tim Goodman 和 Agos :)

奖金更新:

看了Eric Lippert的回答，又看了一眼，稍微重写了一下。基本思想仍然相同，但缓存部分已被取出并放在一个单独的函数中，就像 Eric 的示例一样。结果是一些看起来更优雅的代码。

// the size of our grid
const int gridSize = 20;

// magic.
static Func<A1, A2, R> Memoize<A1, A2, R>(this Func<A1, A2, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<string, R>();
    return (A1 a1, A2 a2) =>
    {
        R r;
        string key = a1 + "x" + a2;
        if (!dictionary.TryGetValue(key, out r))
        {
            // not in cache yet
            r = f(a1, a2);
            dictionary.Add(key, r);
        }
        return r;
    };
}

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) =>
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // calculate it in the right direction
    if (x < gridSize)
        i += progress(x + 1, y);
    // and in the down direction
    if (y < gridSize)
        i += progress(x, y + 1);

    // self-explanatory :)
    return i;
})).Memoize();

顺便说一下，我想不出更好的方法来使用这两个参数作为字典的键。我在谷歌上搜索了一下，这似乎是一个常见的解决方案。好吧。

Answer 1

快速无编程解决方案(基于组合学)

我认为“无回溯”意味着我们总是增加 x 或增加 y。

如果是这样，我们知道总共需要 40 步才能到达终点——x 增加 20 步，y 增加 20 步。

唯一的问题是这 40 个中的哪一个是 x 的 20 个增加值。问题是:您可以用多少种不同的方式从一组 40 个元素中选择 20 个元素。 (这些元素是:第 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。