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

问题描述

我正在尝试编写一个“解决圆圈”的程序。Circle 类包含一个三角形对象的 ArrayList 和一个整数的 ArrayList。每个 Triangle 对象都有三个 int 实例字段，它们代表每个三角形顶点处的三个数字。还有一个 Pairs 类（你可以在“代码”部分看到我拥有的所有代码）这是一个使用四个三角形的设置示例，但未解决：

未解圆

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

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

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

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

该程序的重点是不更改任何给定的实例字段；相反，我只想创建一个名为solveCircle 的方法，该方法返回一个ArrayList of Pairs，它表示Circle 的解决方案。在上面的示例中，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
    }
}

标签： javaalgorithmrecursion

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

问题描述

解决方案

推荐阅读