Как решить проблему с ArrayLists рекурсивно
Я пытаюсь написать программу, которая "решает круг". Класс Circle содержит ArrayList объектов Triangle и ArrayList целых чисел. Каждый объект Triangle имеет три поля экземпляра типа int, которые представляют три числа в вершинах каждого треугольника. Существует также класс Pairs (вы можете увидеть весь код, который у меня есть, в разделе «код») Вот пример установки с использованием четырех треугольников, которая не решена:
А вот тот же круг после «решения»:
Окружность на втором рисунке — это решенная Окружность, потому что число на любой дуге окружности равно сумме двух номеров вершин рядом с ней: 6 = 1+5, 15 = 6+9, 11 = 7+4. , а 9 = 5+4. Обратите внимание, что это было получено путем вращения данных треугольников. В коде это аналогично простому изменению пары, которая присутствует в решении для каждого треугольника (где «пара» — это объект из двух целых чисел, где эти целые числа — это значения в круге для каждого треугольника)
Круг не всегда дается в «решенном» состоянии. Если это так, треугольники можно повернуть так, чтобы круг оказался в решенном состоянии. Предварительным условием любого данного круга является то, что существует решенное состояние, поэтому числа всегда будут выстраиваться.
Круг всегда будет иметь по крайней мере два треугольника, и не существует (практического) максимального количества. Каждый заданный круг всегда будет разрешим, а это означает, что есть способ повернуть каждый треугольник так, чтобы число на круге было результатом суммы двух соседних вершин из двух разных треугольников.
Смысл программы в том, чтобы не изменять ни одно из заданных полей экземпляра; вместо этого я просто хочу создать метод с именем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
}
}
Треугольник 0 будет первым, поэтому я буду использовать треугольник 0 и треугольник 1, чтобы найти сумму 1, и так далее, пока не доберусь до треугольника «size()-1». Затем я бы использовал это и Triangle 0 с суммой 0. Размер суммы ArrayList будет на единицу меньше размера Triangle ArrayList.
Я бы использовал подход судоку. Обойдите круг и найдите треугольник, который имеет минимальное количество допустимых ориентаций. Если существует только одна допустимая ориентация, выберите ее и заблокируйте треугольник. Если есть две или три допустимые ориентации, выберите одну и рекурсивно.
Я думаю, что моя проблема в том, что я запутался в концепции рекурсии, когда она не используется в последовательностях чисел или ситуациях, таких как факториал или сумма. В этом случае я не совсем уверен, что такое рекурсия. Как бы я написал базовый случай? Я думаю, мне просто нужен пример того, как это работает, например, в круге из 4 треугольников, который я привел в качестве примера.
Я бы добавил переменную state в класс Triangle. Есть два состояния: Undecided и Locked. На каждом уровне рекурсии одному треугольнику назначается ориентация и блокируется. Это означает, что на каждом уровне рекурсии на один нерешенный треугольник меньше. Успешный базовый случай: все треугольники заблокированы. В противном случае найдите неопределенный треугольник с наименьшим количеством допустимых ориентаций. Выберите ориентацию для этого треугольника, заблокируйте его и рекурсивно. Обратите внимание, что может быть неопределенный треугольник без допустимых ориентаций. Это неудачный базовый случай.
вы сказали: «Размер суммы ArrayList будет на единицу меньше, чем размер Triangle ArrayList». Как это может быть? посчитайте треугольники и суммы на фото. они одинаковые по счету.
Ответы 2
Вы можете использовать дерево, чтобы отделить решенные треугольники от нерешенных. То же самое для кругов, которые решены и которые не решены. Таким образом, вы сделаете функцию поиска log n, которая будет игнорировать решенные, тем самым избегая ненужных сравнений.
if (solved)
add to left side of the tree
else
add to right side of the tree
Сложность также может быть чрезмерной в зависимости от варианта использования.
Я еще не узнал о деревьях в своем классе, и я не могу использовать ничего, что не использовалось. Я не понимаю, что вы подразумеваете под «решенными треугольниками». Я не узнаю, правильный ли треугольник, пока весь круг не будет решен правильно. Например, если у меня есть сумма 10 и у меня есть два смежных треугольника с вершинами 3,4,8 и 7,6,2, их можно было бы расположить тремя разными способами, которые были бы правильными; но только один будет работать на основе другой информации в круге, а именно других сумм и других треугольников.
Отредактируйте свой вопрос, добавив еще немного примера того, как можно решить проблему. Например, из этого я не могу понять максимальный размер круга и каков домен/диапазон значений, существующих для проблемы.
Вот почему я думаю, что это как-то связано с рекурсивностью, когда я проверял бы правильность двух треугольников, затем, если они проверяют, работает ли третий, и, если он действительно переходит к четвертому, но если это не так. , вернитесь и снова просмотрите первые два треугольника. Я просто не уверен, как это реализовать.
Отредактировано с примером «данного» Круга, а затем решенной версией. Мне нужно написать код, который возьмет этот заданный круг, а затем создаст список пар, представляющий пары вершин каждого треугольника, которые являются частью решения.
Я не думаю, что этот ответ правильный. Треугольник не «решен» изолированно. Возможно, его придется снова повернуть в зависимости от того, что произойдет позже.
Ранее он упомянул, что треугольники можно решить, а затем их нужно будет проверить с другими треугольниками, я полагаю, это относится к кругам, хотя я все еще думаю, что вопрос не совсем ясен, как это применяется.
на начальном этапе вы вызываете помощника три раза: один раз для каждой пары, пока не будет возвращен успех (для обозначения успеха можно использовать логическое значение).
помощник выполняет рекурсивный шаг.
для рекурсивного шага у вас есть сумма, простирающаяся позади вас, целое число, которое вы должны объединить с этой суммой, и три возможных способа ее достижения... однако вы не возвращаете успех, если ваш рекурсивный вызов также не возвращает успех
для конечного шага вращение не разрешено, только окончательная истина или ложь, если я завершил сумму позади меня.
Итак, моя вспомогательная функция — это логическая функция, которая возвращает истину, если сумма двух вершин равна сумме, которую я хочу? Я немного запутался с вашим объяснением (может быть, потому, что мне трудно представить это как рекурсивное так же, как рекурсивны числа Фибоначчи). Приношу свои извинения за несвоевременность ответов; Я пытался сделать это самостоятельно без рекурсии. Я что-то придумал, но это сумбурно и, к сожалению, не выводит правильный ответ.
вспомогательная функция возвращает истину, ЕСЛИ ее текущее вращение соответствует требуемой сумме позади нее И рекурсивный вызов также истинен, ИНАЧЕ она пытается выполнить следующее вращение, ПОКА не попробует все три, ТОГДА она возвращает ложь
«против часовой стрелки», но что будет раньше: треугольник 0 или сумма 0?