跟踪哪些递归调用已经完成了-C#

本文关键字：-C# 递归 调用 跟踪 | 更新日期: 2023-09-27 18:21:55

我正在解决这个问题，在这个问题中，我被要求在20乘20的网格中从一个角落到另一个角落的最短路径的数量。我知道这是一个简单的组合问题，但对我来说，挑战在于实现一种解决它的方法

我的想法是使用递归：到网格点（m，n）的路径数等于到（m-1，n）路径数加上到（m，n-1）路径数。我开始使用以下代码：

using System;
class Program
{
    static void Main()
    {
        long noOfPaths = CountPaths(15, 15);
        Console.WriteLine(noOfPaths);
        Console.ReadKey();
    }
    static long CountPaths(int m, int n)
    {
        if (m == 0) return 1;
        else if (n == 0) return 1;
        return CountPaths(m-1,n) + CountPaths(m,n-1);
    }
}

这运行得很好，并返回了正确数量的路径，但它的运行时间随着网格大小的增加而急剧增加，我无法达到20x20。上面的一个主要问题是，它对同一个网格点进行了多次递归调用，我想了解一些关于跟踪这一点的最佳方法的建议。到目前为止，我已经在这个网站上找到了关于"全局变量"的帖子，我的解决方案是创建一个可以从任何地方访问的数组。下面的代码解决了我的问题，而且速度相当快。

using System;
namespace problem15
{
class Program
{
    static void Main()
    {
        long noOfPaths = CountPaths(Values.m-1, Values.n-1);
        Console.WriteLine(noOfPaths);
        Console.ReadKey();
    }
    static long CountPaths(int m, int n)
    {
        if (m == 0) return 1;
        else if (n == 0) return 1;
        if (Values.A[m - 1, n] == 0) Values.A[m - 1, n] = CountPaths(m - 1, n);
        if (Values.A[m, n - 1] == 0) Values.A[m, n - 1] = CountPaths(m, n - 1);
        return Values.A[m-1,n] + Values.A[m,n-1];
    }
}
static class Values
{
    static public int m = 21, n = 21;
    static public long[,] A = new long[m, n];
}
}

这是一个可以解决问题的方案，还是被认为是"糟糕的形式"？此外，我知道在这个问题中还有更多的优化，例如，到（k，l）的路径数与到（l，k）的路径数目相同。

跟踪哪些递归调用已经完成了-C#

您的递归解决方案是可以的。

另一个递归解决方案也可以，它是以"动态编程"方式实现的递归选项。

还有一种迭代和数学的方法。

你可以在这里看到更多。它来自官方网站。

第二个解决方案的想法很好，它是一种众所周知的技术，称为Memoization。然而，实施情况并非如此。使用共享（"全局"）状态在很大程度上限制了该方法的使用，这还不包括这样一个事实，即按照您的编写方式，它只能被调用一次，并且参数是硬编码的。这是正确的方法。

让我们从第一个解决方案开始，将其封装在一个类中，并将非递归部分与递归部分分离：

public class MyAlgorithms
{
    public static long CountPaths(int m, int n)
    {
        // Agrument validations goes here
        return CountPathsRecursive(m, n);
    }
    private static long CountPathsRecursive(int m, int n)
    {
        if (m == 0 || n == 0) return 1;
        var count = CountPathsRecursive(m - 1, n) + CountPathsRecursive(m, n - 1);
        return count;
    }
}

并使用

using System;
class Program
{
    static void Main()
    {
        long noOfPaths = MyAlgorithms.CountPaths(21, 21);
        Console.WriteLine(noOfPaths);
        Console.ReadKey();
    }
}

现在，您可以通过应用第二个想法来优化实现，而不会影响的使用

public class MyAlgorithms
{
    public static long CountPaths(int m, int n)
    {
        // Agrument validations goes here
        var counts = new long[m, n];
        return CountPathsRecursive(m, n, counts);
    }
    private static long CountPathsRecursive(int m, int n, long[,] counts)
    {
        if (m == 0 || n == 0) return 1;
        var count = counts[m - 1, n - 1];
        if (count == 0) counts[m - 1, n - 1] = count =
            CountPathsRecursive(m - 1, n, counts) + CountPathsRecursive(m, n - 1, counts);
        return count;
    }
}

希望你明白。同样的方式，你可以改变实现使用迭代算法，只是公式等。

纯粹的OO解决方案（既不快速也不贪婪；-））：

有一个优点：您可以获得所有找到的路径及其完整的单元格列表。

   public class MyGrid {
        public int Width { get; protected set; }
        public int Height { get; protected set; }
        public MyCell[,] MyCells { get; protected set; }
        public List<MyPath> MyPathList;
        public MyGrid(int h, int w) {
            this.Width = w;
            this.Height = h;
            this.MyCells = new MyCell[this.Width, this.Height];
            for (int x = 0; x < Width; x++) {
                for (int y = 0; y < Width; y++) {
                    this.MyCells[x, y] = new MyCell(this, x, y);
                }
            }
            this.MyPathList = new List<MyPath>();
        }
        public int FindPaths() {
            this.MyPathList.Clear();
            var p = new MyPath(this);
            this.MyPathList.Add(p);
            var c = new MyCell(this,0,0);
            p.AddCellRecursive(c); 
            return MyPathList.Count;
        }
    }
    public class MyCell {
        public MyGrid myGrid { get; protected set; }
        public int X { get; protected set; }
        public int Y { get; protected set; }
        public MyCell(MyGrid gr, int x, int y) {
            this.myGrid = gr;
            this.X = x;
            this.Y = y;
        }
        public MyCell RightNeighbour {
            get {
                if (this.X == this.myGrid.Width-1)
                    return null;
                else
                    return this.myGrid.MyCells[this.X+1, this.Y];
            }
        }
        public MyCell BelowNeighbour {
            get {
                if (this.Y == this.myGrid.Height-1)
                    return null;
                else
                    return this.myGrid.MyCells[this.X, this.Y+1];
            }
        }
        public override string ToString() {
            return string.Format("{0}|{1}", this.X, this.Y);
        }
    }
    public class MyPath{
        public MyGrid myGrid { get; protected set; }
        public List<MyCell> MyCellList;
        public MyPath(MyGrid gr) {
            this.myGrid = gr;
            this.MyCellList = new List<MyCell>(); }
        public void AddCellRecursive(MyCell c) {
            this.MyCellList.Add(c);
            var r = c.RightNeighbour;
            var b = c.BelowNeighbour;
            MyPath second=null;
            if (b == null && r == null)
                return;//end
            else if (r == null) {
                second = this;
            }
            else {
                second = this.Clone();
                this.myGrid.MyPathList.Add(second);
                this.AddCellRecursive(r);
            }
            if (b == null)
                this.myGrid.MyPathList.Remove(second);
            else 
                second.AddCellRecursive(b);
        }
        public MyPath Clone(){
            var retPath = new MyPath(this.myGrid);
            foreach (var c in MyCellList) {
                retPath.MyCellList.Add(c);
            }
            return retPath;
        }
    }
相关文章：