java - 为什么超出了内存限制,我该如何避免这种情况?
问题描述
代码
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);
}
}
}
我想基本上找出我的解决方案有什么问题......有一个解决方案,但我无法理解超出内存限制的属性。
解决方案
如果您必须更喜欢递归解决方案,您可以限制递归的深度,以避免堆栈溢出。
您可以在连续的时间间隔上运行递归解决方案,一次一个时间间隔:
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
)。
推荐阅读
- c++ - 将复杂列表列表的元组从 c++ 返回到 python
- git - 如何添加分支后面的提交,而不会丢失它前面的提交?
- gitlab - GitLab 页面:可以从项目 wiki 生成静态站点吗?
- node.js - 如何使用 Node.js 永久删除文件?
- java - HTTP 状态 500 - 内部服务器错误 - 数据源不能为空
- html - 老虎机的 CSS 流体布局问题
- javascript - 单击时菜单不切换(关闭)
- node.js - 如何管理在输出类型中可以为空的 GraphQL 子对象类型?
- scala - Spark,Scala在从文件读取后无法正确创建视图
- lua - 如何在 Lua 脚本中像 arduino 一样拥有 currentMilis 和 previousMillis