java.lang.ArrayIndexOutOfBoundsException: help

[SamK21]

hi

i have writtten a program which incorporrates pascals triangle to calcuate n choose r, but i have followed the task instructions and seem to get an outofbounds error and cant seem to make out whats wrong:



public class TestPascal {

public static void main(String[] args) {
InputFrame theInputFrame = new InputFrame();
while(true){
int n = theInputFrame.getInt();
int r = theInputFrame.getInt();
//int maxN = (n > 10) ? n - 10: 0;
//PascalTriangle test = new PascalTriangle(maxN);
PascalTriangle test = new PascalTriangle(n-10);
if (n > 10){
System.out.println(n+", "+r);
System.out.println(test.binomial(n,r));
}
}
}
}


this is the code for the test program which gets values for n and r

this is the code that causes an error and i have highlighted the line:



public class PascalTriangle {
private int maxN;
private double[][] triangle;

PascalTriangle(int maxN){

this.maxN=maxN;

triangle = new double[maxN+1][];

for (int n = 0; n < triangle.length; n++) {
triangle[n] = new double[n+1];

for (int r = 0; r < triangle[n].length; r++) {
triangle[n][r] = -1;
}
triangle[n][n] = 1;
}

}


public double binomial(int n, int r) {


if (triangle[n][r] >= 0) {//line that causes the error in the outofbounds
return triangle[n][r];
} else {
return triangle[n][r] = binomial(n - 1, r - 1) + binomial(n - 1, r);
}

}



the binomial method is meant to do the follwoing:

The method body is the same basic algorithm, except that if 0 <= n <= maxN and 0 <= r <= n then triangle[n][r] must be taken into account:

--If triangle[n][r] is positive, then it is returned as the result.

--Otherwise the result is calculated by the usual recursion but is then also assigned to triangle[n][r].

this what i the output window does when i enter a value:

30, 15

java.lang.ArrayIndexOutOfBoundsException: 30
at ex9.PascalTriangle.binomial(PascalTriangle.java:50)//this line is highlighted above
at ex9.TestPascal.main(TestPascal.java:26)

any help would be great

[Joe Nellis]

That recursive function, binomial, reduces n and r by 1. There is no check for when n or r are less than zero. Your problem is when n or r equal zero and this line is called.

return triangle[n][r] = binomial(n - 1, r - 1) + binomial(n - 1, r);
This calls binomial(-1,whatever) and -1 is never an index into an array.

[SamK21]

thanks Joe



public double binomial(int n, int r) {
//System.out.println("n = " + n + "; r = " + r);

if (r < 0 || r > n) {
return 0;
}

if (triangle.length <= n) {
return binomial(triangle.length - 1, r);
}
if (triangle[n].length <= r) {
return binomial(n, triangle[n].length - 1);
}
if (triangle[n][r] >= 0) {
return triangle[n][r];
} else {
return triangle[n][r] = binomial(n - 1, r - 1) + binomial(n - 1, r);
}

}


this now does not throw an expetion but i am not sure if it is actally right i can calcualte numbers by using pascals triangle but the actual answear for n=30, r=15 is wrong

any suggestions on how to change this method would be much appreciated

[SamK21]

i have tryed the above method fully and gives inaccurate values, can some one help me understand why this isnt working.

thanks

[cjard]

get a pencil and paper out and write down what the code is doing. start with n=30 and r=15.. and do yourself, what the computer does. at some point you'll see why it's wrong.

i note there is a significant lack of comments in that code and hence it is likely you will make mistakes. if you had written the comments first, in plain english, of the algorithm to generate a pascal triangle, it stands a better chance of working correctly

[SamK21]

hi thanks for the replies i have got a draft on paper but its long to work through 30 over 15 cause it gives a large number, but i have fixed the problem

cjard your comments are rarely useful to me :)

[dlorde]

cjard your comments are rarely useful to me :) :D :D a Freudian slip, perhaps? ;)

Good or bad job reference?
"You will be lucky to get this man to work for you..."