i have to create a program that displays the nth line of pascals triangle in other words it has to display whatever line in pascal's triangle i choose whether it be line 1 or line 9583
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
it could be coded in most languages i need to code it in java with recursion instead of iteration but i should be able to figure it out i don't know the formulas and algorithms for the pascal triangle
You can find the formulas and some related things here. There is no simple formula for this. The easiest way is just to implement an iterative procedure. This is probably not the most efficient method though.
I'll write you a quick pseudocode routine....
| Code: |
FUNCTION PascalTriangle(MaxRow)
{
i = 1; // Use i as a counter
OldTriangle= array(1..MaxRow); // Use arraya to hold the triangle patterns
NewTriangle= array(1..MaxRow);
WHILE ( i <= MaxRow)
{
OldTriangle(i) = 0;
i++;
# Fill array with zeroes to begin with
}
NewTriangle(1) = 1;
# Set the first item to one
i = 1;
WHILE( i <=MaxRow )
{
NewTriangle() = OldTriangle()
IF ( OldTriangle(i) != 0 AND OldTriangle(i+1) != 0 )
{
i = MaxRow // Skip the rest of the triangle if remaining is all zeroes
}
ELSE
{
NewTriangle(i+1) = OldTriangle(i) + OldTriangle(i+1);
i++;
}
}
|
Return NewTriangle;
Hope this at least gives you an idea hmm interesting but i think i might try uysing the formula
n!
--------
r!(n-r)!
where n = the row number and because im not allowed to use iteration recusively call r which = the position in the row unil r > n as the first position would be 0 and the rows atart at 0 i will initialize an array with n elements in it in the code and from there recursively fill the array
Hmm, oops I forgot about that formula.... A-level maths was a while back.
I'd be interested to see if it was much faster than my method though, as even with the formula you have a lot of iteration because of the factorials (n!, r!).
Happy programming 
well for this project i had to use recursion no itteration
and this code has a problem that it cant go over line 20 cause long cannot handle it
but here is what i have
public class pascal
{
private int r = 0 ;
String[] element;
private int n;
private int counter = 0;
public pascal(int row)
{
n = row;
element = new String[row + 1];
CreateRow();
}
public void CreateRow()
{
if (r<=n)
{
element[r] = ((factorial(n) / (factorial(r)*factorial(n-r))) + " ");
r++;
CreateRow();
}
PrintRow();
}
public void PrintRow()
{
if (counter<=n)
{
System.out.print( element[counter]);
counter++;
PrintRow();
}
}
public static long factorial(long num) {
if (num < 0) return -1;
if (num == 0) return 1;
if (num <= 2) return num;
return (num * factorial(num - 1));
}
}
