java - 如何递归地解决 ArrayLists 的问题

Question

我正在尝试编写一个“求解圆”的程序。 Circle 类包含一个三角形对象的 ArrayList 和一个整数的 ArrayList。每个 Triangle 对象都有三个 int 实例字段，代表每个三角形顶点的三个数字。还有一个 Pairs 类(你可以在“代码”部分看到我所有的代码) 下面是一个使用未求解的四个三角形的设置示例:

这是“解决”后的同一个圆圈:

第二张图的Circle是解出的Circle，因为圆的任意一条弧上的数都等于它旁边两个顶点数的和:6 = 1+5, 15 = 6+9, 11 = 7+4，9=5+4。请注意，这是通过旋转给定的三角形获得的。这在代码中类似于简单地更改每个三角形的解决方案中存在的对(其中“对”是两个整数的对象，其中这些整数是每个三角形的圆上的值)

圆并不总是处于“已解决”状态。如果是这种情况，可以旋转三角形，使圆处于求解状态。任何给定圆的前提是存在已解决的状态，因此数字将始终排成一行。

一个圆总是至少有两个三角形，并且没有(实际的)最大数量。每个给定的圆总是可解的，这意味着有一种方法可以旋转每个三角形，使圆上的数字是两个不同三角形的两个相邻顶点之和的结果。

程序的重点是不改变任何给定的实例字段；相反，我只想创建一个名为 solveCircle 的方法，它返回一个表示圆的解决方案的对数组列表。在上面的示例中，solveCircle 方法将返回一个包含以下对的 ArrayList:(4,1)、(5,6)、(9,7)、(4,5)。这些对在解决方案中，因为它们都是三角形上的数字对，并且每一对也在圆上。请注意，解决方案绕着圆圈逆时针旋转。

我的直觉告诉我，这个过程应该涉及某种类型的递归，因为由于圆的循环性质，循环会很棘手；换句话说，我可以循环遍历每一对三角形来找到合适的解决方案，但很可能会有不止一个，并且将每个三角形与下一个求和的解决方案进行比较似乎效率很低；递归似乎是一个更好的选择，但我不确定将递归应用于什么......我应该使用什么算法，甚至基本情况是什么？

public class Triangle
{
    private int num1;
    private int num2;
    private int num3;

    public Triangle(int n1, int n2, int n3)
    {
        num1 = n1;
        num2 = n2;
        num3 = n3;
    }

    public ArrayList<Pair> getPairs()
    {
        ArrayList<Pair> pairs = new ArrayList<Pair>();
        pairs.add(new Pair(num1, num2));
        pairs.add(new Pair(num2, num3));
        pairs.add(new Pair(num3, num1));
        return pairs;
    }
}

class Pair
{
    private int p1;
    private int p2;

    public Pair(int x, int y)
    {
        p1 = x;
        p2 = y;
    }
}

public class Circle
{
    private ArrayList<Triangle> triangles;
    private ArrayList<Integer> sums;

    public Wheel(ArrayList<Integer> s, ArrayList<Triangle> t)
    {
        triangles = t;
        sums = s;
    }

    public ArrayList<Pair> solveCircle()
    {
        //need help here
    }
}

Answer 1

您可以使用 tree将求解的三角形与未求解的三角形分开。已解决和 Unresolved 圆圈也是如此。这样，您可以将其设为 log n 搜索函数，忽略已解决的问题，从而避免不必要的比较。

if (solved)
    add to left side of the tree
else 
    add to right side of the tree

根据用例，其复杂性也可能是一种极端矫枉过正的做法。