8
Vấn đề của tôi là tôi thường nhận được một java.lang.StackOverflowError khi tôi sử dụng đệ quy. Câu hỏi của tôi là - tại sao đệ quy gây ra stackoverflow nhiều hơn so với vòng lặp làm, và có cách nào tốt để sử dụng đệ quy để tránh tràn ngăn xếp?java.lang.StackOverflowError do đệ quy
Đây là một nỗ lực để giải quyết problem 107, nó hoạt động tốt cho ví dụ của họ nhưng hết dung lượng ngăn xếp cho chính sự cố đó.
//-1 16 12 21 -1 -1 -1 16 -1 -1 17 20 -1 -1 12 -1 -1 28 -1 31 -1 21 17 28 -1 18 19 23 -1 20 -1 18 -1 -1 11 -1 -1 31 19 -1 -1 27 -1 -1 -1 23 11 27 -1
public class tries
{
public static int n=7,min=Integer.MAX_VALUE;
public static boolean[][] wasHere=new boolean[n][60000];
public static void main(String[] args)
{
int[] lines=new int[n]; Arrays.fill(lines, -1000); lines[0]=0;
int[][] networkMatrix=new int[n][n];
Scanner reader=new Scanner(System.in);
int sum=0;
for(int k=0; k<n; k++)
{
for(int r=0; r<n; r++)
{
networkMatrix[k][r]=reader.nextInt();
if(networkMatrix[k][r]!=-1) sum+=networkMatrix[k][r];
Arrays.fill(wasHere[k], false);
}
}
recursive(lines,networkMatrix,0,0);
System.out.println((sum/2)-min);
}
public static void recursive(int[] lines, int[][] networkMatrix, int row,int lastRow)
{
wasHere[row][value((int)use.sumArr(lines))]=true;
if(min<sum(lines)) return;
if(isAllNotMinus1000(lines)) min=sum(lines);
int[][] copyOfMatrix=new int[n][n];
int[] copyOfLines;
for(int i=0; i<n; i++)
{
copyOfLines=Arrays.copyOf(lines, lines.length);
for(int k=0; k<n; k++) copyOfMatrix[k]=Arrays.copyOf(networkMatrix[k], networkMatrix[k].length);
if(i!=0&©OfMatrix[i][row]!=0) copyOfLines[i]=copyOfMatrix[i][row];
copyOfMatrix[i][row]=0; copyOfMatrix[row][i]=0;
if(networkMatrix[row][i]==-1) continue;
if(wasHere[i][value((int)use.sumArr(copyOfLines))]) continue;
if(min<sum(copyOfLines)) continue;
recursive(copyOfLines,copyOfMatrix,i,row);
}
}
public static boolean isAllNotMinus1000(int[] lines)
{
for(int i=0; i<lines.length; i++) {if(lines[i]==-1000) return false;}
return true;
}
public static int value(int n)
{
if(n<0) return (60000+n);
return n;
}
public static int sum(int[] arr)
{
int sum=0;
for(int i=0; i<arr.length; i++)
{
if(arr[i]==-1000) continue;
sum+=arr[i];
}
return sum;
}
}
Bạn có chắc chắn rằng các chuyến du ngoạn của bạn không tự gọi mình là vô hạn? Nó có thể giúp đưa mã của bạn vào. Mã số –
rất phức tạp và vì nó hoạt động với số lượng nhỏ, tôi chắc chắn đây không phải là trường hợp. Mặc dù vậy, việc thêm mã là một ý tưởng hay. Tôi chỉ hy vọng nó sẽ không trôi quá nhiều chủ đề. – user2705335
Khi bạn có các dòng Integer.MAX_VALUE, nó chỉ thực hiện đệ quy đầu tiên là 7 trong mỗi vòng lặp cho một số cấp độ sâu, nhưng nó có (7^(n + 1) -1/6) -n-1 lặp đi lặp lại, hầu hết nếu họ nhấn trường hợp cơ sở. Việc bắt đầu cho các vòng lặp sẽ thêm 6 lần n lần các dòng Integer.MAX_VALUE mặc dù. – Sylwester