1

欧拉计划15(剧透): 在此处输入图像描述

我意识到这是一个中心二项式系数序列,从而解决了这个问题。另一个好方法是通过动态编程。尽管如此,递归执行似乎很自然,我还是这样做了。

这是我的解决方案:

public long getNumberOfPaths()
{
    getPaths(board[0][0]); //2D array of Positions
    return count; //instance member (long)
}

private void getPaths(Position p)
{   
    if (p.hasDown())
    {
        getPaths(p.getDown());
    }

    if (p.hasRight())
    {
        getPaths(p.getRight());
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1))
    {
        count++;
    }
}

注意:板的大小是:1 + inputSize,所以在这种情况下它将是 21,因为我们有一个 20x20 的网格。这是因为解决上述 2x2 问题等同于解决 3x3 问题,但要通过正方形而不是在它们的边界上移动。

其逻辑getPaths(Position p)是:尽可能向下走,然后尽可能向右走。一旦你到达右下角Position,将路径数加 1 ( count),回到你上次下台的地方,现在不要往下走,而是往右走(如果你不能往右走,再回溯,等等)。重复过程。当然,递归本身会跟踪所有这些。如果不清楚,或者如果有人想搞砸工作代码,这里有两个小类。添加一些打印语句getPaths(Position p)应该使发生的事情非常明显。

无论如何,这一切正常,我的问题是如何在不使用count. 同样,如上所述,我知道有更好的方法来解决这个问题,这不是我的问题。我的问题是尝试获得与上述相同的功能,但不使用辅助变量。这将意味着getPaths(Position p)从更改void为使其返回 a long。这可能是一个简单的修复,但我现在没有看到它。提前致谢。

本质上,我希望递归调用它们自己来跟踪计数,而不是任何类型的实际计数器。

4

3 回答 3

1

我相信这应该有效

private long getPaths(Position p) {
    return (p.hasDown() ? getPaths(p.getDown()) : 0) +
        (p.hasRight() ? getPaths(p.getRight()) : 0) +
        ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1) ? 1 : 0);
}
于 2013-06-27T16:37:47.933 回答
1

不使用辅助变量:

public long getNumberOfPaths()
{
    return getPaths(new Position(0,0)); //2D array of Positions
}

private long getPaths(Position p)
{  
    long result= 0;
    if (p.hasDown())
    {
        result+= getPaths(p.getDown());
    }

    if (p.hasRight())
    {
        result+= getPaths(p.getRight());
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length -1))
    {
        result+= 1;
    }
    return result;
}

那么试试这个:

private long getPaths(Position p)
{ 
    return (p.hasDown() ? getPaths(p.getDown()) : 0) + 
                 (p.hasRight() ? getPaths(p.getRight()) : 0) + 
                 ((p.getRow() == board.length - 1) && 
                 (p.getColumn() == board.length -1) ? 1 : 0);
}
于 2013-06-27T16:45:26.030 回答
0

您可以简单地更改方法签名以将计数作为参数:

private long getPaths(Position p, long count) {
    if (p.hasDown()) {
        getPaths(p.getDown(), count);
    }

    if (p.hasRight()) {
        getPaths(p.getRight(), count);
    }

    if ((p.getRow() == board.length - 1) && (p.getColumn() == board.length - 1)) {
        count++;
    }
    return count;
}
于 2013-06-27T16:38:19.700 回答