CS162 Lab 9 - Pascal's Triangle

CS162 Lab 9 - Pascal's Triangle

by Deleted user -
Number of replies: 2

Just spent the last 2 hours tracking down a bug that ended up being super simple, thought I'd share my frustrating experience and maybe save someone the trouble.

I had my recursive function running and my triangle was mostly correct, but some of the numbers were off.  I couldn't figure out why, it worked on paper, worked on my calculator, worked when I tested those numbers in a separate piece of code.  Why wouldn't it work in my function?  I assumed I either had a mistake in my formula, or my code was rounding off somewhere.

The piece of code ended up being subtle, but simple.  I was using:
number *= x/y; // as an example, number starts at 2, is multiplied by 1/2, should be 1, right?

Wrong, it was rounding to 0.  Ok, but if I printed a test line as:
2*1/2 I got 1.  So why was I still getting 0 in my function?

I finally realized that in this case, n*= is not the same as n = n*.  The order of operations rounds 1/2 down to 0, then does 1*0=0.  I did not think about it, but I should have realized it would resolve both sides separately, and of course round down because x and y are both ints.

So anyway, there's how I spent the last 2 hours.  It did not feel very rewarding, but I understand my mistake now and will hopefully avoid relearning it so painfully next time.  And on the plus side, once that was fixed the rest of my program is working nicely.

Anyone else have a painful learning experience on this one?  Hope to see a lot of you in class tomorrow, it should be a good catch-up day.

In reply to Deleted user

Re: CS162 Lab 9 - Pascal's Triangle

by Deleted user -

I'm having a bit of difficulty getting my triangle started.  The hint said to store each line in an array, but would that have me create an array for each line, or cycle through one array with a loop, altering and printing one line at a time? I just need to get a foothold and I think I can take it from there, but right now I'm stuck.

In reply to Deleted user

Re: CS162 Lab 9 - Pascal's Triangle

by Deleted user -

Great question.  I bet everyone did this differently, but here's my thoughts.

Because we're using a recursive function to display the triangle, the innermost run of the function will complete first.  So I didn't bother storing the numbers, I just printed them as I went.

As an example, if my function starts out by printing 3 lines of the triangle, it looks something like:

displayTriangle(3);

Then inside my displayTriangle function, I check that number to see if it's bigger than 1.  If so, I call the function again with a smaller number, like displayTriangle(3-1);

So the function calls itself until it's only printing 1 line of the triangle.  Now I'm at the top, and can use println to display a single row of the triangle.

Once that's done, the method ends, and the rest of displayTriangle(3-1) runs, which prints out line #2 of the triangle.

Then displayTriangle(3) runs, printing line #3 of the triangle, and so on.

If I were to write it out, it would look something like:

displayTriangle(3) starts
  3 isn't 1, so call displayTriangle(3-1)
    displayTriangle(2) starts
       2 isn't 1, so call displayTriangle(2-1)
         displayTriangle(1) starts
         1 is 1, so print line 1 of the triangle
      print line 2 of the triangle
  print line 3 of the triangle

I hope that helps a little.  For me, the hardest part was figuring out how to form each line of the triangle, which I did using a math formula.  Since the assignment was more about recursion than a common and several hundred year old formula, I think it's safe to describe here.  So here goes:

Each number in a row of Pascal's Triangle can be found using it's position and the previous number in that row.  The first number of a row is always 1, I'll call this num.

Every number after the first, can be found by using num*(col-distance away from edge)/(distance away from edge)

So the 1st number in row 5 is 1.
The second number in row 5 is 1*(5-1) / 1=4.
The 2nd number in row 5 is 4 * (5-2) / 2 = 6
The 3rd number in row 5 is 6 (5-3) / 3 = 4

And so on.  This works for any row of Pascal's Triangle, and is a commonly used formula.  I'm sure there are other ways to find each number as well.

Anyway, hopefully something I said helps, post back if you're still stuck or someone has another suggestion.