为什么超出了内存限制,我该如何避免呢? [英] Why was the memory limit exceeded and how can I avoid this?
本文介绍了为什么超出了内存限制,我该如何避免呢?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
import java.util.*;
public class AlmostPerfect {
public static void main(String[] args) {
Scanner x = new Scanner(System.in);
while(x.hasNext()) {
int n = x.nextInt();
int sum = recursion(n, n-1, 0);
if (sum == n) {
System.out.println(n + " perfect");
} else if ((n - sum) <= 2) {
System.out.println(n + " almost perfect");
} else {
System.out.println(n + " not perfect");
}
}
}
public static int recursion(int n, int x,int sum) {
if(x == 0){
return sum;
}
else if (n % x == 0) {
sum += x;
return recursion(n, x-1, sum);
}
else{
return recursion(n, x-1, sum);
}
}
}
我想从根本上找到解决方案的问题.存在解决方案,但是我无法理解内存超出限制属性.
I want to basically find what's wrong with my solution... There exists a solution for this, but I can't understand the memory limit exceeded property.
问题链接: https://open.kattis.com/problems/almostperfect
推荐答案
如果必须使用递归解决方案,则可以限制递归的深度,以避免堆栈溢出.
If you must prefer a recursive solution, you can limit the depth of the recursion, to avoid stack overflow.
您可以在连续的时间间隔(一次为一个时间间隔)上运行递归解决方案:
You can do it be running the recursive solution on continuous intervals, one interval at time:
import java.util.stream.IntStream;
public class AlmostPerfect {
// Defines the recursive iteration depth. increase it and you run into
// Stack overflow
private static int RECURSION_DEPTH = 5000;
public static void main(String[] args) {
// Run comparison test between recursive and non recursive solutions
IntStream.range(1, 200000).forEach(i -> {
double sumRecursive = recursionWithLimitedDepth(i);
double sumIterative = iterative(i);
if((sumRecursive != sumIterative)) {
System.out.println("for " + i + " " + sumRecursive + "<>" + sumIterative);
return;
}
if((i%20000) == 0) {
System.out.println("20,000 numbers successfully checked");
}
});
System.out.println("Test finished");
}
// Helper method for recursive solution
public static double recursionWithLimitedDepth(int n) {
double sum = 0;
int rangeStart = n-1;
int rangeEnd = rangeStart - RECURSION_DEPTH;
while (rangeStart > 0) {
sum += recursionWithLimitedDepth(n, rangeStart, rangeEnd, 0);
rangeStart = (rangeEnd - 1) >= 0 ? rangeEnd - 1 : 0;
rangeEnd = (rangeStart - RECURSION_DEPTH) >= 0 ? rangeStart - RECURSION_DEPTH : 0;
}
return sum;
}
// Run recursive solution on a limited range defined by rangeStart, rangeEnd
public static double recursionWithLimitedDepth(int numberToTest, int rangeStart,
int rangeEnd, double sum) {
if(rangeStart == 0) {
return sum;
}
else if ((numberToTest % rangeStart) == 0) {
sum += rangeStart;
}
if(rangeStart == rangeEnd) {
return sum;
}
return recursionWithLimitedDepth(numberToTest, rangeStart-1, rangeEnd, sum);
}
// Simple iterative to test against
public static double iterative(int n) {
double sum = 0;
for(int x = n-1; x > 0; x--) {
if((n%x) == 0) {
sum += x;
}
}
return sum;
}
}
请注意, sum
是 double
,以避免 Integer
溢出(已通过 Integer.MAX_VALUE
测试).
Note that sum
is double
to avoid Integer
overflow (tested with Integer.MAX_VALUE
).
这篇关于为什么超出了内存限制,我该如何避免呢?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文