我必须用Java编写一个递归方法,使用递归将偶数分成2,4,6的和,同时不能有2个相同的数字连续出现。
例如n=8
返回:
([2,4,2], [2,6], [6,2])
(where [2,2,2,2], [2,2,4], [4,2,2], [4,4] are not allowed as answers)
我正在寻找执行此操作的算法。目前我想我需要给该方法提供两个参数,其中一个是 int n
及其他ArrayList<Integer>
存储找到的分离方式。但我很难想到可以做到这一点的算法。
public static ArrayList<Integer> subtractions(int n, ArrayList<Integer> integers){
int sum = 0;
for(Integer i:integers){
sum += i;
}
if(n>2 && sum<n) {
integers.add(n - 2);
return subtractions(n - 2, integers);
}
integers.add(2);
return integers;
}
这就是我现在所拥有的,但在 n=8
的情况下它只给了我一个答案那就是[6,2]
有人可以给我一个起始位置或其他东西吗?
最佳答案
您忽略了整个复杂性。您不应该处理整数列表,而应该处理整数列表的列表。这个问题更多的是关于数据结构而不是数学。我的示例解决方案:
public static List<List<Integer>> subtractions_recursive(int target, int exclude) {
List<List<Integer>> solutions = new ArrayList<>();
if (target == 0) { // base case for recursion
List<Integer> empty = new ArrayList<>(); // ()
solutions.add(empty); // (())
} else {
for (int i = 2; i <= 6 && target - i > -1; i += 2) {
if (i == exclude) {
continue;
}
List<List<Integer>> sub_solutions = subtractions_recursive(target - i, i); // ((4, 2), (6))
for (List<Integer> sub_solution:sub_solutions) {
sub_solution.add(0, i); // ((2, 4, 2), (2, 6))
}
solutions.addAll(sub_solutions);
}
}
return solutions; // ((2, 4, 2), (2, 6), (6, 2))
}
public static List<List<Integer>> subtractions(int target) {
return subtractions_recursive(target, 0);
}
关于java - 使用递归将偶数分解为 2,4,6 的和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55226924/