0

我想以非递归的方式重写这个算法（我用来解决 ProjectEuler 问题 15）的功能。

是的，我意识到有很多更好的方法可以解决实际问题，但作为一个挑战，我想尽可能简化这个逻辑。

public class SolveRecursion
{
    public long Combination = 0;
    public int GridSize;

    public void CalculateCombination(int x = 0, int y = 0)
    {
        if (x < GridSize)
        {
            CalculateCombination(x + 1, y);
        }
        if (y < GridSize)
        {
            CalculateCombination(x, y + 1);
        }
        if (x == GridSize && y == GridSize)
            Combination++;
    }
}

和测试：

[Test]
public void SolveRecursion_GivenThree_GivesAnswerOf20Routes()
{
    solveRecursion.GridSize = 3;
    solveRecursion.CalculateCombination();
    var result = solveRecursion.Combination;
    Assert.AreEqual(20, result);
}

[Test]
public void SolveRecursion_GivenFour_GivesAnswerOf70Routes()
{
    solveRecursion.GridSize = 4;
    solveRecursion.CalculateCombination();
    var result = solveRecursion.Combination;
    Assert.AreEqual(70, result);
}

编辑：这是另一个以两种方式编写的简单函数：

//recursion
private int Factorial(int number)
{
    if (number == 0)
        return 1;
    int returnedValue = Factorial(number - 1);

    int result = number*returnedValue;
    return result;
}

//loop
private int FactorialAsLoop(int number)
{
    //4*3*2*1
    for (int i = number-1; i >= 1; i--)
    {
        number = number*i;
    }
    return number;
}

任何提示将不胜感激。我尝试了动态编程解决方案（它使用更多基于数学的方法）和一个成功解决难题的方程式。

我想知道——这第一个算法可以简单地做成非递归的吗？

4

1 回答 1

0

非递归解决方案是：

const int n = 4;
int a[n + 2][n + 2] = {0};

a[0][0] = 1;
for (int i = 0; i < n + 1; ++i)
    for (int j = 0; j < n + 1; ++j) {
        a[i][j + 1] += a[i][j];
        a[i + 1][j] += a[i][j];
    }

std::cout << a[n][n] << std::endl;

仅供参考，这个问题应该已经在纸上解决了，NxM 网格的答案是 C(N+M,N)，其中 C 是组合函数 - http://en.wikipedia.org/wiki/Combination

于 2013-08-26T17:20:46.940 回答